代码随想录刷题-栈与队列-用队列实现栈

用队列实现栈

本节对应代码随想录中：代码随想录，对应视频链接为：队列的基本操作！ | LeetCode：225. 用队列实现栈_哔哩哔哩_bilibili

习题

题目链接：225. 用队列实现栈 - 力扣（LeetCode）

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

实现 MyStack 类：

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

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

两个队列

我们知道队列是先进先出的，如1 2 3的进入顺序，那出去的时候也是1 2 3。而栈的出去顺序则相反为3 2 1。

直观上可以用两个队列来实现一个栈。队列出去的是第一个元素，而栈出去的是最后一个元素。那么可以在 push 的时候将元素先 push 到第二个队列，然后将第一个队列中的全部元素 push 到队列2中。这样新进来的元素每次就放在了队列的前面，pop 的时候可以直接 pop 就是弹的最后一个进来的元素。最后，再将队列1和队列2交换，保持队列1存放所有元素，队列2只是在 push 的时候临时存放元素

以上思路是 LeetCode 官方的解法，在 push 的时候用到了第二个队列
代码随想录中是 pop 的时候，用到第二个队列，两种方法均可实现

class MyStack {private:queue<int> q1;queue<int> q2;public:MyStack() {}void push(int x) {// 先将元素放入q2q2.push(x);// 把q1的元素都移到q2里面while (!q1.empty()) {q2.push(q1.front());q1.pop();}// 交换q1和q2，这样新进来的元素就在q1的开头位置swap(q1, q2);}int pop() {int res = q1.front();q1.pop();return res;}int top() { return q1.front(); }bool empty() { return q1.empty(); }
};

• 时间复杂度：push 是 O($n$)，其余都是 O(1)，其中 n 是栈内的元素个数
• 空间复杂度：O($n$)。需要使用两个队列存储栈内的元素，其中 n 是栈内的元素个数

一个队列

上面用两个队列主要是解决如何弹出队列中最后一个元素的问题，用到了第二个队列作为临时储存元素的地方。

而我们可以使用一个队列，在 push 元素后，将 push 前所有元素依次弹出再重新 push 到队列中。如原队列为3 2 1，将要 push 元素4。push 后变为3 2 1 4，然后将原来的3个元素依次 pop 再 push 后就变为 4 3 2 1。这样新进来的元素4就变成了队头，就实现了栈的后进先出。和上面的解法只有 push 的时候操作不同。

class MyStack {private:queue<int> q1;public:MyStack() {}void push(int x) {int size = q1.size();q1.push(x);for (int i = 0; i < size; i++){q1.push(q1.front());q1.pop();}}int pop() {int res = q1.front();q1.pop();return res;}int top() { return q1.front(); }bool empty() { return q1.empty(); }
};

• 时间复杂度：push 是 O($n$)，其余都是 O(1)，其中 n 是栈内的元素个数
• 空间复杂度：O($n$)。需要使用一个队列存储栈内的元素，其中 n 是栈内的元素个数