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

假设我们有两个堆栈，没有其他的临时variables。

是否有可能“构build”一个队列数据结构只使用两个堆栈？

Answer 1

保持2堆，我们称他们为inbox和发件outbox 。

排队 ：

• 将新元素推入inbox

出队 ：

• 如果发件outbox为空，请通过从inboxpopup每个元素并将其推送到发件outbox重新填充

• popup并返回发件outbox的顶部元素

使用这种方法，每个元素将在每个堆栈中只有一次 – 意味着每个元素将被推动两次，并popup两次，给予分期恒定时间操作。

这是Java中的一个实现：

 public class Queue<E> { private Stack<E> inbox = new Stack<E>(); private Stack<E> outbox = new Stack<E>(); public void queue(E item) { inbox.push(item); } public E dequeue() { if (outbox.isEmpty()) { while (!inbox.isEmpty()) { outbox.push(inbox.pop()); } } return outbox.pop(); } } 

Answer 2

A – 如何反转堆栈

要了解如何使用两个堆栈构build队列，您应该了解如何将透明堆栈反转。 请记住堆叠是如何工作的，它和厨房的盘子非常相似。 最后洗过的盘子将放在干净的堆栈的顶部，这在计算机科学中被称为“先入先出”（LIFO）。

让我们想像我们的堆栈像一个瓶子如下;

如果我们分别推1,2,3，那么3将会在栈顶。 因为1会先被推动，然后2会被放在1的顶部。最后，3将被放在堆栈的顶部，我们堆栈的最新状态如下：

现在我们将我们的堆栈表示为一个瓶子，其值为3,2,1。 而我们想要反转堆栈，以使堆栈的顶层元素为1，堆栈的底层元素为3.我们可以做什么？ 我们可以把瓶子拿起来倒过来，这样所有的数值都应该相反。

是的，我们可以做到这一点，但这是一个瓶子。 为了做同样的过程，我们需要第二个堆栈，它将以相反的顺序存储第一个堆栈元素。 让我们把我们填充的堆栈放在左边，把新的空的堆栈放在右边。 为了颠倒元素的顺序，我们要从左边的堆栈中popup每个元素，并将它们推送到正确的堆栈。 您可以在下面的图片中看到会发生什么情况。

所以我们知道如何反转一个堆栈。

B – 使用两个栈作为队列

在前面的部分，我已经解释了如何颠倒堆栈元素的顺序。 这很重要，因为如果我们将元素推送到堆栈中，输出将完全按照与队列相反的顺序。 想想一个例子，让我们把整数数组{1, 2, 3, 4, 5}推到一个栈中。 如果我们popup元素并打印它们直到堆栈为空，我们将按照推送顺序相反的顺序获得数组，这将是{5, 4, 3, 2, 1}请记住，对于相同的input，如果我们出队列直到队列为空，输出将是{1, 2, 3, 4, 5} 。 所以很显然，对于相同的元素input顺序，队列的输出与堆栈的输出完全相反。 由于我们知道如何使用额外的堆栈来反转堆栈，我们可以使用两个堆栈来构build一个队列。

我们的队列模型将由两个堆栈组成。 一个堆栈将用于入enqueue操作（堆栈＃1在左边，将被称为input堆栈），另一堆栈将用于dequeue操作（堆栈＃2在右边，将被称为输出堆栈）。 看看下面的图片;

我们的伪代码如下：

---

入队操作

 Push every input element to the Input Stack 

出队操作

 If ( Output Stack is Empty) pop every element in the Input Stack and push them to the Output Stack until Input Stack is Empty pop from Output Stack 

---

让我们分别排列整数{1, 2, 3} 。 整数将被压入位于左侧的input堆栈 （ 堆栈＃1 ）;

那么如果我们执行一个出队操作会发生什么？ 无论何时执行出列操作，队列将检查输出堆栈是否为空（参见上面的伪代码）。如果输出堆栈是空的，则将在输出中提取input堆栈，以便元素的input堆栈将被颠倒。 在返回值之前，队列的状态如下所示;

检查输出堆栈（堆栈＃2）中元素的顺序。 显而易见，我们可以从输出堆栈中popup元素，以便输出与从队列中出队相同。 因此，如果我们执行两个出队操作，首先我们将分别得到{1, 2} 。 然后元素3将是输出堆栈的唯一元素，并且input堆栈将是空的。 如果我们排队元素4和5，那么队列的状态将如下;

