大家好呀，我是蛋蛋。
今天解决用队列实现栈这道题，和用栈实现队列一样是考察对”栈和队列理解程度“的好题。
但是用队列实现栈，和用栈实现队列是两种不同的移动思路。
这种题都是为了考察而考察，没啥工程意义，实际工作中要是有人敢让你这么做，不要说话，先给他一 jue。
话不多说，直接开整。
LeetCode 232：用栈实现队列
题意
用队列实现栈的下列操作：
void push(int x)：元素 x 入栈。
int pop()：移除并返回栈顶元素。
int peek()：返回栈顶元素。
boolean empty()：栈为空，返回 true，否则返回 false。
示例
提示
- 1 <= x <= 9
- 最多调用 100 次 push、pop、top 和 empty
- 每次调用 pop 和 top 都保证栈不为空
题目解析
水题，难度简单，主要还是考察对栈和队列的理解能力。
如果对栈和队列还不熟悉，看一下本帅比写的这篇文章：
和栈实现队列相仿，用队列实现栈也涉及 4 步操作：
- 入栈 push
- 出栈 pop
- 取栈顶元素 peek
- 判空 empty
知道了需求，下面就是如何用队列模拟栈。
这里有两种方法：
- 两个队列模拟。
- 一个队列模拟。
两个队列模拟
建一个主队列和一个辅助队列，每次入栈操作时，将新元素添加到辅助队列，再依次将主队列的元素出队列，依次加入辅助队列，最后将主队列与辅助队列互换。
一个队列模拟
建一个主队列，其余操作正常，只是在每次模拟栈弹出元素的时候，将除了最后一个元素外的之前元素弹出队列，重新添加到主队列尾部即可。
图解
为了照顾大多数臭宝，我用两个队列来模拟，笨笨的方法更直观一些。
首先初始化主队列和辅助队列。
def __init__(self): self.major_queue = [] self.help_queue = []
push(x)，入栈操作，先压入辅助队列，再将主队列的元素加入辅助队列，再互换主队列和辅助队列。
首先 push(1)：
再 push(2)：
def push(self, x: int) -> None: # 新元素放入辅助队列的队首 self.help_queue.append(x) # 将主队列的元素加入辅助队列 while self.major_queue: self.help_queue.append(self.major_queue.pop(0)) # 现在辅助队列元素是和栈的元素排列一致，为了后续方便理解，交换两个队列的内容 self.major_queue = self.help_queue self.help_queue = []
入栈需要将所有的元素都倒腾一遍，所以入栈的时间复杂度为 O(n)，因为需要额外的队列存储栈内的元素，所以入栈的空间复杂度为 O(n)。
pop()，出栈操作，出栈出的是栈顶元素，由上图可以看出，栈顶元素即主队列的队首元素。
def pop(self) -> int: # 判断是否为空 if self.empty(): return None # pop移除栈顶元素，相当于移除主队列的队首元素 return self.major_queue.pop(0)
出栈对应的是将主队列的队首元素出栈，所以时间复杂度是 O(1)，空间复杂度为 O(n)。
top()，获取栈顶元素，与 pop 类似，即相当于获取主队列的队首元素。
def top(self) -> int: # top获取栈顶元素，即获取主队列的队首元素 return self.major_queue[0]
同样，获取栈顶元素是获取主队列的首元素，所以时间复杂度为 O(1)，空间复杂度为 O(n)。
empty()，判断栈是否为空。其实就是看主队列是否为空，主队列为空，栈就空，主队列不为空，栈不为空。
def empty(self) -> bool: # 只需要判断主队列是否为空 if not self.major_queue: return True return False
对于判空，只需要判断主队列是否为空，所以时间复杂度为 O(1)，空间复杂度为 O(n)。
代码实现
Python 代码实现
class MyStack: def __init__(self): """ Initialize your data structure here. """ # 初始化主队列和辅助队列 self.major_queue = [] self.help_queue = [] def push(self, x: int) -> None: """ Push element x onto stack. """ # 新元素放入辅助队列的队首 self.help_queue.append(x) # 将主队列的元素加入辅助队列 while self.major_queue: self.help_queue.append(self.major_queue.pop(0)) # 现在辅助队列元素是和栈的元素排列一致，为了后续方便理解，交换两个队列的内容 self.major_queue = self.help_queue self.help_queue = [] def pop(self) -> int: """ Removes the element on top of the stack and returns that element. """ # 判断是否为空 if self.empty(): return None # pop移除栈顶元素，相当于移除主队列的队首元素 return self.major_queue.pop(0) def top(self) -> int: """ Get the top element. """ # top获取栈顶元素，即获取主队列的队首元素 return self.major_queue[0] def empty(self) -> bool: """ Returns whether the stack is empty. """ # 只需要判断主队列是否为空 if not self.major_queue: return True return False # Your MyStack object will be instantiated and called as such: # obj = MyStack() # obj.push(x) # param_2 = obj.pop() # param_3 = obj.top() # param_4 = obj.empty()
Java 代码实现
class MyStack { Queue<Integer> queue1; // 和栈中保持一样元素的队列 Queue<Integer> queue2; // 辅助队列 /** Initialize your data structure here. */ public MyStack() { queue1 = new LinkedList<>(); queue2 = new LinkedList<>(); } /** Push element x onto stack. */ public void push(int x) { queue2.offer(x); // 先放在辅助队列中 while (!queue1.isEmpty()){ queue2.offer(queue1.poll()); } Queue<Integer> queueTemp; queueTemp = queue1; queue1 = queue2; queue2 = queueTemp; // 最后交换queue1和queue2，将元素都放到queue1中 } /** Removes the element on top of the stack and returns that element. */ public int pop() { return queue1.poll(); // 因为queue1中的元素和栈中的保持一致，所以这个和下面两个的操作只看queue1即可 } /** Get the top element. */ public int top() { return queue1.peek(); } /** Returns whether the stack is empty. */ public boolean empty() { return queue1.isEmpty(); } }
图解队列实现栈到这就结束啦，是不是觉得小菜一碟？
别飘，这只是简单题，后面题解继续。
如果有问题的话，直接评论区见呀，动动小手，给我你的点赞在看么么哒。
我是帅蛋，我们下次见！
