剑指offer:用两个栈实现一个队列
题目描述
用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。
类似汉诺塔,当我们需要将栈A下面的元素出栈的时候可以先将栈A中的元素全部逆序压入到另一个栈B,这时栈B保存的就是栈A的逆序,也就是满足了FIFO的要求
class Solution: """ 用两个栈模拟一个队列,如果两个栈的容量分别为M和N,其中M > N,那么模拟得到的队列的容量是2N+1 因为假设先把stack2塞满N个,然后此时stack1塞进N+2个,那么此时将元素出队,当stack2的元素全 部出栈之后,将stack1的后N个元素压入stack2,此时stack1还有2个元素,且这两个元素是即将要出队 的两个元素,最先要出队的元素在下面,没办法按顺序出队,不满足队列的特性。因此最大容量是2N+1 """ def __init__(self): self.stack1 = [] # stack1用来保存进队的元素 self.stack2 = [] # stack2用来保存将要出队的元素 def push(self, node): self.stack1.append(node) def pop(self): if not self.stack1 and not self.stack2: return None if not self.stack2: # 当stack2为空的时候将stack1的元素逆序压入 while self.stack1: self.stack2.append(self.stack1.pop(-1)) return self.stack2.pop(-1)
声明:本站所有文章资源内容,如无特殊说明或标注,均为采集网络资源。如若本站内容侵犯了原著者的合法权益,可联系本站删除。