当前位置:网站首页>一刷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
边栏推荐
- Pytorch中named_parameters、named_children、named_modules函数
- ICE -- 源码分析
- php函数
- Sword finger offer (2) -- for Huawei
- [backtrader source code analysis 18] Yahoo Py code comments and analysis (boring, interested in the code, you can refer to)
- Today's sleep quality record 76 points
- Go并发和通道
- cadence SPB17. 4 - Active Class and Subclass
- Sword finger offer (1) -- for Huawei
- Explanation 2 of redis database (redis high availability, persistence and performance management)
猜你喜欢
API gateway / API gateway (II) - use of Kong - load balancing
Mobile finance (for personal use)
Sorting and replying to questions related to transformer
Explanation 2 of redis database (redis high availability, persistence and performance management)
Mysql database explanation (10)
For examination
MultiTimer v2 重构版本 | 一款可无限扩展的软件定时器
WPS品牌再升级专注国内,另两款国产软件低调出国门,却遭禁令
激活函数的优缺点和选择
KNN, kmeans and GMM
随机推荐
Comparaison du menu de l'illustrateur Adobe en chinois et en anglais
php函数
What role does the software performance test report play? How much is the third-party test report charged?
控制结构(一)
adobe illustrator 菜单中英文对照
MySQL query library size
PHP PDO ODBC将一个文件夹的文件装载到MySQL数据库BLOB列,并将BLOB列下载到另一个文件夹
Node.js ODBC连接PostgreSQL
通过 PDO ODBC 将 PHP 连接到 MySQL
Use of common pod controller of kubernetes
Mysql database explanation (8)
今日睡眠质量记录76分
Precautions for use of dispatching system
【backtrader源码解析18】yahoo.py 代码注释及解析(枯燥,对代码感兴趣,可以参考)
Detailed explanation of redirection and request forwarding
Kubernetes详解(九)——资源配置清单创建Pod实战
自主作业智慧农场创新论坛
Nacos程序连接MySQL8.0+ NullPointerException
【Leetcode-每日一题】安装栅栏
基于 TiDB 的 Apache APISIX 高可用配置中心的最佳实践