河南省建设招投标网站,手机笑话网站模板,建站全过程,微网站特点题目链接#xff1a;https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
1. 题目介绍#xff08;09. 用两个栈实现队列#xff09; 用两个栈实现一个队列。队列的声明如下#xff0c;请实现它的两个函数 appendTail 和 deleteHead #xff0c;分别…题目链接https://leetcode.cn/problems/yong-liang-ge-zhan-shi-xian-dui-lie-lcof/
1. 题目介绍09. 用两个栈实现队列 用两个栈实现一个队列。队列的声明如下请实现它的两个函数 appendTail 和 deleteHead 分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素deleteHead 操作返回 -1 ) 【测试用例】 对测试用例的解释说明 输入 [“CQueue”,“appendTail”,“deleteHead”,“deleteHead”] 这一行表示每一行代码的操作 [[],[3],[],[]] 这个表示每一行代码操作所需要的参数 举例 CQueue 表示新建一个CQueue对象对应的所需参数为[]即此操作不需要参数。 appendTail 表示执行一个appendTail()操作对应要被操作的元素为3。 deleteHead 表示执行一个deleteHead操作对应的所需参数为[]即此操作不需要参数。 deleteHead 表示执行一个deleteHead操作对应的所需参数为[]即此操作不需要参数。 以上的输入其实是一个代码执行的步骤描述与其对应所需参数。 即两个纬度 1、操作描述 2、此次操作所需参数 3、操作描述与操作所需参数是通过默认顺序一一对应的。 示例1 输入 [“CQueue”,“appendTail”,“deleteHead”,“deleteHead”,“deleteHead”] [[],[3],[],[],[]] 输出[null,null,3,-1,-1] 示例2 输入 [“CQueue”,“deleteHead”,“appendTail”,“appendTail”,“deleteHead”,“deleteHead”] [[],[],[5],[2],[],[]] 输出[null,-1,null,null,5,2] 【条件约束】 1 values 10000 最多会对 appendTail、deleteHead 进行 10000 次调用 2. 题解
相同题目【LeetCode】No.232. 用栈实现队列 – Java Version 相似题目【LeetCode】No.225. 用队列实现栈 – Java Version
2.1 用两个栈实现队列 – O(1)
时间复杂度O(1)空间复杂度O(n)
代码参考于 kd35 在 力扣官方题解用两个栈实现队列的Comment.
解题思路
class CQueue {//两个栈一个出栈一个入栈private StackInteger stack1;private StackInteger stack2;public CQueue() {stack1 new Stack();stack2 new Stack();}// 1. 尾添加入队先存Stack1public void appendTail(int value) {stack1.push(value);}// 2. 头删除出队走Stack2public int deleteHead() {// 3. stack2不为空直接弹出栈顶元素if(!stack2.isEmpty()){return stack2.pop();// 4. stack2为空将stack1中全部元素弹出并压入stack2}else{while(!stack1.isEmpty()){stack2.push(stack1.pop());}// 5. 最后判断stack2是否为空如果为空返回-1如果不为空弹出栈顶元素return stack2.isEmpty() ? -1 : stack2.pop();}}
}/*** Your CQueue object will be instantiated and called as such:* CQueue obj new CQueue();* obj.appendTail(value);* int param_2 obj.deleteHead();*/3. 参考资料
[1] 面试题09. 用两个栈实现队列清晰图解-- 解题思路来源 [2] 用两个栈实现队列力扣官方题解-- 代码来源 [3] 【JAVA】栈和队列Part2 队列-- 基础知识写的很好
