当前位置:网站首页>一刷314-剑指 Offer 09. 用两个栈实现队列(e)
一刷314-剑指 Offer 09. 用两个栈实现队列(e)
2022-04-23 15:35:00 【丿唐宋】
题目:
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail 和 deleteHead ,
分别完成在队列尾部插入整数和在队列头部删除整数的功能。
(若队列中没有元素,deleteHead 操作返回 -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 次调用
----------------
思路:
解题思路:
栈无法实现队列功能: 栈底元素(对应队首元素)无法直接删除,需要将上方所有元素出栈。
双栈可实现列表倒序: 设有含三个元素的栈 A = [1,2,3]和空栈 B = []
若循环执行 A 元素出栈并添加入栈 B ,直到栈 A 为空,则 A = []B = [3,2,1],
即 栈 B 元素实现栈 A 元素倒序 。
利用栈 B 删除队首元素: 倒序后,B 执行出栈则相当于删除了 A 的栈底元素,即对应队首元素。
函数设计:
题目只要求实现 加入队尾appendTail() 和 删除队首deleteHead() 两个函数的正常工作,
因此我们可以设计栈 A 用于加入队尾操作,栈 B 用于将元素倒序,从而实现删除队首元素。
加入队尾 appendTail()函数: 将数字 val 加入栈 A 即可。
删除队首deleteHead()函数: 有以下三种情况。
当栈 B 不为空: B中仍有已完成倒序的元素,因此直接返回 B 的栈顶元素。
否则,当 A 为空: 即两个栈都为空,无元素,因此返回 -1。
否则: 将栈 A 元素全部转移至栈 B 中,实现元素倒序,并返回栈 B 的栈顶元素。
-----------
复杂度分析:
由于问题特殊,以下分析仅满足添加 N 个元素并删除 N 个元素,即栈初始和结束状态下都为空的情况。
时间复杂度: appendTail()函数为 O(1);deleteHead()
函数在 N 次队首元素删除操作中总共需完成 N 个元素的倒序。
空间复杂度 O(N): 最差情况下,栈 A 和 B 共保存N个元素。
---------------------
class CQueue {
//A 用来添加 B 用来删除 B是A的倒序
LinkedList<Integer> A, B;//定义两个栈
public CQueue() {
//初始化
A = new LinkedList<Integer>();
B = new LinkedList<Integer>();
}
public void appendTail(int value) {
//A的末端添加元素
A.addLast(value);
}
public int deleteHead() {
if (!B.isEmpty()) return B.removeLast();//特判
if (A.isEmpty()) return -1;//特判
while (!A.isEmpty()) {
//B为空 A不为空, 先让B获得A的元素
B.addLast(A.removeLast());
}
return B.removeLast();
}
}
注: return B.removeLast(); 要作为返回值
/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */
版权声明
本文为[丿唐宋]所创,转载请带上原文链接,感谢
https://blog.csdn.net/m0_45170946/article/details/124363467
边栏推荐
- Cookie&Session
- 推荐搜索 常用评价指标
- Basic concepts of website construction and management
- MySQL sync could not find first log file name in binary log index file error
- How to design a good API interface?
- 通过 PDO ODBC 将 PHP 连接到 MSSQL
- Mysql连接查询详解
- Independent operation smart farm Innovation Forum
- Differential privacy (background)
- SSH connects to the remote host through the springboard machine
猜你喜欢
JVM-第2章-类加载子系统(Class Loader Subsystem)
[leetcode daily question] install fence
Openstack command operation
My raspberry PI zero 2W toss notes to record some problems and solutions
Mysql database explanation (10)
【Leetcode-每日一题】安装栅栏
Byte interview programming question: the minimum number of K
API gateway / API gateway (II) - use of Kong - load balancing
T2 iCloud日历无法同步
pgpool-II 4.3 中文手册 - 入门教程
随机推荐
推荐搜索 常用评价指标
控制结构(一)
Openstack command operation
kubernetes之常用Pod控制器的使用
函数(第一部分)
Go语言条件,循环,函数
MySQL InnoDB transaction
Explanation of redis database (III) redis data type
控制结构(二)
Independent operation smart farm Innovation Forum
木木一路走好呀
Adobe Illustrator menu in Chinese and English
软件性能测试报告起着什么作用?第三方测试报告如何收费?
HJ31 单词倒排
Baidu written test 2022.4.12 + programming topic: simple integer problem
Demonstration meeting on startup and implementation scheme of swarm intelligence autonomous operation smart farm project
Pytorch中named_parameters、named_children、named_modules函数
MySQL installation process (steps for successful installation)
For examination
今日睡眠质量记录76分