用两个栈模拟队列

　　用两个栈模拟队列，算法如下图所示：

程序如下：

Queue类的接口与实现

 1 /********************************************************************
 2     created:    2013/08/18
 3     created:    18:8:2013   21:54
 4     file base:    Queue
 5     file ext:    h
 6     author:        Justme0 (http://blog.csdn.net/Justme0)
 7     
 8     purpose:    用两个栈模拟队列
 9 *********************************************************************/
10 
11 #ifndef _QUEUE_H_
12 #define _QUEUE_H_
13 
14 #include <cassert>
15 #include <stack>
16 using namespace std;
17 
18 template <class T>
19 class Queue {
20 public:
21     bool empty() const;
22     void push(T x);
23     T pop();
24 
25 protected:
26     stack<T> _s_push;
27     stack<T> _s_pop;
28 };
29 
30 template <class T>
31 bool Queue<T>::empty() const {
32     return this->_s_pop.empty() && this->_s_push.empty();
33 }
34 
35 template <class T>
36 void Queue<T>::push(T x) {
37     _s_push.push(x);
38 }
39 
40 template <class T>
41 T Queue<T>::pop() {
42     assert(!empty());
43 
44     if (this->_s_pop.empty()) {
45         while (!_s_push.empty()) {
46             _s_pop.push(_s_push.top());
47             _s_push.pop();
48         }
49     }
50 
51     T top = _s_pop.top();
52     _s_pop.pop();
53     return top;
54 }
55 
56 #endif

测试程序

 1 /********************************************************************
 2     created:    2013/08/18
 3     created:    18:8:2013   21:53
 4     file base:    main
 5     file ext:    cpp
 6     author:        Justme0 (http://blog.csdn.net/Justme0)
 7     
 8     purpose:    测试程序
 9 *********************************************************************/
10 
11 #include "Queue.h"
12 #include <iostream>
13 
14 using namespace std;
15 
16 int main(int argc, char **argv) {
17     Queue<int> obj;
18 
19     for (int i = 0; i < 10; ++i) {
20         obj.push(i);
21     }
22 
23     for (int i = 0; i < 5; ++i) {
24         cout << obj.pop() << endl;
25     }
26 
27     for (int i = 10; i < 20; ++i) {
28         obj.push(i);
29     }
30 
31     while (!obj.empty()) {
32         cout << obj.pop() << endl;
33     }
34 
35     return 0;
36 }

运行结果

0
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
请按任意键继续. . .