【LeetCode】No.225. 用队列实现栈 -- Java Version

题目链接：https://leetcode.cn/problems/implement-stack-using-queues/

1. 题目介绍（225. 用队列实现栈）

请你仅使用两个队列实现一个后入先出（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（双端队列）来模拟一个队列 , 只要是标准的队列操作即可。

【测试用例】：
示例：

输入：
[“MyStack”, “push”, “push”, “top”, “pop”, “empty”]
[[], [1], [2], [], [], []]
输出：
[null, null, null, 2, 2, false]

解释：
MyStack myStack = new MyStack();
myStack.push(1);
myStack.push(2);
myStack.top(); // 返回 2
myStack.pop(); // 返回 2
myStack.empty(); // 返回 False

【条件约束】：

提示：

• 1 <= x <= 9
• 最多调用100 次 push、pop、top 和 empty
• 每次调用 pop 和 top 都保证栈不为空

【跟踪】：

进阶：你能否仅用一个队列来实现栈。

2. 题解

2.1 两个队列实现栈 – O(n)

时间复杂度O(n)，空间复杂度O(n)

class MyStack {// 1. 定义两个队列对象private Queue<Integer> queue1;private Queue<Integer> queue2;// 2. 定义一个变量，用于记录当前的queue元素长度private int curSize = 0;// 3. 构造方法，创建队列对象public MyStack() {queue1 = new LinkedList<>();queue2 = new LinkedList<>();}// 4. 入栈方法，如果哪个队列有值先添加到哪个，默认添加queue1public void push(int x) {if (!queue1.isEmpty()) queue1.offer(x);else if (!queue2.isEmpty()) queue2.offer(x);else queue1.offer(x);}// 5. 出栈方法public int pop() {// 判空if (empty()) return -1;// 至少有一个非空// 当queue1非空时，将queue1中size-1的元素出队存入queue2// 循环结束，queue1中只剩下一个元素，即栈顶元素（最后添加的元素）if (!queue1.isEmpty()){curSize = queue1.size();for (int i = 0; i < curSize-1; i++){queue2.offer(queue1.poll());}return queue1.poll();// queue1为空，说明queue2非空，步骤基本同上}else {curSize = queue2.size();for (int i = 0; i < curSize-1; i++){queue1.offer(queue2.poll());}return queue2.poll();}}// 6. 返回栈顶方法public int top() {// 定义一个临时值变量，用于记录queue出队值int ret = -1;// 判空if (empty()) return -1;// 至少有一个非空// 当queue1非空时，将queue1中所有的元素出队存入queue2// 同时通过临时值变量ret记录出队值，循环结束返回ret，即为栈顶元素if (!queue1.isEmpty()){curSize = queue1.size();for (int i = 0; i < curSize; i++){//System.out.println(queue1.size());ret = queue1.poll(); queue2.offer(ret);}System.out.println(ret);return ret;// queue1为空，说明queue2非空，步骤基本同上}else {curSize = queue2.size();for (int i = 0; i < curSize; i++){ret = queue2.poll(); queue1.offer(ret);}return ret;}}// 判空方法，queue1与queue2全为空，则为空public boolean empty() {return queue1.isEmpty() && queue2.isEmpty();}
}/*** Your MyStack object will be instantiated and called as such:* MyStack obj = new MyStack();* obj.push(x);* int param_2 = obj.pop();* int param_3 = obj.top();* boolean param_4 = obj.empty();*/

改进：（官方题解）

这里的改进点在于：push方法的巧妙设置，数据首先会存入queue2，并检查queue1是否为空，如果不为空，则将queue1中的元素全部出队，并存入queue2；然后借助临时变量交换queue1和queue2，保证每次push方法后，queue2始终为空，queue1为真正的栈结构，做到后进先出。

class MyStack {Queue<Integer> queue1;Queue<Integer> queue2;/** Initialize your data structure here. */public MyStack() {queue1 = new LinkedList<Integer>();queue2 = new LinkedList<Integer>();}/** Push element x onto stack. */public void push(int x) {queue2.offer(x);while (!queue1.isEmpty()) {queue2.offer(queue1.poll());}Queue<Integer> temp = queue1;queue1 = queue2;queue2 = temp;}/** Removes the element on top of the stack and returns that element. */public int pop() {return queue1.poll();}/** Get the top element. */public int top() {return queue1.peek();}/** Returns whether the stack is empty. */public boolean empty() {return queue1.isEmpty();}
}

2.2 一个队列实现栈 – O(n)

时间复杂度O(n)，空间复杂度O(n)

核心方法：当有新元素加入时，将原来的元素依次出队并重新入队，让队列中的元素始终保持倒序的状态。

class MyStack {Queue<Integer> queue;/** Initialize your data structure here. */public MyStack() {queue = new LinkedList<Integer>();}/** Push element x onto stack. */public void push(int x) {int n = queue.size();queue.offer(x);for (int i = 0; i < n; i++) {queue.offer(queue.poll());}}/** Removes the element on top of the stack and returns that element. */public int pop() {return queue.poll();}/** Get the top element. */public int top() {return queue.peek();}/** Returns whether the stack is empty. */public boolean empty() {return queue.isEmpty();}
}

3. 参考资料

[1] 用队列实现栈（官方题解）-- 部分代码来源
[2] 【LeetCode】No.232. 用栈实现队列 – Java Version（相似题目）
[3] 【LeetCode】剑指 Offer 09. 用两个栈实现队列 p68 – Java Version（相似题目）