现在输出堆栈不是空的，如果我们执行一个出队操作，输出堆栈中只有3个popup。 那么这个国家就会被看作如下。

同样，如果我们再执行两次出队操作，在第一次出队操作时，队列将检查输出堆栈是否为空，这是正确的。 然后popupinput堆栈的元素并将它们推送到输出堆栈，直到input堆栈为空，那么队列的状态将如下所示;

很容易看到，两个出队操作的输出将是{4, 5}

C – 用两个栈构造队列的实现

这是Java中的一个实现。 我不打算使用Stack的现有实现，所以这里的例子将重新发明。

C – 1）MyStack类：一个简单的栈实现

 public class MyStack<T> { // inner generic Node class private class Node<T> { T data; Node<T> next; public Node(T data) { this.data = data; } } private Node<T> head; private int size; public void push(T e) { Node<T> newElem = new Node(e); if(head == null) { head = newElem; } else { newElem.next = head; head = newElem; // new elem on the top of the stack } size++; } public T pop() { if(head == null) return null; T elem = head.data; head = head.next; // top of the stack is head.next size--; return elem; } public int size() { return size; } public boolean isEmpty() { return size == 0; } public void printStack() { System.out.print("Stack: "); if(size == 0) System.out.print("Empty !"); else for(Node<T> temp = head; temp != null; temp = temp.next) System.out.printf("%s ", temp.data); System.out.printf("\n"); } } 

C – 2）MyQueue类：使用两个堆栈实现队列

 public class MyQueue<T> { private MyStack<T> inputStack; // for enqueue private MyStack<T> outputStack; // for dequeue private int size; public MyQueue() { inputStack = new MyStack<>(); outputStack = new MyStack<>(); } public void enqueue(T e) { inputStack.push(e); size++; } public T dequeue() { // fill out all the Input if output stack is empty if(outputStack.isEmpty()) while(!inputStack.isEmpty()) outputStack.push(inputStack.pop()); T temp = null; if(!outputStack.isEmpty()) { temp = outputStack.pop(); size--; } return temp; } public int size() { return size; } public boolean isEmpty() { return size == 0; } } 

C – 3）演示代码

 public class TestMyQueue { public static void main(String[] args) { MyQueue<Integer> queue = new MyQueue<>(); // enqueue integers 1..3 for(int i = 1; i <= 3; i++) queue.enqueue(i); // execute 2 dequeue operations for(int i = 0; i < 2; i++) System.out.println("Dequeued: " + queue.dequeue()); // enqueue integers 4..5 for(int i = 4; i <= 5; i++) queue.enqueue(i); // dequeue the rest while(!queue.isEmpty()) System.out.println("Dequeued: " + queue.dequeue()); } } 

C – 4）样本输出

 Dequeued: 1 Dequeued: 2 Dequeued: 3 Dequeued: 4 Dequeued: 5 

Answer 3

你甚至可以用一个堆栈模拟一个队列。 第二个（临时）堆栈可以通过recursion调用insert方法的调用堆栈来模拟。

将新元素插入队列时，原理保持不变：

• 您需要将元素从一个堆栈传输到另一个临时堆栈，以反转它们的顺序。
• 然后将要插入的新元素推入临时堆栈
• 然后将元素传回原始堆栈
• 新元素将位于堆栈的底部，而最早的元素位于顶部（首先被popup）

一个Queue类只使用一个Stack，如下所示：

 public class SimulatedQueue<E> { private java.util.Stack<E> stack = new java.util.Stack<E>(); public void insert(E elem) { if (!stack.empty()) { E topElem = stack.pop(); insert(elem); stack.push(topElem); } else stack.push(elem); } public E remove() { return stack.pop(); } } 

Answer 4

布赖恩的答案是经典的。 实际上，这是实现恒定function队列和恒定时间的最佳方法之一。 这是因为在函数式编程中，我们有一个非常好的持久堆栈（链表）。 通过以Brian描述的方式使用两个列表，可以实现快速队列，而不需要进行大量的复制。

作为一个未成年人，有可能certificate你可以用两个堆栈做任何事情 。 这是因为双栈操作完全满足了通用图灵机的定义。 但是，正如Forth所示，这并不总是容易的。 🙂

Answer 5

但时间的复杂性会更糟糕。 一个好的队列实现可以在一切时间内完成。

编辑

不知道为什么我的答案已经在这里downvoted。 如果我们编程，我们关心时间复杂性，并且使用两个标准堆栈来创build一个队列是低效的。 这是一个非常有效的相关点。 如果其他人觉得需要更多地降低这一点，我会有兴趣知道为什么。

更详细一点 ：为什么使用两个堆栈比一个队列更糟糕：如果您使用两个堆栈，并且某人在发件箱为空时调用了出队，则需要线性时间才能到达收件箱的底部（如您所见在Dave的代码中）。

您可以将一个队列实现为一个单链表（每个元素指向下一个插入的元素），保留一个额外的指针，指向最后插入的元素进行推送（或使其成为一个循环列表）。 在这个数据结构上实现队列和出队是非常容易的。 这是最坏的情况下，不摊销。 而且，正如评论似乎要求澄清的那样，最坏情况下的恒定时间严格地好于摊销后的恒定时间。

Answer 6

让队列被实现为q和用来实现q的堆栈是stack1和stack2。

q可以通过两种方式来实现：

方法1（通过使enQueue操作昂贵）

这个方法确保新input的元素总是在堆栈1的顶部，所以deQueue操作只是从堆栈1中popup。 为了把元素放在stack1的顶部，使用了stack2。

 enQueue(q, x) 1) While stack1 is not empty, push everything from stack1 to stack2. 2) Push x to stack1 (assuming size of stacks is unlimited). 3) Push everything back to stack1. deQueue(q) 1) If stack1 is empty then error 2) Pop an item from stack1 and return it. 

