用两个队列实现一个栈算法思路流程
时间: 2023-06-26 19:03:59 浏览: 109
我们可以用两个队列来模拟一个栈的操作,具体算法思路如下:
1. 定义两个队列 queue1 和 queue2,其中 queue1 用来存储栈中的元素,queue2 用来作为辅助队列。
2. 入栈操作:将元素插入到 queue1 队列的末尾即可。
3. 出栈操作:先将 queue1 中的元素依次出队并插入到 queue2 中,直到 queue1 中只剩下一个元素,然后将该元素出队即可。最后再将 queue2 中的元素依次出队并插入到 queue1 中。
4. 取栈顶元素:类似出栈操作,只是最后不需要将元素出队,而是将其插入到 queue2 中再立即将其出队即可。
下面是实现代码:
```python
class Stack:
def __init__(self):
self.queue1 = []
self.queue2 = []
def push(self, val):
self.queue1.append(val)
def pop(self):
if not self.queue1:
return None
while len(self.queue1) > 1:
self.queue2.append(self.queue1.pop(0))
res = self.queue1.pop(0)
self.queue1, self.queue2 = self.queue2, self.queue1
return res
def top(self):
if not self.queue1:
return None
while len(self.queue1) > 1:
self.queue2.append(self.queue1.pop(0))
res = self.queue1[0]
self.queue2.append(self.queue1.pop(0))
self.queue1, self.queue2 = self.queue2, self.queue1
return res
```
这样,我们就可以使用两个队列来实现栈的操作了。
阅读全文