1.

//使用两个队列实现一个栈,优化版（1.入栈只如q1,出栈将q1数据倒q2，删掉刚进来的，//若q1无数据，从q2倒,删q2中最后一个数据2.只保证一个栈中有数据，简单，易理解）//第一种实现

template<classT>classStack{public:boolEmpty(){return_q1.empty()&&_q2.empty();}voidPush(constT&x){_q1.push(x);}voidPop(){assert((!_q1.empty())||(!_q2.empty()));if(_q1.empty()){while(_q2.size()!=1){_q1.push(_q2.front());_q2.pop();}_q2.pop();}else{while(_q1.size()!=1){_q2.push(_q1.front());_q1.pop();}_q1.pop();}}intSize(){return_q1.size()+_q2.size();}//先取_q1的back,若_q1为空，再取_q2的值T&Top(){assert((!_q1.empty())||(!_q2.empty()));if(!_q1.empty())return_q1.back();elsereturn_q2.back();}protected:queue<T>_q1;queue<T>_q2;};

2.

//第二种实现template<classT>classStack{public:voidPush(constT&x){if(!_q2.empty())_q2.push(x);else_q1.push(x);}voidPop(){if(!_q1.empty()){while(_q1.size()!=1){_q2.push(_q1.front());_q1.pop();}_q1.pop();}else{while(_q2.size()!=1){_q1.push(_q2.front());_q2.pop();}_q2.pop();}}T&Top(){if(!_q1.empty()){return_q1.back();}elsereturn_q2.back();}protected:queue<T>_q1;queue<T>_q2;};voidTest1(){Stack<int>s1;s1.Push(1);s1.Push(2);s1.Push(3);s1.Push(4);s1.Push(5);s1.Pop();cout<<s1.Top()<<endl;s1.Pop();cout<<s1.Top()<<endl;//cout<<s1.Size()<<endl;s1.Push(6);cout<<s1.Top()<<endl;s1.Pop();cout<<s1.Top()<<endl;s1.Push(7);cout<<s1.Top()<<endl;s1.Pop();s1.Pop();s1.Pop();cout<<s1.Top()<<endl;}