唯一元素堆栈的容器

Question

我要做的是构造一个包含唯一元素的堆栈。

如果一个元素被推到已经在堆栈中的位置，则该元素不会被推到，但现有元素应该被移动到堆栈的顶部，即。ABCD+B>ACDB

我想告诉你，哪个容器将是具有此功能的最佳选择。

我决定用户堆栈适配器超过列表，因为

1. 列表确实为元素移动提供了恒定时间
2. list是堆栈本机支持的容器之一

我选择的缺点是必须手动检查重复的元素。

附言：我的编译器不是最新的，所以请不要建议使用unsodered_set。

Answer 1

基本上，您必须在恒定时间移动+长搜索或恒定时间搜索+长移动之间进行选择。

很难说哪一个会更耗时，但考虑一下：

• 每次尝试添加元素时，您都必须搜索元素是否存在
• 您将不必每次都移动元素，因为很明显，在某些时候您将添加容器的"新"元素

我建议您将元素及其堆栈位置存储在不同的容器中。以提供快速搜索的方式存储元素，以提供快速移动的方式存储堆栈位置。用指针连接两者（这样你就可以知道哪个元素在哪个位置，哪个位置容纳哪个元素<--我知道！），你会很快执行任务。

Answer 2

根据您的需求，在我看来，您想要的结构可以从Max Heap派生。

如果不是只存储项，而是存储一对（generation，item），其中generation来自单调递增的计数器，那么堆的"根"总是最后一个看到的元素（其他元素实际上并不重要，是吗？）。

• Pop：堆上的典型Pop操作（delete-max操作）
• 推送：修改操作，以说明结构中"项目"的唯一性
  • 查找"项"，如果找到，则更新其生成（increase-key操作）
  • 如果没有，则插入（insert操作）

考虑到元素的数量（20），在vector上构建堆似乎是一个自然的选择。