保留 2 个堆栈，我们称它们为inbox和outbox。

排队：

• 将新元素推送到inbox

出队：

• 如果outbox为空，则通过弹出每个元素inbox并将其推入来重新填充它outbox

• 弹出并返回顶部元素outbox

使用此方法，每个元素将在每个堆栈中恰好出现一次 - 这意味着每个元素将被压入两次并弹出两次，从而提供摊销的常数时间操作。

这是 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();
    }

}

A - 如何反转堆栈

要了解如何使用两个堆栈构造队列，您应该清楚地了解如何反转堆栈。记住堆叠的工作原理，它与厨房中的盘子堆叠非常相似。最后洗过的盘子将放在干净堆栈的顶部，这在计算机科学中称为后进先出（LIFO） 。

让我们想象一下我们的堆栈就像一个瓶子，如下所示；

如果我们分别压入整数 1,2,3，那么 3 就会在栈顶。因为 1 将首先被压入，然后 2 将被放在 1 的顶部。最后，3 将被放在堆栈的顶部，我们堆栈的最新状态表示为一个瓶子将如下所示；

Now we have our stack represented as a bottle is populated with values 3,2,1. And we want to reverse the stack so that the top element of the stack will be 1 and bottom element of the stack will be 3. What we can do ? We can take the bottle and hold it upside down so that all the values should reverse in order ?

Yes we can do that, but that's a bottle. To do the same process, we need to have a second stack that which is going to store the first stack elements in reverse order. Let's put our populated stack to the left and our new empty stack to the right. To reverse the order of the elements, we are going to pop each element from left stack, and push them to the right stack. You can see what happens as we do so on the image below;

So we know how to reverse a stack.

B - Using Two Stacks As A Queue

On previous part, I've explained how can we reverse the order of stack elements. This was important, because if we push and pop elements to the stack, the output will be exactly in reverse order of a queue. Thinking on an example, let's push the array of integers {1, 2, 3, 4, 5} to a stack. If we pop the elements and print them until the stack is empty, we will get the array in the reverse order of pushing order, which will be {5, 4, 3, 2, 1} Remember that for the same input, if we dequeue the queue until the queue is empty, the output will be {1, 2, 3, 4, 5}. So it is obvious that for the same input order of elements, output of the queue is exactly reverse of the output of a stack. As we know how to reverse a stack using an extra stack, we can construct a queue using two stacks.

Our queue model will consist of two stacks. One stack will be used for enqueue operation (stack #1 on the left, will be called as Input Stack), another stack will be used for the dequeue operation (stack #2 on the right, will be called as Output Stack). Check out the image below;

Our pseudo-code is as below;

Enqueue Operation

Push every input element to the Input Stack

Dequeue Operation

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

Let's enqueue the integers {1, 2, 3} respectively. Integers will be pushed on the Input Stack (Stack #1) which is located on the left;

Then what will happen if we execute a dequeue operation? Whenever a dequeue operation is executed, queue is going to check if the Output Stack is empty or not(see the pseudo-code above) If the Output Stack is empty, then the Input Stack is going to be extracted on the output so the elements of Input Stack will be reversed. Before returning a value, the state of the queue will be as below;

Check out the order of elements in the Output Stack (Stack #2). It's obvious that we can pop the elements from the Output Stack so that the output will be same as if we dequeued from a queue. Thus, if we execute two dequeue operations, first we will get {1, 2} respectively. Then element 3 will be the only element of the Output Stack, and the Input Stack will be empty. If we enqueue the elements 4 and 5, then the state of the queue will be as follows;

Now the Output Stack is not empty, and if we execute a dequeue operation, only 3 will be popped out from the Output Stack. Then the state will be seen as below;

同样，如果我们再执行两次出队操作，在第一次出队操作时，队列将检查输出堆栈是否为空，这是真的。然后将Input Stack的元素pop出来，压入Output Stack，直到Input Stack为空，此时Queue的状态如下；

很容易看出，两次出队操作的输出将是{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

您甚至可以仅使用一个堆栈来模拟队列。第二个（临时）堆栈可以通过对插入方法的递归调用的调用堆栈来模拟。

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

• 您需要将元素从一个堆栈转移到另一个临时堆栈，以反转它们的顺序。
• 然后将要插入的新元素压入临时堆栈
• 然后将元素传回原栈
• 新元素在栈底，最早的元素在栈顶（最先出栈）

仅使用一个 Stack 的 Queue 类如下所示：

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();
    }
}

但是，时间复杂度会更糟。一个好的队列实现在恒定时间内完成所有事情。

编辑

不知道为什么我的回答在这里被否决了。如果我们编程，我们关心时间复杂度，使用两个标准栈来做一个队列是低效的。这是一个非常有效和相关的观点。如果其他人觉得有必要对此投反对票，我很想知道为什么。

更详细一点：关于为什么使用两个堆栈比只使用一个队列更糟糕：如果你使用两个堆栈，并且有人在发件箱为空时调用 dequeue，你需要线性时间才能到达收件箱底部（如你所见在戴夫的代码中）。

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

使用堆栈实现队列的以下操作。

push(x) -- 将元素 x 推到队列的后面。

pop() -- 从队列前面移除元素。

peek() -- 获取前面的元素。

empty() -- 返回队列是否为空。

class MyQueue {

  Stack<Integer> input;
  Stack<Integer> output;

  /** Initialize your data structure here. */
  public MyQueue() {
    input = new Stack<Integer>();
    output = new Stack<Integer>();
  }

  /** Push element x to the back of queue. */
  public void push(int x) {
    input.push(x);
  }

  /** Removes the element from in front of queue and returns that element. */
  public int pop() {
    peek();
    return output.pop();
  }

  /** Get the front element. */
  public int peek() {
    if(output.isEmpty()) {
        while(!input.isEmpty()) {
            output.push(input.pop());
        }
    }
    return output.peek();
  }

  /** Returns whether the queue is empty. */
  public boolean empty() {
    return input.isEmpty() && output.isEmpty();
  }
}

c#中的一个解决方案

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();
    }
}

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

入队： 入队的元素总是被压入stack1

Dequeue：当stack2不为空时， stack2 的栈顶是最先插入队列的元素，可以弹出栈顶。当stack2为空时，我们将stack1中的所有元素弹出，然后将它们一个一个地压入stack2 。队列中的第一个元素被推入stack1的底部。因为它在stack2的顶部，所以可以在 pop 和 push 操作后直接弹出。

以下是相同的 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;
}

这个解决方案是从我的博客中借来的。在我的博客网页上可以找到更详细的分步操作模拟分析。