请你仅使用两个栈实现先入先出队列。队列应当支持一般队列支持的所有操作(push
、pop
、peek
、empty
):
python中数组的pop默认是针对数组中的最后一个元素,数组的pop就是栈的pop操作
class MyQueue(object):
# 使用两个栈进行模拟队列
def __init__(self):
self.stack_in = [] # 输入栈
self.stack_out = [] # 输出栈
def push(self, x):
"""
:type x: int
:rtype: None
"""
self.stack_in.append(x)
def pop(self):
"""
:rtype: int
"""
# 数组的pop默认是针对数组中的最后一个元素,数组的pop就是栈的pop操作
# 当输出栈空时,将输入栈的元素全部先pop弹出,再用数组的append压入stack_out,
# pop弹出的是最后进入stack_in的元素,append压入后为变为数组的第一个元素,再用pop弹出时是最后被弹出
# 所以stack_in中的第一个进入的元素,进入stack_out后为最后一个元素,pop弹出时为第一个
if self.stack_out:
return self.stack_out.pop()
else:
for i in range(len(self.stack_in)):
self.stack_out.append(self.stack_in.pop())
return self.stack_out.pop()
def peek(self):
"""
:rtype: int
"""
# 返回队列开头的元素
# 利用刚实现的pop操作
# pop会删除元素,
res = self.pop()
# 假设连续调用两次peek,队列开头的元素就变了,因为上一个开头被pop删除,也会影响其他操作
# 将刚被pop的元素加入stack_out,首先不会影响队列的pop操作,
# 其次,下次调用peek之前还会调用pop操作,pop会先弹stack_out的元素,此时stack_out中元素还是开头
self.stack_out.append(res)
return res
def empty(self):
"""
:rtype: bool
"""
# 当输出栈和输入栈同时为空才为空
if self.stack_in or self.stack_out:
return False
else:
return True
# Your MyQueue object will be instantiated and called as such:
# obj = MyQueue()
# obj.push(x)
# param_2 = obj.pop()
# param_3 = obj.peek()
# param_4 = obj.empty()