剑指Offer - 九度1512 - 用两个栈实现队列
2013-11-29 21:23
- 题目描述：
-
用两个栈来实现一个队列，完成队列的Push和Pop操作。
队列中的元素为int类型。
- 输入：
-
每个输入文件包含一个测试样例。
对于每个测试样例，第一行输入一个n(1<=n<=100000)，代表队列操作的个数。
接下来的n行，每行输入一个队列操作：
1. PUSH X 向队列中push一个整数x(x>=0)
2. POP 从队列中pop一个数。
- 输出：
-
对应每个测试案例，打印所有pop操作中从队列pop中的数字。如果执行pop操作时，队列为空，则打印-1。
- 样例输入：
-
3
PUSH 10
POP
POP
- 样例输出：
-
10
-1
题意分析：
用两个栈实现一个队列。栈(stack)的特点是先进后出，是反的；而队列(queue)的特点是先进先出，是正的。因此用两个栈，反两次就能正过来。接下来咱看看怎么个反法。
咱们从例子入手：四个数1， 2， 3， 4进入队列，如果这时想pop的话，应当是1出队。两个栈s1，s2如下(左边代表栈顶)：
s1 = [4, 3, 2, 1]
s2 = []
但是1， 2， 3， 4进栈时，栈顶元素是4。要想取出1的话，必须先pop掉4，3，2。pop出来的元素又不能扔掉，就扔另一个栈里去吧，于是就成了这样：
s1 = [1]
s2 = [2, 3, 4]
因为进站后顺序又反了一次，所以s2中存储的顺序就是正确的出队顺序，这时直接从s1中pop出元素‘1’即可。如果要继续pop元素的话，s2栈不为空，直接pop就能得到正确的结果。
于是有了下面的思路：
1. 初始化s1、s2为空。
2. 当进队时，直接将元素push进s1。
3. 当出队时，
若s2不为空，直接pop s2的元素即可出队；
若s2为空，则将s1中元素pop出来，并push到s2中，直到s1只剩一个元素。剩的那个元素pop出来就是出队的元素。
当然，两个栈都为空的话pop操作是无效的。
这题应该算是很经典的面试题了，挺巧妙的。以下是ac的代码。push入队时间复杂度O(1)，pop出队时间复杂度O(1)或O(n)，均摊下来仍是O(1)。
// 651425 zhuli19901106 1512 Accepted 点击此处查看所有case的执行结果 1184KB 1415B 70MS
//
#include <cstdio>
#include <cstring>
#include <stack>
using namespace std; class MyQueue{
public:
MyQueue()
{
} ~MyQueue()
{
while(!s1.empty()){
s1.pop();
}
while(!s2.empty()){
s1.pop();
}
} void push(int n)
{
s1.push(n);
} int pop()
{
if(s1.size() <= && s2.size() <= ){
// The queue is empty, return -1 to signal an error.
return -;
}
if(s2.size() > ){
int res = s2.top();
s2.pop();
return res;
}else{
int res;
while(s1.size() > ){
res = s1.top();
s1.pop();
s2.push(res);
}
res = s1.top();
s1.pop();
return res;
}
} void clear()
{
while(s1.size() > ){
s1.pop();
}
while(s2.size() > ){
s2.pop();
}
} int size()
{
return s1.size() + s2.size();
}
private:
stack<int> s1, s2;
}; int main()
{
char s[];
int n;
int i;
int tmp;
MyQueue queue; while(scanf("%d", &n) == ){
for(i = ; i < n; ++i){
scanf("%s", s);
if(strcmp(s, "PUSH") == ){
scanf("%d", &tmp);
queue.push(tmp);
}else if(strcmp(s, "POP") == ){
printf("%d\n", queue.pop());
}
}
queue.clear();
} return ;
}