题目
栈和队列是常见的数据结构,栈的特点是 先进后出
,而队列的特点是 先进先出
。
请使用 栈 模拟实现队列的下列操作:
- push(x) -- 将元素 x 推到队列的末尾
- pop() -- 从队列的开头移除并返回元素
- peek() -- 返回队列开头的元素
- empty() -- 判断队列是否为空
说明:
- 可以用 列表list 来模拟栈,但只允许使用栈的基本操作。
- 假设每次调用 pop 和 peek 都能保证队列不为空。
实现思路1
- 使用两个栈,一个作为输入栈 stack1 ,另一个作为输出栈 stack2
- 每次 push 入队操作,直接把 待入队的新元素 入栈到 stack1 即可
- 每次 pop 出队操作,stack2的栈顶就相当于队列的队头,直接从 stack2 弹出栈顶元素即可,如果 stack2 为空,那么就把 stack1 的所有元素导入到 stack2 中,最后再从 stack2 弹出数据
- 每次 peek 获取队头元素操作,可以复用出队操作的实现,从而拿到队列开头的元素
- 每次 empty 操作,则需判断 stack1 和 stack2 是否都为空
代码实现1
class MyQueue:
def __init__(self):
self.stack1 = [] # 输入栈
self.stack2 = [] # 输出栈
def push(self, x):
self.stack1.append(x)
def pop(self):
if self.stack2 == []:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()
def peek(self):
tmp = self.pop()
self.stack2.append(tmp)
return tmp
def empty(self):
return self.stack1 == [] and self.stack2 == []
实现思路2
- 使用两个栈,一个作为辅助栈 stack1 ,另一个作为存放队列元素的栈 stack2
- 每次 push 入队操作,需先把 stack2 中全部元素导入到 stack1 ,接着把 待入队的新元素 入栈到 stack1 ,最后把 stack1 中全部元素导入到 stack2,这样一来,stack2的栈顶就相当于队列的队头
- 每次 pop 出队操作,直接从 stack2 弹出栈顶元素
- 每次 peek 获取队头元素操作,直接从 stack2 获取栈顶元素
- 每次 empty 操作,则只需判断 stack2 是否为空
代码实现2
class MyQueue:
def __init__(self):
self.stack1 = [] # 辅助栈
self.stack2 = [] # 存放队列元素
def push(self, x):
while self.stack2:
self.stack1.append(self.stack2.pop())
self.stack1.append(x)
while self.stack1:
self.stack2.append(self.stack1.pop())
def pop(self):
return self.stack2.pop()
def peek(self):
return self.stack2[-1]
def empty(self):
return self.stack2 == []