❓ 剑指 Offer 09. 用两个栈实现队列
难度:简单
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 appendTail
和 deleteHead
,分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素,deleteHead
操作返回 -1 )
示例 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 < = v a l u e s < = 10000 1 <= values <= 10000 1<=values<=10000
- 最多会对
appendTail
、deleteHead
进行10000
次调用
💡思路:
用两个栈来实现一个队列,完成队列的 appendTail
和 deleteHead
操作。
-
in
栈用来处理入栈(push
)操作,out
栈用来处理出栈(pop
)操作; - 一个元素进入
in
栈之后,出栈的顺序被反转。当元素要出栈时,需要先进入out
栈,此时元素出栈顺序再一次被反转,因此出栈顺序就和最开始入栈顺序是相同的,先进入的元素先退出,这就是队列的顺序。
🍁代码:(C++、Java)
C++
class CQueue {
private:
stack<int> in, out;
void in2out(){
while(!in.empty()){
out.push(in.top());
in.pop();
}
}
public:
CQueue() { }
void appendTail(int value) {
in.push(value);
}
int deleteHead() {
if(out.empty()){
if(in.empty()) return -1;
in2out();
}
int ans = out.top();
out.pop();
return ans;
}
};
/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/
Java
class CQueue {
private Stack<Integer> in = new Stack<Integer>();
private Stack<Integer> out = new Stack<Integer>();
private void in2out(){
while(!in.isEmpty()){
out.push(in.pop());
}
}
public CQueue() { }
public void appendTail(int value) {
in.push(value);
}
public int deleteHead() {
if(out.isEmpty()){
if(in.isEmpty()) return -1;
in2out();
}
return out.pop();
}
}
/**
* Your CQueue object will be instantiated and called as such:
* CQueue obj = new CQueue();
* obj.appendTail(value);
* int param_2 = obj.deleteHead();
*/
🚀 运行结果:
🕔 复杂度分析:
-
时间复杂度:
appendTail
为 O ( 1 ) O(1) O(1),deleteHead
为均摊 O ( 1 ) O(1) O(1)。对于每个元素,至多入栈和出栈各两次,故均摊复杂度为 O ( 1 ) O(1) O(1)。 -
空间复杂度: O ( n ) O(n) O(n),其中
n
是操作总数。对于有n
次appendTail
操作的情况,队列中会有 nnn 个元素,故空间复杂度为 O ( n ) O(n) O(n)。
题目来源:力扣。文章来源:https://www.toymoban.com/news/detail-583863.html
放弃一件事很容易,每天能坚持一件事一定很酷,一起每日一题吧!
关注我LeetCode主页 / CSDN—力扣专栏,每日更新!文章来源地址https://www.toymoban.com/news/detail-583863.html
注: 如有不足,欢迎指正!
到了这里,关于(栈队列堆) 剑指 Offer 09. 用两个栈实现队列 ——【Leetcode每日一题】的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!