用两个栈实现队列

  • 题目描述:

用两个栈来实现一个队列,完成队列的Push和Pop操作。 队列中的元素为int类型。

  • 解题思路:

Push操作:入栈 => 入队
Pop操作:队列的特点是先进先出,栈的特点是先进后出,所以可以利用两个栈,先将栈1的元素都压入栈2中,再从栈2中依次将元素弹出,从而实现队列的Pop操作。

  • 源代码:
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
class Solution
{
public:
void push(int node) {
stack1.push(node); //入栈 => 入队
}

int pop() {
if (stack1.empty() && stack2.empty()) {
return false;
}
int p;
if (stack2.empty()) {
while (!stack1.empty()) {
p = stack1.top();
stack2.push(p); //不断取出栈1的栈顶元素并压入栈2中
stack1.pop(); //弹出栈1中的元素
}
}
p = stack2.top();
stack2.pop();
return p; //弹出栈2中的元素并返回值,经过栈2的元素转移可以达到队列的效果
}

private:
stack<int> stack1;
stack<int> stack2;
};
-------------The End-------------