剑指 Offer 09. 用两个栈实现队列

用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )

示例 1：

输入： ["CQueue","appendTail","deleteHead","deleteHead"] [[],[3],[],[]] 输出：[null,null,3,-1]

示例 2：

输入： ["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"] [[],[],[5],[2],[],[]] 输出：[null,-1,null,null,5,2]

1、题目分析

这个题目比较清晰明了，就是用两个栈模仿队列，那么栈的特点就是先进后出，队列的特点是先进先出，因此需要用两个栈来模仿队列的出入。

2、解题分析

基本思路就是用一个栈入队，另一个栈用来出队。加入有两个栈：stack1，stack2：只用stack1进行入队操作，等出队操作的时候我们把stack1栈中的元素都一一弹出然后再压入到stack2栈中，然后再执行stack2的出栈操作，stack1先弹出来入stack2的元素就是stack1最后入栈的元素，那么我们把这个元素放到栈底了，可不就实现了后进后出嘛，先进先出嘛。因此两个栈实现队列的大致思想就是这样。

声明两个栈stack1，stack2使用stack1进行入栈操作，stack2进行出栈操作进行出栈 如果stack2为空，判断stack1 stack1为空直接返回-1，因为入栈都是空的，都没进哪来的出那stack1不为空，将stack1出栈的元素全部压入stack2中，然后再出栈就很流畅了如果不为空直接出栈就完事了

3、代码

class CQueue: def __init__(self): self.stack1 = [] self.stack2 = [] #入队 def appendTail(self, value: int) -> None: self.stack1.append(value) #出队 def deleteHead(self) -> int: if not self.stack2: if not self.stack1: return -1 else: while self.stack1: self.stack2.append(self.stack1.pop()) return self.stack2.pop() else: return self.stack2.pop() # Your CQueue object will be instantiated and called as such: # obj = CQueue() # obj.appendTail(value) # param_2 = obj.deleteHead()

4、画图说明

总结：两个栈模仿一个队列，必须要清楚队列和栈的各自特点。