本文为剑指 offer 系列第七篇。
目的就是用两个后进先出的栈来实现一个先进先出的队列，思路比较巧妙。
用两个栈来实现一个队列，完成队列的Push和Pop操作。 队列中的元素为int类型。
解题思路
思路1
思路1比较朴素，我们用一个栈来作为数据存储的栈A，然后另一个作为中转的栈B，当我们存数据的时候，我们将数据压入到栈A中，然后取数据的时候，我们将A的所有数据都压入到B中，这个时候B的出栈顺序也就是队列应该的出队列顺序了，所以此时将B的栈顶元素取出即可，然后再将B中的所有的数据重新压回A中，后续操作皆是如此。
思路2
思路2其实是思路1的改进版，我们发现思路1在将数据取出之后，又把所有数据压回A栈，这样就会有很大的浪费，这里其实只要加一层判断，当往外取数据的时候，只要B栈不为空，就直接从B栈出栈栈顶元素即可，如果B栈为空，那么将A栈的数据全部压入到B栈中。从而省去中间多余的数据的来回压入操作。
解题代码
思路1代码
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
| class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
int res = stack2.top();
stack2.pop();
while(!stack2.empty()){
stack1.push(stack2.top());
stack2.pop();
}
return res;
}
private:
stack<int> stack1;
stack<int> stack2;
};
|
时间复杂度为O(n^2),空间复杂度为O(n)
思路2代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| class Solution
{
public:
void push(int node) {
stack1.push(node);
}
int pop() {
if(stack2.empty()){
while(!stack1.empty()){
stack2.push(stack1.top());
stack1.pop();
}
}
int res = stack2.top(); stack2.pop();
return res;
}
private:
stack<int> stack1;
stack<int> stack2;
};
|
时间复杂度为O(n),空间复杂度为O(n)
以上，本题结束！