双栈实现队列

使用两个栈，一个是pushStack, 另一个是pollStack;

1. 进队列规则

1. 观察pollStack是否为空，不空，则将元素移动到pushStack，保证顺序不乱
2. pollStack为空，则直接向pushStack中添加元素

2. 出队列规则

1. 观察pushStack是否为空，不空，则将元素全部移动到pollStack
2. pushStack为空，则直接出队或者查看头部元素

由于进入队列和出队列都全部移动了一个栈的元素，因此在入队与出队的过程中，保证了正确的顺序，入队出队的时间复杂度为O(n)

代码

class StackQueue {

    private Stack<Integer> pushStack;
    private Stack<Integer> pollStack;

    public StackQueue() {
        pushStack = new Stack<>();
        pollStack = new Stack<>();
    }


    public void add(int item) {
        if (pushStack.empty() && !pollStack.empty()) {
            while (!pollStack.empty()) {
                pushStack.push(pollStack.pop());
            }
        }
        pushStack.push(item);
    }

    public int poll() {
        if (pushStack.empty() && pollStack.empty()) {
            throw new RuntimeException("Queue is empty!");
        }
        if (pollStack.empty() && !pushStack.empty()){
            while(!pushStack.empty()) {
                pollStack.push(pushStack.pop());
            }
        }
        return pollStack.pop();
    }

    public int peek(){
        if (pushStack.empty() && pollStack.empty()) {
            throw new RuntimeException("Queue is empty!");
        }
        if (pollStack.empty() && !pushStack.empty()){
            while(!pushStack.empty()) {
                pollStack.push(pushStack.pop());
            }
        }
        return pollStack.peek();
    }
}