兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列
要求：只能使用棧的pop和push，以及測(cè)試棧是否為空三個(gè)操作。
實(shí)現(xiàn)思路：
隊(duì)列里面使用stack one 和 stack two。
進(jìn)隊(duì)列時(shí)，直接進(jìn)入棧one即可。
出隊(duì)列時(shí)，從two彈出一個(gè)元素，如果two里面的元素為空，則將one里面的元素依次彈出并壓入two中，再?gòu)膖wo彈出一個(gè)元素返回。
用STL里面的stack模擬實(shí)現(xiàn)queue的代碼如下：
1 #include <stdio.h> 2 #include <stdlib.h>
3 #include <time.h>
4 #include <stack>
5 using std::stack;
6
7 template<class T> class CQueue
8 {
9 public:
10 CQueue()
11 {
12 nSize = 0;
13 }
14
15 void clear()
16 {
17 while (!one.empty())
18 {
19 one.pop();
20 }
21 while (!two.empty())
22 {
23 two.pop();
24 }
25 }
26
27 void push(const T& t)
28 {
29 one.push(t);
30 ++nSize;
31 }
32
33 void pop()
34 {
35 if (two.empty())
36 {
37 while (!one.empty())
38 {
39 two.push(one.top());
40 one.pop();
41 }
42 }
43 two.pop();
44 --nSize;
45 }
46
47 T& front()
48 {
49 if (two.empty())
50 {
51 while (!one.empty())
52 {
53 two.push(one.top());
54 one.pop();
55 }
56 }
57 return two.top();
58 }
59
60 T& back()
61 {
62 return one.top();
63 }
64
65 bool empty()
66 {
67 return nSize == 0;
68 }
69
70 private:
71 stack<T> one;
72 stack<T> two;
73 int nSize;
74 };
75
76 #define MAX 20
77
78 int main()
79 {
80 CQueue<int> q;
81
82 srand(time(NULL));
83 for (int i = 0; i < MAX; ++i)
84 {
85 q.push(i);
86
87 if (rand() % 2)
88 {
89 printf("front: %d\n", q.front());
90 q.pop();
91 }
92 }
93
94 while (!q.empty())
95 {
96 printf("front: %d\n", q.front());
97 q.pop();
98 }
99
100 return 0;
101 }
102
兩個(gè)隊(duì)列實(shí)現(xiàn)一個(gè)棧
要求：只能使用從隊(duì)列的尾部入和頭部出，以及測(cè)試隊(duì)列是否為空三個(gè)操作。
實(shí)現(xiàn)思路：
隊(duì)列里面使用queue one 和 stack two。
進(jìn)棧時(shí)，根據(jù)當(dāng)前元素是全部存儲(chǔ)在哪個(gè)隊(duì)列而選擇從one或者two的尾部進(jìn)入。
出棧時(shí)，假設(shè)當(dāng)前元素都存儲(chǔ)在one里面，則不斷出隊(duì)列，直到隊(duì)列為空之前的所有元素一次進(jìn)入隊(duì)列two，而one里面的最后一個(gè)元素
作為棧彈出的值返回。
對(duì)于當(dāng)前元素是存儲(chǔ)在哪個(gè)隊(duì)列里面，可以設(shè)置變量標(biāo)記，初始化時(shí)候存儲(chǔ)在one里面，操作一次，由于元素要倒轉(zhuǎn)，則存儲(chǔ)位置會(huì)變
一次。
用STL里面的queue模擬實(shí)現(xiàn)的stack代碼如下：
1 #include <stdio.h> 2 #include <queue>
3 using std::queue;
4
5 template<class T> class CStack
6 {
7 public:
8 CStack()
9 {
10 nSize = 0;
11 nTime = 1;
12 }
13
14 void clear()
15 {
16 while (!one.empty())
17 {
18 one.pop();
19 }
20 while (!two.empty())
21 {
22 two.pop();
23 }
24 }
25
26 void push(const T& t)
27 {
28 if (nTime % 2)
29 {
30 one.push(t);
31 }
32 else
33 {
34 two.push(t);
35 }
36 ++nSize;
37 }
38
39 void pop()
40 {
41 if (nTime % 2)
42 {
43 while (!one.empty())
44 {
45 T t = one.front();
46 one.pop();
47 if (!one.empty())
48 {
49 two.push(t);
50 }
51 }
52 }
53 else
54 {
55 while (!two.empty())
56 {
57 T t = two.front();
58 two.pop();
59 if (!two.empty())
60 {
61 one.push(t);
62 }
63 }
64 }
65
66 nTime = (nTime + 1) % 2;
67 --nSize;
68 }
69
70 T& top()
71 {
72 if (nTime % 2)
73 {
74 while (!one.empty())
75 {
76 T t = one.front();
77 one.pop();
78 if (!one.empty())
79 {
80 two.push(t);
81 }
82 else
83 {
84 two.push(t);
85 nTime = (nTime + 1) % 2;
86 return two.back();
87 }
88 }
89 }
90 else
91 {
92 while (!two.empty())
93 {
94 T t = two.front();
95 two.pop();
96 if (!two.empty())
97 {
98 one.push(t);
99 }
100 else
101 {
102 one.push(t);
103 nTime = (nTime + 1) % 2;
104 return one.back();
105 }
106 }
107 }
108 }
109
110 bool empty()
111 {
112 return nSize == 0;
113 }
114
115 private:
116 queue<T> one;
117 queue<T> two;
118 int nSize;
119 int nTime;
120 };
121
122 #define MAX 20
123
124 int main()
125 {
126 CStack<int> stack;
127
128 for (int i = 0; i < MAX; ++i)
129 {
130 stack.push(i);
131 }
132
133 while (!stack.empty())
134 {
135 printf("top: %d\n", stack.top());
136 stack.pop();
137 }
138
139 return 0;
140 }
141