当前位置:网站首页>One brush 314 sword finger offer 09 Implement queue (E) with two stacks
One brush 314 sword finger offer 09 Implement queue (E) with two stacks
2022-04-23 15:40:00 【Tang and Song Dynasties】
subject :
Use two stacks to implement a queue . The declaration of the queue is as follows , Please implement its two functions appendTail and deleteHead ,
The functions of inserting integers at the end of the queue and deleting integers at the head of the queue are respectively completed .
( If there are no elements in the queue ,deleteHead Operation return -1 )
-----------------
Example :
Input :
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
Output :[null,null,3,-1]
Example 2:
Input :
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
Output :[null,-1,null,null,5,2]
Tips :
1 <= values <= 10000
At most appendTail、deleteHead Conduct 10000 Secondary call
----------------
Ideas :
Their thinking :
The stack cannot implement the queue function : Stack bottom element ( Corresponding to the first element of the team ) Can't delete directly , All the elements above need to be out of the stack .
Double stack can realize the reverse order of the list : There is a stack with three elements A = [1,2,3] Empty stack B = []
If the loop executes A Element out of the stack and added into the stack B , Until the stack A It's empty , be A = []B = [3,2,1],
namely Stack B Element implementation stack A Elements in reverse order .
Utilization stack B Delete team leader element : In reverse order ,B Executing out of the stack is equivalent to deleting A At the bottom of the stack , That is, the corresponding team head element .
Function design :
The title only requires the realization of To join a party appendTail() and Delete team leader deleteHead() The normal operation of the two functions ,
So we can design the stack A Used to join the end of the queue , Stack B Used to reverse the order of elements , So as to delete the team head element .
To join a party appendTail() function : The digital val Join the stack A that will do .
Delete team leader deleteHead() function : There are three situations .
Stack B Not empty : B There are still elements in reverse order , So go straight back B Top element of .
otherwise , When A It's empty : That is, both stacks are empty , Element free , Therefore return -1.
otherwise : Stack A All elements are transferred to the stack B in , Implement elements in reverse order , And return to the stack B Top element of .
-----------
Complexity analysis :
Because of the special problem , The following analysis only meets the requirements of adding N And delete N Elements , That is, the stack is empty in the initial and end states .
Time complexity : appendTail() Function is O(1);deleteHead()
Function in N A total of... Needs to be completed in the deletion of the first element of the team N The reverse order of the elements .
Spatial complexity O(N): In the worst case , Stack A and B Keep together N Elements .
---------------------
class CQueue {
//A Used to add B Used to delete B yes A In reverse order
LinkedList<Integer> A, B;// Define two stacks
public CQueue() {
// initialization
A = new LinkedList<Integer>();
B = new LinkedList<Integer>();
}
public void appendTail(int value) {
//A Add an element at the end of the
A.addLast(value);
}
public int deleteHead() {
if (!B.isEmpty()) return B.removeLast();// Special judgement
if (A.isEmpty()) return -1;// Special judgement
while (!A.isEmpty()) {
//B It's empty A Not empty , First, let B get A The elements of
B.addLast(A.removeLast());
}
return B.removeLast();
}
}
notes : return B.removeLast(); To return as a value
/** * Your CQueue object will be instantiated and called as such: * CQueue obj = new CQueue(); * obj.appendTail(value); * int param_2 = obj.deleteHead(); */
版权声明
本文为[Tang and Song Dynasties]所创,转载请带上原文链接,感谢
https://yzsam.com/2022/04/202204231535203756.html
边栏推荐
猜你喜欢
JVM-第2章-类加载子系统(Class Loader Subsystem)
Cap theorem
IronPDF for .NET 2022.4.5455
Demonstration meeting on startup and implementation scheme of swarm intelligence autonomous operation smart farm project
时序模型:长短期记忆网络(LSTM)
pgpool-II 4.3 中文手册 - 入门教程
Wechat applet customer service access to send and receive messages
Mysql database explanation (IX)
负载均衡器
Application of Bloom filter in 100 million flow e-commerce system
随机推荐
[leetcode daily question] install fence
通過 PDO ODBC 將 PHP 連接到 MySQL
el-tree实现只显示某一级复选框且单选
【Leetcode-每日一题】安装栅栏
字符串排序
Sorting and replying to questions related to transformer
Multi level cache usage
什么是CNAS认证?CNAS认可的软件测评中心有哪些?
Mumu, go all the way
PHP operators
字节面试 transformer相关问题 整理复盘
c语言---字符串+内存函数
c语言---指针进阶
【backtrader源码解析18】yahoo.py 代码注释及解析(枯燥,对代码感兴趣,可以参考)
Educational codeforces round 127 A-E problem solution
The El tree implementation only displays a certain level of check boxes and selects radio
[backtrader source code analysis 18] Yahoo Py code comments and analysis (boring, interested in the code, you can refer to)
Deep learning - Super parameter setting
时序模型:门控循环单元网络(GRU)
Use of common pod controller of kubernetes