题目描述:
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int
类型。
解法:
队列是先进先出,后进后出,而栈是先进后出,后进先出。
用两个栈stack1
和stack2
。
(1)Push操作:直接在stack1
的最后添加元素;
(2)Pop操作:如果stack2
非空,直接pop;如果stack2
为空,则先将栈stack1
的元素都pop到stack2
中,stack2
再pop。
上述pop操作指的是堆栈的pop操作。这种方法可以保证stack2
的栈顶元素是队列的底部元素。
代码:
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
self.stack1.append(node)
def pop(self):
if self.stack2:
return self.stack2.pop()
else:
while self.stack1:
self.stack2.append(self.stack1.pop())
return self.stack2.pop()