Leetcode 225. 用队列实现栈

力扣传送门(opens new window)

请你仅使用两个队列实现一个后入先出（LIFO）的栈，并支持普通栈的全部四种操作（push、top、pop 和 empty）。

实现 MyStack 类：

• void push(int x) 将元素 x 压入栈顶。
• int pop() 移除并返回栈顶元素。
• int top() 返回栈顶元素。
• boolean empty() 如果栈是空的，返回 true ；否则，返回 false 。

注意：

• 你只能使用队列的标准操作 —— 也就是 push to back、peek/pop from front、size 和 is empty 这些操作。
• 你所使用的语言也许不支持队列。 你可以使用 list （列表）或者 deque（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

解题思路：

当使用两个队列实现栈时，主要的思路是在 push 操作中将新元素放在队列的头部，以实现后入先出（LIFO）的特性。以下是详细的解题思路：

1. 定义两个队列 queue1 和 queue2，其中 queue1 是主队列用于存储栈中的元素，queue2 是辅助队列用于在 push 操作中临时存储元素。
2. 在构造函数 MyStack() 中，初始化两个队列，即 queue1 和 queue2。
3. 在 push 操作中，首先将 queue1 中的所有元素移到 queue2，以保证新元素可以添加到队列的头部。然后将新元素 x 添加到 queue1。最后，将 queue2 中的所有元素移回 queue1，确保栈中的元素顺序不变。
4. 在 pop 操作中，直接从 queue1 中移除并返回头部元素，即栈顶元素。
5. 在 top 操作中，返回 queue1 的头部元素，即栈顶元素。
6. 在 empty 操作中，判断 queue1 和 queue2 是否都为空。如果两个队列都为空，说明栈中没有元素，返回 true；否则，返回 false。

代码实现：

class MyStack {
    // 主队列，用于存储栈中的元素
    Deque<Integer> queue1; 
    // 辅助队列，用于在 push 操作中临时存储元素
    Deque<Integer> queue2; 

    public MyStack() {
        queue1 = new LinkedList();
        queue2 = new LinkedList();
    }

    public void push(int x) {
        while (!queue1.isEmpty()) {
            // 将 queue1 中的元素移到 queue2
            queue2.add(queue1.poll()); 
        } 
        // 将新元素添加到 queue1
        queue1.add(x); 
        while (!queue2.isEmpty()) {
            // 将 queue2 中的元素移到 queue1
            queue1.add(queue2.poll()); 
        }
    }

    public int pop() {
        // 直接从 queue1 中移除并返回栈顶元素
        return queue1.poll(); 
    }

    public int top() {
        // 返回 queue1 的头部元素，即栈顶元素
        return queue1.peek(); 
    }

    public boolean empty() {
        // 判断栈是否为空
        return queue1.isEmpty() && queue2.isEmpty(); 
    }
}