方法2（通过使deQueue操作昂贵）

在这种方法中，在队列操作中，新元素被input到stack1的顶部。 在出队操作中，如果stack2为空，那么所有的元素都被移动到stack2，最后返回到stack2的顶端。

 enQueue(q, x) 1) Push x to stack1 (assuming size of stacks is unlimited). deQueue(q) 1) If both stacks are empty then error. 2) If stack2 is empty While stack1 is not empty, push everything from stack1 to stack2. 3) Pop the element from stack2 and return it. 

方法2肯定比​​方法1更好。方法1在enQueue操作中移动所有元素两次，而方法2（在deQueue操作中）移动元素一次，仅当stack2为空时移动元素。

Answer 7

队列中的两个堆栈被定义为stack1和stack2 。

排队：排队的元素总是被推入栈1

出队：栈2的顶端可以被popup，因为当栈2不是空的时候它是插入到队列中的第一个元素。 当stack2为空时，我们从stack1中popup所有元素，并将它们一个接一个地推入到stack2中 。 队列中的第一个元素被压入stack1的底部。 popup和popup操作后，可以直接popup，因为它位于堆栈2的顶部。

以下是相同的C ++示例代码：

 template <typename T> class CQueue { public: CQueue(void); ~CQueue(void); void appendTail(const T& node); T deleteHead(); private: stack<T> stack1; stack<T> stack2; }; template<typename T> void CQueue<T>::appendTail(const T& element) { stack1.push(element); } template<typename T> T CQueue<T>::deleteHead() { if(stack2.size()<= 0) { while(stack1.size()>0) { T& data = stack1.top(); stack1.pop(); stack2.push(data); } } if(stack2.size() == 0) throw new exception("queue is empty"); T head = stack2.top(); stack2.pop(); return head; } 

这个解决scheme是从我的博客借来的。 我的博客网页提供了详细的分步操作模拟分析。

Answer 8

你必须从第一个堆栈中popup所有的东西来获得底层元素。 然后把它们全部放回到第二个栈上，以便每次“出列”操作。

Answer 9

