Implement Queue by Two Stacks

Question

As the title described, you should only use two stacks to implement a queue's actions.

The queue should support push(element), pop() and top() where pop is pop the first(a.k.a front) element in the queue.

Both pop and top methods should return the value of first element.

Example

push(1)
pop()     // return 1
push(2)
push(3)
top()     // return 2
pop()     // return 2

Analysis

用两个Stack来实现一个Queue，可以考虑到push()时，几乎与Queue中的offer()一样，都是加在末尾，区别是当Stack pop()时，取出的是最近加入（newest）的元素，而Queue用poll()则是将最老（oldest）的元素取出。使用2个Stack，可以将stack2作为push()时的目标，而另一个stack1用来翻转顺序，只有当peek()或者是poll()时，才需要将元素翻转存入stack1，再进行读取。

Solution

public class Queue {
    private Stack<Integer> stack1;
    private Stack<Integer> stack2;

    public Queue() {
        stack1 = new Stack<Integer>();
        stack2 = new Stack<Integer>();
    }

    private void switchStack() {
        while (!stack2.empty()) {
            stack1.push(stack2.pop());
        }
    }

    public void push(int element) {
        stack2.push(element);
    }

    public int pop() {
        if (stack1.empty()) {
            switchStack();
        }
        return stack1.pop();
    }

    public int top() {
        if (stack1.empty()) {
            switchStack();
        }
        return stack1.peek();
    }
}

Reference

• http://algs4.cs.princeton.edu/ QueueWithTwoStacks.java