题解 | #两个队列实现栈#

先进先出，变先进后出。两个队列，

• push时，push到q1
• pop时，先将q1的元素转移到q2中，最终q1只剩一个元素，长度为1，此时即为最后push进来的，后进先出
• pop完成后，需要交换q1和q2，方便下次pop
• push操作始终在q1

public class MyStack {
    // 进行push操作
    Queue<Integer> q1 = new LinkedList<>();
    // 进行pop操作时，存储之前的值
    Queue<Integer> q2 = new LinkedList<>();

    public void push(int node) {
        q1.add(node);
    }

    public int pop() {
        while (q1.size() > 1) {
            q2.add(q1.poll());
        }

        // 交换q1和q2
        Queue<Integer> tmp = q1;
        q1 = q2;
        q2 = tmp;

        return q2.poll();
    }

    public int top(){
        while (q1.size() > 1) {
            q2.add(q1.poll());
        }
        int res = q1.peek();

        // 最后一个也放进去q2，然后交换q1和q2
        q2.add(q1.poll());

        // 交换q1和q2
        Queue<Integer> tmp = q1;
        q1 = q2;
        q2 = tmp;

        return res;
    }

    public boolean empty() {
        return q1.isEmpty() && q2.isEmpty();
    }
}