隊列是先進先出的數據結構，棧時先進后出的數據結構，可以使用棧和隊列模擬彼此。 # 兩個隊列模擬棧 使用C++泛型編程，隊列使用STL的queue容器適配器。 主要思想： 兩個隊列模擬棧時，某時刻要么兩個隊列均為空，要么有一個隊列為空。 （1）向棧中push時：如果兩個隊列均為空，將元素插入某個隊列（這里假定插入隊列1）； ????????????????????????????????????? 如果某個隊列不為空，將元素push到該隊列中即可。 （2）從棧中pop時： 如果兩個隊列均為空，則函數返回即可； ???????????????????????????????????? 如果某個隊列不為空，將該隊列的前n-1個元素出隊，并依次插入另一個隊列，再將最后一個元素pop（最后一個元素就是要）。 ~~~ //test.h #ifndef TEST_TEST_H #define TEST_TEST_H #include <iostream> #include <string> #include <vector> #include <map> #include <set> #include <queue> #include <stack> using namespace std; template <class T> class Qstack { private: queue<T> queue1; queue<T> queue2; public: void display(); //輸出所有元素 void push(const T& value); //向棧中插入 void pop(); //從棧中彈出 }; template<typename T> void Qstack<T>::display() { if (queue1.size() > 0) { queue<T> q1(queue1); while (q1.size() > 0) { cout << q1.front() << " "; q1.pop(); } } if (queue2.size() > 0) { queue<T> q2(queue2); while (q2.size() > 0) { cout << q2.front() << " "; q2.pop(); } } cout << endl << endl; } //注意這里在類模板外定義其成員函數的寫法 template<class T> void Qstack<T>::push(const T& value) { if (queue2.empty()) queue1.push(value); else if (queue1.empty()) queue2.push(value); else {} } //這里的pop操作返回void，當棧為空時什么也不做。 //這和STL中棧適配器pop操作行為一致 template<typename T> void Qstack<T>::pop() { if (queue1.size() > 0) { while (queue1.size() > 1) { queue2.push(queue1.front()); queue1.pop(); } queue1.pop(); } else if (queue2.size() > 0) { while (queue2.size() > 1) { queue1.push(queue2.front()); queue2.pop(); } queue2.pop(); } else {} return; } #endif ~~~ 測試： ~~~ #include "qstack.h" using namespace std; int main() { Qstack<string> s; s.push("1"); s.push("2"); s.push("3"); s.display(); s.pop(); s.display(); s.push("4"); s.push("5"); s.display(); s.pop(); s.display(); s.pop(); s.display(); } ~~~  # 兩個棧模擬隊列 使用C++泛型編程，棧使用STL的stack容器適配器。 主要思想： 與“兩個隊列模擬棧”不同：這個問題中，在某個狀態下兩個棧可能都不為空。 （1）向隊列插入：一律插入stack1中。 （2）從隊列取數：如果stack2不為空，直接從stack2中彈出一個元素； ?????????????????????????? ? ??? 如果stack2為空，那么將stack1中所有元素彈出并插入stack2，然后從stack2中pop一個。 ~~~ template <typename T> class CQueue { public: void display(); // 在隊列末尾添加一個結點 void appendTail(const T& node); // 刪除隊列的頭結點 void deleteHead(); private: stack<T> stack1; stack<T> stack2; }; template<typename T> void CQueue<T>::display() { stack<T> sq1(stack1); stack<T> sq2(stack2); while (sq2.size() > 0) { cout << sq2.top() << " "; sq2.pop(); } while (sq1.size() > 0) { T data = sq1.top(); sq1.pop(); sq2.push(data); } while (sq2.size() > 0) { cout << sq2.top() << " "; sq2.pop(); } cout << endl; } template<typename T> void CQueue<T>::appendTail(const T& element) { stack1.push(element); } template<typename T> void CQueue<T>::deleteHead() { if(stack2.size()<= 0) { while(stack1.size()>0) { T& data = stack1.top(); stack1.pop(); stack2.push(data); } } if (stack2.size() > 0) stack2.pop(); return; } ~~~ 《劍指offer》中deleteHead函數返回被刪除的元素，我認為沒必要，因為STL中queue隊列的刪除返回就是void。當對空queue進行pop操作時，在VS2010下運行時會提示下圖所示內容，但是g++下不會有任何提示，程序正確。  測試： ~~~ int main() { CQueue<int> cq; cq.appendTail(1); cq.appendTail(2); cq.appendTail(3); cq.appendTail(4); cq.display(); cq.deleteHead(); cq.deleteHead(); cq.display(); cq.appendTail(5); cq.appendTail(6); cq.display(); } ~~~