stack - 从堆栈中删除重复元素

Question

假设我有一个堆栈，它的元素是 [1,2,3,3,2,1,4,5,4,5] 堆栈的顶部指针指向元素 1。现在我想删除所有重复的元素，所以我的最终堆栈将是 [1,2,3,4,5]。我怎么能做这件事，这个操作有什么算法吗？此操作需要的最小堆栈数是多少。

Answer 1

好吧，你没有指定任何语言，所以我会尝试给出一些步骤来对一些伪语言执行此操作：

Stack FunctionName(Stack paramStack)
{
   Stack aux1 = param;
   Stack aux2;
   while (aux1.size() > 0)
   {
      StackElement eleAux = aux1.pop();
      if (NotExist(aux2,eleAux))
      {
         aux2.push(eleAux);
      }
    }
    while (aux2.size() > 0)
    {
       StackElement eleAux = aux2.pop();
       aux1.push(eleAux);
    }
  }

假设 Stack 表示堆栈的数据结构（抱歉冗余），而 StackElement 表示堆栈的元素。“NotExist”函数仅验证某个元素是否在某个堆栈上不存在。

希望它有所帮助。^^

Answer 2

@ColdHack 的答案从第一个堆栈中的每个元素遍历第二个堆栈，这在大堆栈大小上可能代价高昂。我想到的第一件事是使用哈希映射并从堆栈中弹出每个值查找它的映射 - 如果它已经存在，则不执行任何操作，如果没有将其放入并将哈希映射中的键设置为来自的值将哈希映射中的堆栈和值映射到堆栈中的索引，然后在完成后按值对哈希映射进行排序并将其放入堆栈中。如果这个想法不清楚，我可以尝试发布一些通用代码。