如何使用两个堆栈实现队列

Question

今天我考了数据结构。问题之一是如何实现给定堆栈 s1 和 s2 入队和出队的队列函数。这个方法我用过，对吗？

enqueue(& item)
   if(!s2.isEmpty())
      s1.push(s2.pop());
   s1.push(item);
dequeue
   if(!s1.isEmpty())
      s2.push(s1.pop());
   return s2.pop();

Answer 1

通常如果你有这样的堆栈：

[1,2,3,4]

这里的问题是弹出将要按 LIFO 顺序弹出，这意味着它要弹出元素 4。队列应按 FIFO 顺序弹出并弹出元素 1.

要获得这种行为，我们基本上需要能够以相反的顺序弹出。第二个堆栈可以让我们实际反转堆栈的内容。想象一下遍历上面的堆栈并从中弹出并将内容推送到另一个堆栈：

[1,2,3,4] []
[1,2,3]   [4]
[1,2]     [4,3]
[1]       [4,3,2]
[]        [4,3,2,1]

现在，当我们从第二个堆栈中弹出时，我们会根据需要弹出 1。

但是为了按正确的顺序执行此操作，我们必须首先遍历所有第一个堆栈的元素并将它们转移到第二个堆栈。所以在你的 enqueue/dequeue 操作中实际上应该有循环来翻转（反转）这些堆栈的内容。

这就是第二个堆栈派上用场的地方：它允许您通过传输反转堆栈的内容。但是你将需要一个循环，因为想象一下排队 4 个元素。现在要出列，您需要一个循环来反转内容。您可以将 s1 视为压栈，将 s2 视为弹出栈。看来你的想法是对的，但我们需要稍微调整一下：

enqueue(item):
   while(!s2.isEmpty())
      s1.push(s2.pop());
   s1.push(item);

dequeue(item):
   while(!s1.isEmpty())
      s2.push(s1.pop());
   return s2.pop();

Answer 2

就其价值而言，入队不需要循环。如果你有两个栈，enqueueStack 和 dequeueStack，你只需要推入 enqueueStack 并在它为空时反向推入 dequeueStack。

enqueue(item):
    enqueueStack.push(item);
dequeue(item):
    if(dequeueStack.isEmpty()){
        while(!enqueueStack.isEmpty()){
            dequeueStack.push(enqueueStack.pop());
        }
    }
    return dequeueStack.pop()

如果堆栈变大，可以节省一点时间。

如何使用两个堆栈实现队列

How to Implement a Queue With Two Stacks

queue

stack

data-structures