python中如何用队列来构建栈
时间: 2024-05-15 19:16:11 浏览: 14
可以使用两个队列来构建栈。具体实现方法如下:
1. 定义一个栈类,初始化时创建两个空队列。
2. 实现栈的push方法,将元素添加到其中一个队列中。
3. 实现栈的pop方法,先判断其中一个队列是否为空。若不为空,将队列中的元素依次出队并添加到另一个队列中,直到队列中只剩一个元素,然后将该元素出队即可。
4. 实现栈的top方法,先判断其中一个队列是否为空。若不为空,将队列中的元素依次出队并添加到另一个队列中,直到队列中只剩一个元素,然后将该元素出队并返回即可。
5. 实现栈的empty方法,判断两个队列是否都为空即可。
下面是代码示例:
```python
class MyStack:
def __init__(self):
self.queue1 = []
self.queue2 = []
def push(self, x: int) -> None:
self.queue1.append(x)
def pop(self) -> int:
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) -> int:
if not self.queue1:
return None
while len(self.queue1) > 1:
self.queue2.append(self.queue1.pop(0))
res = self.queue1.pop(0)
self.queue2.append(res)
self.queue1, self.queue2 = self.queue2, self.queue1
return res
def empty(self) -> bool:
return not self.queue1 and not self.queue2
```