用两个栈实现一个队列(转载)

栈为后进先出，队列为先进先出

    用两个栈实现一个队列。是一个比较经典的问题。

看到这个问题，我的第一个解题思路为：

          定义两个栈，s1,s2。s1作为入队列栈，s2作为出队列栈；

                    入队列：每次入队列的时候，将数值压入s1栈中；

                    出队列：出队列时，将s1中的所有数据，压进s2栈中，然后删除s2的栈顶数据，然后再将s2中的剩余数据压入s1中。

在这其中s1是一个存储空间，s2是一个辅助空间。

   进一步想一下上述办法，在出队列时，每一次都要将s1倒进s2，然后删除s2栈顶后又将s2的数据倒入s1;有另一个思路可以减少倒的次数；

             入队列时：将数据压进s1;

             出队列时：判断如果s2为空，那么将s1中的数据，压进s2中，然后删除s2栈顶，如果s2不为空那么再删除s2的栈顶即可；

并且还可以优化，优化如下：

           出队列时，判断如果s2为空，那么将s1中n-1个数据，压进s2中，然后删除s1中的栈顶，如果s2不为空那么直接删除s2的栈顶即可；

优化版的c++实现如下：

[cpp] view plain copy

1. #include<iostream>  
2. using namespace std;  
3. #include<stack>  
4. //栈 后进先出  队列 先进先出  
5. template<class T>  
6. class Queue  
7. {  
8. public:  
9.   
10.     /*T Pop_back() 
11.     { 
12.         if (s2.size() <= 0) 
13.         { 
14.             while(s1.size() > 0) 
15.             { 
16.                 T& temp = s1.top(); 
17.                 s1.pop(); 
18.                 s2.push(temp); 
19.             } 
20.         } 
21.         if (s2.size() == 0) 
22.             throw new exception("queue is empty "); 
23.  
24.         T tep = s2.top(); 
25.         s2.pop(); 
26.         return tep; 
27.     }*/  
28.   
29.     T Pop_back()  //比上面少一次出栈  
30.     {  
31.         if (s2.size() <= 0)  
32.         {  
33.             while (s1.size() > 1)  
34.             {  
35.                 T& temp = s1.top();  
36.                 s1.pop();  
37.                 s2.push(temp);  
38.             }  
39.             T tep = s1.top();  
40.             s1.pop();  
41.             return tep;  
42.         }  
43.         else{  
44.             T tep = s2.top();  
45.             s2.pop();  
46.             return tep;  
47.         }  
48.     }  
49.       
50.         void Push_back(const T& value)  
51.     {  
52.         s1.push(value);  
53.     }  
54.   
55.         bool Empty()  
56.         {  
57.             return (s1.empty() && s2.empty());  
58.         }             
59.   
60. protected:  
61.     stack<T> s1;  
62.     stack<T> s2;  
63. };  
64.   
65. void TextQueue()  
66. {  
67.     Queue<int> q1;  
68.     q1.Push_back(1);  
69.     q1.Push_back(2);  
70.     q1.Push_back(3);  
71.     q1.Push_back(4);  
72.   
73.     cout << q1.Pop_back() << endl;  
74.     cout << q1.Pop_back() << endl;  
75.     cout << q1.Pop_back() << endl;  
76.     cout << q1.Pop_back() << endl;  
77. }