用两个队列实现一个栈。
姊妹问题：用两个栈实现队列
分析：
队列插入可直接等同于栈的压栈。弹栈时，需要将队列1前n-1个元素存放到队列2中。将队列1的最后一个元素pop，然后把2中的元素赋值回去。
// offer-7-1-QueueToStack.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <iostream> #include <queue> using namespace std; // 栈模版 template <typename T> class CStack { public: CStack(){}; ~CStack(){}; void appendTail(const T& node); T deleteTail(); private: queue<T> q1; queue<T> q2; }; //压栈 template<typename T> void CStack<T>::appendTail(const T& node) { q1.push(node); } // 弹栈 template<typename T> T CStack<T>::deleteTail() { // 栈空？ if(q1.empty() && q2.empty()) throw exception("stack is empty"); // 栈不空，则将队列1的前n-1的元素挪到2中 if(!q1.empty()) { while(q1.size()!=1) { T& data = q1.front(); q1.pop(); q2.push(data); } } //弹栈 T tail = q1.front(); q1.pop(); // 恢复栈 if(!q2.empty()) { while(!q2.empty()) { T & data = q2.front(); q1.push(data); q2.pop(); } } return tail; } int _tmain(int argc, _TCHAR* argv[]) { CStack<int> a; //cout << a.deleteTail() << endl; a.appendTail(1); // 1 a.appendTail(2); // 1-2 a.appendTail(3); // 1-2-3 cout << a.deleteTail(); // 1-2 a.appendTail(4); // 1-2-4 cout << a.deleteTail() << endl; // 1-2 cout << a.deleteTail() << endl; // 1 //cout << a.deleteTail() << endl; // 空 return 0; }问题： 上述实现中，每次弹栈将1的元素搬到2中，完了再搬回去。两次拷贝，开销较大。
解决：两个队列的状态，当结束操作时，总是一个空，一个为栈。我们每次压栈时，判断谁不空则给谁压。删除时，判断谁不是空的，则把值拷贝到空的。这样每次弹栈只需要一次拷贝。
// offer-7-1-QueueToStack.cpp : 定义控制台应用程序的入口点。 // #include "stdafx.h" #include <iostream> #include <queue> using namespace std; template <typename T> class CStack { public: CStack(){}; ~CStack(){}; void appendTail(const T& node); T deleteTail(); private: queue<T> q1; queue<T> q2; }; template<typename T> void CStack<T>::appendTail(const T& node) { // q1空则给q2压，q1不空则压q1 queue<T> * qtmp = (q1.empty()) ? &q2 : &q1; qtmp->push(node); } template<typename T> T CStack<T>::deleteTail() { if(q1.empty() && q2.empty()) throw exception("stack is empty"); // 两个指针分别指向空队列和不空队列 queue<T> * qtmp_not_empty = (q1.empty()) ? &q2 : &q1; queue<T> * qtmp_empty = (q1.empty()) ? &q1 : &q2; while(qtmp_not_empty->size() != 1) { // 将不空队列的n-1个值拷贝到空队列 T& data = qtmp_not_empty->front(); qtmp_not_empty->pop(); qtmp_empty->push(data); } // 弹栈。队列交换状态 T tail = qtmp_not_empty->front(); qtmp_not_empty->pop(); return tail; } // 测试 int _tmain(int argc, _TCHAR* argv[]) { CStack<int> a; //cout << a.deleteTail() << endl; a.appendTail(1); a.appendTail(2); a.appendTail(3); cout << a.deleteTail() << endl; a.appendTail(4); cout << a.deleteTail() << endl; cout << a.deleteTail() << endl; //cout << a.deleteTail() << endl; return 0; }