posts - 183,  comments - 10,  trackbacks - 0

栈是 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 阅读(928) 评论(0)  编辑 收藏 引用

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理