日常实践（四）：使用两个栈实现队列

标题：日常实践（四）：使用两个栈实现队列分类：[剑指offer]标签：[日常实践]日期：2022/01/17日常练习（四）：实现一个有两个栈的队列和实现一个有两个栈的队列。队列的声明如下，请实现它的两个函数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<=values<=10000将调用appendTail和deleteHead直到10000次来源：力扣（LeetCode）链接：https://leetcode-cn.com/probl...方法：一进二出算法过程：入栈：先进先出，后进先出队列：firstinfirstout,lastin出栈后，s1负责appendTail，stacks2负责deleteHead。对应的插入元素的方法是appendTailstack1。直接插入元素和删除元素对应的方法是deleteHead。如果stack2为空，则将stack1中的所有元素弹出并插入到stack2中。如果stack2仍然为空，则返回-1，否则，从stack2中弹出一个元素并返回它。复杂度分析时间复杂度：对于插入和删除操作，时间复杂度为O(1)。插入就不多说了，虽然删除操作看起来是O(n)的时间复杂度，但是仔细一想，每个元素只会“插入和弹出stack2最多一次”，所以每个元素的成本被删除平分。时间复杂度还是O(1)。空间复杂度：O(n)。需要使用两个栈来存储已有的元素。类CQueue{stackstack1,stack2;public:CQueue(){while(!stack1.empty()){stack1.opo();}while(!stack2.empty()){stack2.pop();}}voidappendTail(intvalue){stack1.push(value);}intdeleteHead(){//如果第二个栈为空if(stack2.empty()){while(!stack1.empty()){stack2.push(stack1.top());stack1.pop();}}if(stack2.empty()){返回-1;}else{intdeleteItem=stack2.top();stack2.pop();返回删除项；}}}/***你的CQueue对象将被实例化并调用：*CQueue*obj=newCQueue();*obj->appendTail(value);*intparam_2=obj->deleteHead();*/