队列是先进先出的数据结构，栈时先进后出的数据结构，可以使用栈和队列模拟彼此。 # 两个队列模拟栈 使用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(); } ~~~