对于C＃开发人员来说，这里是完整的程序：

 using System; using System.Collections.Generic; using System.Linq; using System.Text; using System.Threading.Tasks; namespace QueueImplimentationUsingStack { class Program { public class Stack<T> { public int size; public Node<T> head; public void Push(T data) { Node<T> node = new Node<T>(); node.data = data; if (head == null) head = node; else { node.link = head; head = node; } size++; Display(); } public Node<T> Pop() { if (head == null) return null; else { Node<T> temp = head; //temp.link = null; head = head.link; size--; Display(); return temp; } } public void Display() { if (size == 0) Console.WriteLine("Empty"); else { Console.Clear(); Node<T> temp = head; while (temp!= null) { Console.WriteLine(temp.data); temp = temp.link; } } } } public class Queue<T> { public int size; public Stack<T> inbox; public Stack<T> outbox; public Queue() { inbox = new Stack<T>(); outbox = new Stack<T>(); } public void EnQueue(T data) { inbox.Push(data); size++; } public Node<T> DeQueue() { if (outbox.size == 0) { while (inbox.size != 0) { outbox.Push(inbox.Pop().data); } } Node<T> temp = new Node<T>(); if (outbox.size != 0) { temp = outbox.Pop(); size--; } return temp; } } public class Node<T> { public T data; public Node<T> link; } static void Main(string[] args) { Queue<int> q = new Queue<int>(); for (int i = 1; i <= 3; i++) q.EnQueue(i); // q.Display(); for (int i = 1; i < 3; i++) q.DeQueue(); //q.Display(); Console.ReadKey(); } } } 

Answer 10

 public class QueueUsingStacks<T> { private LinkedListStack<T> stack1; private LinkedListStack<T> stack2; public QueueUsingStacks() { stack1=new LinkedListStack<T>(); stack2 = new LinkedListStack<T>(); } public void Copy(LinkedListStack<T> source,LinkedListStack<T> dest ) { while(source.Head!=null) { dest.Push(source.Head.Data); source.Head = source.Head.Next; } } public void Enqueue(T entry) { stack1.Push(entry); } public T Dequeue() { T obj; if (stack2 != null) { Copy(stack1, stack2); obj = stack2.Pop(); Copy(stack2, stack1); } else { throw new Exception("Stack is empty"); } return obj; } public void Display() { stack1.Display(); } } 

对于每一个入队操作，我们都会添加到栈顶1。 对于每个出列，我们将stack1的内容清空到stack2，并删除堆栈顶部的元素。时间复杂度为O（n），因为我们必须将stack1复制到stack2。 入队的时间复杂度与常规堆栈相同

Answer 11

 // Two stacks s1 Original and s2 as Temp one private Stack<Integer> s1 = new Stack<Integer>(); private Stack<Integer> s2 = new Stack<Integer>(); /* * Here we insert the data into the stack and if data all ready exist on * stack than we copy the entire stack s1 to s2 recursively and push the new * element data onto s1 and than again recursively call the s2 to pop on s1. * * Note here we can use either way ie We can keep pushing on s1 and than * while popping we can remove the first element from s2 by copying * recursively the data and removing the first index element. */ public void insert( int data ) { if( s1.size() == 0 ) { s1.push( data ); } else { while( !s1.isEmpty() ) { s2.push( s1.pop() ); } s1.push( data ); while( !s2.isEmpty() ) { s1.push( s2.pop() ); } } } public void remove() { if( s1.isEmpty() ) { System.out.println( "Empty" ); } else { s1.pop(); } } 

Answer 12

我将在Go中回答这个问题，因为Go标准库中没有丰富的集合。

由于一个堆栈实际上很容易实现，我想我会尝试使用两个堆栈来实现一个双端队列。 为了更好地理解我是如何得出答案的，我将实现分为两部分，第一部分希望更容易理解，但是不完整。

 type IntQueue struct { front []int back []int } func (q *IntQueue) PushFront(v int) { q.front = append(q.front, v) } func (q *IntQueue) Front() int { if len(q.front) > 0 { return q.front[len(q.front)-1] } else { return q.back[0] } } func (q *IntQueue) PopFront() { if len(q.front) > 0 { q.front = q.front[:len(q.front)-1] } else { q.back = q.back[1:] } } func (q *IntQueue) PushBack(v int) { q.back = append(q.back, v) } func (q *IntQueue) Back() int { if len(q.back) > 0 { return q.back[len(q.back)-1] } else { return q.front[0] } } func (q *IntQueue) PopBack() { if len(q.back) > 0 { q.back = q.back[:len(q.back)-1] } else { q.front = q.front[1:] } } 

它基本上是两个堆栈，我们允许堆栈的底部被彼此操纵。 我也使用了STL命名约定，其中传统的push，pop，peek操作有前/后缀前缀，而不pipe它们是指队列的前面还是后面。

上述代码的问题是它不能非常有效地使用内存。 事实上，在空间不足的情况下，它会不断增长。 这真的很糟糕。 对此的解决方法是尽可能简单地重用堆栈空间的底部。 我们必须引入一个偏移来跟踪这个，因为Go中的一个切片不能在前面缩小。

 type IntQueue struct { front []int frontOffset int back []int backOffset int } func (q *IntQueue) PushFront(v int) { if q.backOffset > 0 { i := q.backOffset - 1 q.back[i] = v q.backOffset = i } else { q.front = append(q.front, v) } } func (q *IntQueue) Front() int { if len(q.front) > 0 { return q.front[len(q.front)-1] } else { return q.back[q.backOffset] } } func (q *IntQueue) PopFront() { if len(q.front) > 0 { q.front = q.front[:len(q.front)-1] } else { if len(q.back) > 0 { q.backOffset++ } else { panic("Cannot pop front of empty queue.") } } } func (q *IntQueue) PushBack(v int) { if q.frontOffset > 0 { i := q.frontOffset - 1 q.front[i] = v q.frontOffset = i } else { q.back = append(q.back, v) } } func (q *IntQueue) Back() int { if len(q.back) > 0 { return q.back[len(q.back)-1] } else { return q.front[q.frontOffset] } } func (q *IntQueue) PopBack() { if len(q.back) > 0 { q.back = q.back[:len(q.back)-1] } else { if len(q.front) > 0 { q.frontOffset++ } else { panic("Cannot pop back of empty queue.") } } } 

这是很多小函数，但是6个函数中的3个只是另一个的镜像。

Answer 13

在C＃中的解决scheme

  public class Queue<T> where T : class { private Stack<T> input = new Stack<T>(); private Stack<T> output = new Stack<T>(); public void Enqueue(T t) { input.Push(t); } public T Dequeue() { if (output.Count == 0) { while (input.Count != 0) { output.Push(input.Pop()); } } return output.Pop(); } } 

Answer 14

这里是我在java中使用链表的解决scheme。

 class queue<T>{ static class Node<T>{ private T data; private Node<T> next; Node(T data){ this.data = data; next = null; } } Node firstTop; Node secondTop; void push(T data){ Node temp = new Node(data); temp.next = firstTop; firstTop = temp; } void pop(){ if(firstTop == null){ return; } Node temp = firstTop; while(temp != null){ Node temp1 = new Node(temp.data); temp1.next = secondTop; secondTop = temp1; temp = temp.next; } secondTop = secondTop.next; firstTop = null; while(secondTop != null){ Node temp3 = new Node(secondTop.data); temp3.next = firstTop; firstTop = temp3; secondTop = secondTop.next; } } 

}

注意：在这种情况下，popup操作非常耗时。 所以我不会build议使用两个堆栈创build一个队列。

Answer 15

用O(1) dequeue() ，和pythonquick的答案一样 ：

 // time: O(n), space: O(n) enqueue(x): if stack.isEmpty(): stack.push(x) return temp = stack.pop() enqueue(x) stack.push(temp) // time: O(1) x dequeue(): return stack.pop() 

用O(1) enqueue() （在这篇文章中没有提到这个答案），它也使用回溯来冒泡并返回最下面的项目。

 // O(1) enqueue(x): stack.push(x) // time: O(n), space: O(n) x dequeue(): temp = stack.pop() if stack.isEmpty(): x = temp else: x = dequeue() stack.push(temp) return x 

显然，这是一个很好的编码练习，因为它效率低下但优雅。

Answer 16

在Swift中使用两个堆栈的实现：

 struct Stack<Element> { var items = [Element]() var count : Int { return items.count } mutating func push(_ item: Element) { items.append(item) } mutating func pop() -> Element? { return items.removeLast() } func peek() -> Element? { return items.last } } struct Queue<Element> { var inStack = Stack<Element>() var outStack = Stack<Element>() mutating func enqueue(_ item: Element) { inStack.push(item) } mutating func dequeue() -> Element? { fillOutStack() return outStack.pop() } mutating func peek() -> Element? { fillOutStack() return outStack.peek() } private mutating func fillOutStack() { if outStack.count == 0 { while inStack.count != 0 { outStack.push(inStack.pop()!) } } } } 

Answer 17

使用两个java.util.Stack对象实现队列实现：

 public final class QueueUsingStacks<E> { private final Stack<E> iStack = new Stack<>(); private final Stack<E> oStack = new Stack<>(); public void enqueue(E e) { iStack.push(e); } public E dequeue() { if (oStack.isEmpty()) { if (iStack.isEmpty()) { throw new NoSuchElementException("No elements present in Queue"); } while (!iStack.isEmpty()) { oStack.push(iStack.pop()); } } return oStack.pop(); } public boolean isEmpty() { if (oStack.isEmpty() && iStack.isEmpty()) { return true; } return false; } public int size() { return iStack.size() + oStack.size(); } }