1️⃣ 题目描述
用两个栈实现一个队列。队列的声明如下,请实现它的两个函数 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]
2️⃣ 解题思路
-
示例的含义:
-
第一行可以理解为对队列的操作,共有三种
①CQueue:创建队列
②appendTail:入队
③deleteHead:出队 -
第二行是appendTail,即入队函数的
形参值
。这里只有appendTail有形参值,CQueue和deleteHead没有 -
第三行代表deleteHead,即出队函数的
返回值
。这里只有deleteHead有返回值,CQueue和appendTail没有。(若队列中没有元素,deleteHead返回 -1)
-
-
思路:
队列(queue)先入先出,栈(stack)先入后出。我们可以创建两个栈A和B来实现队列,其中栈A实现入队操作,栈B实现出队操作。
图解可以看 【栈】用两个栈实现队列对于deleteHead,共有四种情况:
栈A 栈B 操作 A空 B空 返回-1 A不空 B不空 返回 B栈顶的元素 A空 B不空 返回 B栈顶的元素 A不空 B空 A所有元素出栈,入栈到B中,然后返回 B栈顶的元素 上面的四种情况根据操作可以分为三类(第二行和第三行归为一类),可以下面的结构实现:文章来源:https://www.toymoban.com/news/detail-693892.html
if(条件1){ 条件1满足执行的语句 }else if(条件2){条件2满足执行的语句}... else{ 都不满足执行的语句}
3️⃣ 代码
class CQueue {
public:
CQueue() {}
void appendTail(int value) {
A.push(value);
}
int deleteHead() {
// 返回-1
if(A.empty()&&B.empty()){
return -1;
}
// 返回 B栈顶的元素
else if(!B.empty()){
int temp=B.top();
B.pop();
return temp;
}
// A所有元素出栈,入栈到B中,然后返回 B栈顶的元素
else{
while(!A.empty()){
int temp=A.top();
A.pop();
B.push(temp);
}
int temp=B.top();
B.pop();
return temp;
}
}
private:
stack<int> A,B;
};
/**
* Your CQueue object will be instantiated and called as such:
* CQueue* obj = new CQueue();
* obj->appendTail(value);
* int param_2 = obj->deleteHead();
*/
4️⃣ 知识点
c++中,stack的pop() 函数并不返回被删除元素的值,而是返回 void(空类型)。因此,如果想获得从栈中弹出的元素的值,需要调用top() ,即:文章来源地址https://www.toymoban.com/news/detail-693892.html
int temp=B.top();
B.pop();
return temp;
到了这里,关于Week1:用两个栈实现队列的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!