通过两个stack来实现Queue

题目

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.

正如标题所述，你只能使用两个栈来实现队列的一些操作。队列应支持push(element)，pop() 和 top()，其中pop是弹出队列中的第一个(最前面的)元素。pop和top方法都应该返回第一个元素的值。

题目解析

Stack是先进后出 First in Last Out
Queue 是先进先出 First in First Out

通过两个stack来回颠倒可以实现Queue结构

思路

两个stack
push入队 时候，即 添加元素，直接放入 stack1

pop时候，从stack2开始往出弹，如果stack2为空，则执行stack1全部放入stack2
然后，再从stack2往出弹。

top时候，直接执行stack。peek（） 查看stack2的顶端元素就可以了
如果stack2为空，就把stack1里面全部放入stack2，然后从stack2取peek

总结
入队时，将元素压入s1。

出队时，判断s2是否为空，如不为空，则直接弹出顶元素；

如为空，则将s1的元素逐个“倒入”s2，把最后一个元素弹出并出队。

代码

public class MyQueue {
    

    Stack<Integer> stack1;
    Stack<Integer> stack2;

    public MyQueue() {
    
        // do intialization if necessary
        stack1 = new Stack<>();
        stack2 = new Stack<>();
    }

    /* * @param element: An integer * @return: nothing */
    public void push(int element) {
    
        // write your code here
        stack1.push(element);
    }

    /* * @return: An integer */
    public int pop() {
    
        // write your code here
        if(!stack2.isEmpty()){
    
            return stack2.pop();
        }

        while(!stack1.isEmpty()){
    
            stack2.push(stack1.pop());
        }

        return stack2.pop();
    }

    /* * @return: An integer */
    public int top() {
    
        // write your code here
        if(!stack2.isEmpty()){
    
            return stack2.peek();
        }

        while( !stack1.isEmpty()){
    
            stack2.push(stack1.pop());
        }

        return stack2.peek();
    }
}

Reference

https://www.lintcode.com/problem/40/solution/18895
https://www.cnblogs.com/wanghui9072229/archive/2011/11/22/2259391.html