用两个栈来实现一个队列，完成队列的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
题解：应该是考察STL栈应用的一道面试题，还有一点小技巧，不要用两个水杯倒来倒去（如图，明显错误做法）。用一个水杯倒就可以了。
代码：C的简洁 && C++的优雅。
C代码：
|
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 |
#include <stdio.h>#include <string.h>#include <stdlib.h>int main(int
argc, char
const *argv[]){ int
t, data, top1, top2; top1 = top2 = 0; scanf("%d", &t); char
command[10]; int
*stack1 = (int
*)malloc( (t+1) * sizeof(int)); int
*stack2 = (int
*)malloc( (t+1) * sizeof(int)); while(t--){ scanf("%s", command); if(strcmp(command, "PUSH") == 0){ scanf("%d", &data); stack1[top1++] = data; } if(strcmp(command, "POP") == 0){ if(!top1 && !top2) printf("-1\n"); else{ if(!top2) while(top1) stack2[top2++] = stack1[--top1]; printf("%d\n", stack2[--top2]); } } } return
0;} |
C++ 代码：
|
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57 |
#include <cstdio>#include <stack>using
namespace std;char
ch[10];class
queue{public: void
push(int
a) { pushStack.push(a); } int
pop() { int
tmp = -1; if
(popStack.empty()) { if
(pushStack.empty()) return
-1; else { while
(!pushStack.empty()) { popStack.push(pushStack.top()); pushStack.pop(); } } } tmp = popStack.top(); popStack.pop(); return
tmp; }private: stack<int> pushStack; stack<int> popStack;}; int
main(){ int
n,t; while(scanf("%d",&n) != EOF) { queue q; for(int
i = 0; i < n; ++i) { scanf("%s",ch); if(ch[1] == ‘U‘) { scanf("%d",&t); q.push(t); }else { printf("%d\n",q.pop()); } } } return
0;} |
C++的 优雅写法：
|
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66 |
#include<iostream>#include<stdlib.h>#include<stack>using
namespace std;template
<typename
T>class
CQueue{public: CQueue(void); ~CQueue(void); void
appendtail(const
T& node); T deleteHead();private: stack<T> stack1; stack<T> stack2;};//构造函数template
<typename
T> CQueue<T>::CQueue(void){}//析构函数template
<typename
T> CQueue<T>::~CQueue(void){}//插入元素template
<typename
T> void
CQueue<T>::appendtail(const
T& node){ stack1.push(node);}//删除元素并返回template
<typename
T> T CQueue<T>::deleteHead(){ if(stack2.size()<=0) { while(stack1.size()>0) { stack2.push(stack1.top()); stack1.pop(); } } if(stack2.size()==0) throw
new exception("队列为空"); T head=stack2.top(); stack2.pop(); return
head;}void
main(){ CQueue<int> queue; queue.appendtail(1); queue.appendtail(2); queue.appendtail(3); queue.appendtail(4); int
len=4; while(len>0) { cout<<queue.deleteHead()<<endl; --len; }} |
原文：http://www.cnblogs.com/firstrate/p/3541807.html