难度:简单
知识点:栈
题目描述:
用两个栈来实现一个队列,分别完成在队列尾部插入整数(push)和在队列头部删除整数(pop)的功能。 队列中的元素为int类型。保证操作合法,即保证pop操作时队列内已有元素。解题思路:
栈是先进后出,队列是先进先出。
所以,要想实现先进先出,则需要两个栈,从栈顶至栈底,依次把元素挪入另一个栈,此时原栈顶变为栈底,原栈底变为栈顶,再对第二个栈进行存取,也就相当于实现了队列的先进先出功能。
class Solution: def __init__(self): self.acceptStack = [] self.outputStack = [] def push(self, node): self.acceptStack.append(node) # write code here def pop(self): if not self.outputStack: # A中包含元素,B中包含元素,此时需要逐个转移 while self.acceptStack: self.outputStack.append(self.acceptStack.pop()) if self.outputStack: # 判断,不为空的时候,返回 return self.outputStack.pop() else: # A、B中都不包含元素 return None # return xx
时间复杂度和空间复杂度都是O(n)