棧是 LIFO，將進出順序逆序。
隊列是 FIFO，保持進與出的順序一致。
所以隊列對順序不起作用，不能用兩個隊列模擬一個棧。
兩個棧模擬一個隊列
S1 S2 Q
S1 為插入棧，S2 為彈出棧。以實現隊列 Q。
1 #include <iostream>
2 #include <stack>
3 using namespace std;
4
5 template <typename T>
6 class QueueByDoubleStack
7 {
8 private:
9 stack<T> s1;
10 stack<T> s2;
11 public:
12 size_t size()
13 {
14 return s1.size() + s2.size();
15 }
16 bool empty()
17 {
18 return s1.empty() && s2.empty();
19 }
20 void push(T t)
21 {
22 s1.push(t);
23 }
24 void pop()
25 {
26 if (s2.empty())
27 {
28 while (!s1.empty())
29 {
30 s2.push(s1.top());
31 s1.pop();
32 }
33 }
34 s2.pop();
35 }
36 T top()
37 {
38 if (s2.empty())
39 {
40 while (!s1.empty())
41 {
42 s2.push(s1.top());
43 s1.pop();
44 }
45 }
46 return s2.top();
47 }
48 };
49
50 int main()
51 {
52 QueueByDoubleStack<int> q;
53 for (int i = 0; i < 10; ++i)
54 {
55 q.push(i);
56 }
57 while (!q.empty())
58 {
59 cout << q.top() << ' ';
60 q.pop();
61 }
62 cout << endl;
63 return 0;
64 }
posted on 2011-05-18 19:58
unixfy 閱讀(933)
評論(0) 編輯 收藏 引用