# 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
For push(1), pop(), push(2), push(3), top(), pop(), you should return 1, 2 and 2

Challenge
implement it by two stacks, do not use any other data structure and push,
pop and top should be O(1) by AVERAGE.


## 题解

### Java

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

public Solution() {
// source stack
stack1 = new Stack<Integer>();
// target stack
stack2 = new Stack<Integer>();
}

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

public int pop() {
if (stack2.empty()) {
stack1ToStack2(stack1, stack2);
}
return stack2.pop();
}

public int top() {
if (stack2.empty()) {
stack1ToStack2(stack1, stack2);
}
return stack2.peek();
}

private void stack1ToStack2(Stack<Integer> stack1, Stack<Integer> stack2) {
while (!stack1.empty()) {
stack2.push(stack1.pop());
}
}
}