C++ 數據結構實現兩個棧實現一個隊列
棧為后進先出，隊列為先進先出
用兩個棧實現一個隊列。是一個比較經典的問題。
看到這個問題，我的第一個解題思路為：
定義兩個棧，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++實現如下：
#include<iostream> using namespace std; #include<stack> //棧 后進先出 隊列 先進先出 template<class T> class Queue { public: /*T Pop_back() { if (s2.size() <= 0) { while(s1.size() > 0) { T& temp = s1.top(); s1.pop(); s2.push(temp); } } if (s2.size() == 0) throw new exception("queue is empty "); T tep = s2.top(); s2.pop(); return tep; }*/ T Pop_back() //比上面少一次出棧 { if (s2.size() <= 0) { while (s1.size() > 1) { T& temp = s1.top(); s1.pop(); s2.push(temp); } T tep = s1.top(); s1.pop(); return tep; } else{ T tep = s2.top(); s2.pop(); return tep; } } void Push_back(const T& value) { s1.push(value); } bool Empty() { return (s1.empty() && s2.empty()); } protected: stack<T> s1; stack<T> s2; }; void TextQueue() { Queue<int> q1; q1.Push_back(1); q1.Push_back(2); q1.Push_back(3); q1.Push_back(4); cout << q1.Pop_back() << endl; cout << q1.Pop_back() << endl; cout << q1.Pop_back() << endl; cout << q1.Pop_back() << endl; } 感謝閱讀，希望能幫助到大家，謝謝大家對本站的支持！
新聞熱點
疑難解答
