LeetCode简支Offer09.使用两个栈实现队列|liang-ge-zhan-shi-xian-dui-lie-lcoftitle用两个栈实现一个队列。队列的声明如下，请实现它的两个函数appendTail和deleteHead，分别完成在队尾插入一个整数和在队头删除一个整数的功能。（如果队列中没有元素，则deleteHead操作返回-1）示例1：输入：["CQueue","appendTail","deleteHead","deleteHead"][[],[3],[],[]]输出：[null,null,3,-1]示例2：输入：["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"][[],[],[5],[2],[],[]]output:[null,-1,null,null,5,2]prompt:1<=values<=10000会调用appendTail和deleteHeadupto10000次思路：栈题目要求我们用栈来实现队列，所以在开始之前，先说说栈和队列。栈的特点是先进后出，队列是先进先出。然后要实现队列，这里需要两个栈，其中一个（stack1）支持插入操作，另一个栈（stack2）支持删除操作。根据栈的先进后出特性，往stack1栈中插入元素，其中栈底元素相当于队列首元素，但是栈不能直接删除栈底元素。于是引入stack2栈，借助stack2实现倒序，则stack1底部的元素成为stack2的顶部元素。具体思路如下：初始化变量stack1和stack2，stack1支持插入操作，stack2支持删除操作。插入元素函数的实现：将元素插入stack1和删除元素的函数实现，这里分为以下几种情况：当stack1有元素（非空），stack2为空时，将stack1的元素放入stack2，实现倒序。返回stack2的顶部元素。当stack2不为空时，直接返回stack2的栈顶元素即可。当stack1和stack2都为空时，返回-1以例2为例：Input:["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"][[],[],[5],[2],[],[]]output:[null,-1,null,null,5,2]方法实现图如下：具体代码实现如下。代码实现类CQueue:def__init__(self):"""初始化stack1和stack2两个栈"""self.stack1=[]self.stack2=[]defappendTail(self,value:int)->None:"""Insertelement"""#Insertanelementintostack1self.stack1.append(value)defdeleteHead(self)->int:"""Deleteelement"""#这里根据情况处理#stack2为空,但stack1不为空,#把stack1的元素转移到stack2ifnotself.stack2:whileself.stack1:self.stack2.append(self.stack1.pop())#stack2有元素,直接返回栈顶元素ifself.stack2:del_ele=self.stack2.pop()returndel_ele#当stack1和stack2都为空时，返回-1return-1#你的CQueue对象将被实例化并这样调用：#obj=CQueue()#obj.appendTail(value)#param_2=obj.deleteHead()实现结果总结题中需要使用两个栈来辅助实现队列，因为根据characterist栈的ics，单个栈底元素相当于队列的首元素（且队列的特点是先进先出），栈不能直接删除栈底元素，因此需要引入第二个堆栈。具体设计思路：维护两个栈，stack1和stack2，初始化为空；stack1支持插入操作，stack2支持删除操作。插入函数的实现：直接向stack1插入元素；删除函数的实现分为以下几种情况：当stack2为空，stack1中有元素时，将stack1中的元素转移到stack2中。此时stack2的栈顶元素就相当于stack1的栈底元素（即队列首元素）。当stack2不为空时，直接返回栈顶元素；当stack1和stack2都为空时，直接返回-1。文章原创，欢迎关注和点赞。微信公众号《书所集录》同步更新，也欢迎大家关注。
