top_interview

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）
题解来源于https://leetcode.cn/problems/implement-stack-using-queues/solutions/2664345/python3javacgo-yi-ti-yi-jie-liang-ge-dui-lt48
方法一：两个队列
我们使用两个队列1和2，其中q1用于存储栈中的元素，而q2用于辅助实现栈的操作。
push 操作：将元素压入q2，然后将q1中的元素依次弹出并压入q2，最后交换q1和q2的引用。时间复杂度O(m)。
pop 操作：直接弹出的队首元素。时间复杂度O(1)。
top操作：直接返回qh的队首元素。时间复杂度O(1)。
empty操作：判断q1是否为空。时间复杂度O(1)。
空间复杂度O(),其中n是栈中元素的个数。
```java
import java.util.Deque;

class MyStack {
    private Deque<Integer> q1 = new ArrayDeque<>();
    private Deque<Integer> q2 = new ArrayDeque<>();

    public MyStack() {
    }

    public void push(int x) {
        q2.offer(x);
        while (!q1.isEmpty()) {
            q2.offer(q1.poll());
        }
        Deque<Integer> q = q1;
        q1 = q2;
        q2 = q;
    }

    public int pop() {
        return q1.poll();
    }

    public int top() {
        return q1.peek();
    }

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