# 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

```java
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](http://algs4.cs.princeton.edu/13stacks/QueueWithTwoStacks.java.html)