用两个栈实现队列
关键词：栈stack、队列
题目描述
用两个栈实现一个队列。队列的声明如下，请实现它的两个函数 appendTail 和 deleteHead ，分别完成在队列尾部插入整数和在队列头部删除整数的功能。(若队列中没有元素，deleteHead 操作返回 -1 )
示例 1：
1
2
3
4
| 输入：
["CQueue","appendTail","deleteHead","deleteHead"]
[[],[3],[],[]]
输出：[null,null,3,-1]
|
示例2：
1
2
3
4
| 输入：
["CQueue","deleteHead","appendTail","appendTail","deleteHead","deleteHead"]
[[],[],[5],[2],[],[]]
输出：[null,-1,null,null,5,2]
|
思路
思路一：
栈和队列的区别就是先进后出和先进先出，所以可以使用一个栈当作辅助栈，用来实现另一个栈中元素的顺序调节。
建立栈s1和s2，初始化为空；（栈s1用作辅助栈）
添加元素：如果s2为空，则直接添加；如果s2有元素，则先倒到s1中，添加元素，再从s1倒回来；
删除元素：如果s2为空，返回-1，否则返回并删除s2顶端的元素。
代码
思路一：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
| class CQueue {
public:
CQueue() {
s1 = stack<int> ();
s2 = stack<int> ();
}
void appendTail(int value) {
if(s2.empty()){
s2.push(value);
return;
}
else{
while(!s2.empty()){
s1.push(s2.top());
s2.pop();
}
s2.push(value);
while(!s1.empty()){
s2.push(s1.top());
s1.pop();
}
}
}
int deleteHead() {
if(s2.empty()) return -1;
int res = s2.top();
s2.pop();
return res;
}
stack<int> s1;
stack<int> s2;
};
|
知识点
栈stack的使用：
stack没有clear()函数，可以用s1 = stack<int> ();初始化为空。
栈和队列的区别。