首先，我们得了解队列和栈的基本原理。

队列是一个“先进先出“的一个结构。队列的定义是在队尾插入，在队头删除，这就要求要用一种在尾部插入容易的，在头部删除容易的结构，你一定会想到单链表，对，库的实现就是用一个链表实现的。

栈，相信大家都不会陌生，函数栈帧等的实现，它是一种”先进后出“的结构。栈的插入删除都是在尾部进行的。

所以要用队列实现一个栈，要解决的问题就是在删除时要删除最后插入的那个元素。

我们先来模拟一下出栈和入栈的情况：

（1）入栈：Q1：1，2，3，4入队列（相当于入栈）；

（2）出栈：Q1：1，2，3出队列，Q2：1，2，3入队列；（此时Q1只剩4，正是我们要出栈的元素）

（3）

1>入栈：Q1：5入队列（每次入栈都用Q1入队列实现，而不入队列Q2，这样会提高效率，后面会说到）

2>出栈：判断：如果Q1队列不为空就用（1）（2）步的方法出栈最后一个元素。否则，出栈Q2队列的最后一个元素。

我们首先来搭建这个栈的结构：

#pragmaonce#include<iostream>#include<queue>#include<string>#include<assert.h>usingnamespacestd;template<classT>classMYStack{public:MYStack():_size(0){}~MYStack(){}voidPush(constT&x);voidPop();boolEmpty();size_tSize();voidPrint();private:queue<T>q1;queue<T>q2;size_t_size;};

一个栈具有的功能我们都实现一下，Psh(),Pop(),Empty(),Size()等等。

在这个结构中数据成员是两个队列的对象，因为我们是用两个队列来实现的，还有一个_size用来记录栈中元素的个数。

下面是函数具体实现：

template<classT>voidMYStack<T>::Push(constT&x){q1.push(x);++_size;}template<classT>voidMYStack<T>::Pop(){//assert(_size>0);//size_tplen=q1.size();//while(plen!=1)//{//Ttmp=q1.front();//q2.push(tmp);//q1.pop();//--plen;//}//q1.pop();//plen=q2.size();//while(plen)//{//Ttmp=q2.front();//q1.push(tmp);//q2.pop();//--plen;//}//--_size;assert(_size>0);size_tplen=q1.size();if(plen==0){//if(q2.size()==0)//return;plen=q2.size();while(plen!=1){Ttmp=q2.front();q1.push(tmp);q2.pop();--plen;}q2.pop();}else{size_tplen=q1.size();while(plen!=1){Ttmp=q1.front();q2.push(tmp);q1.pop();--plen;}q1.pop();}--_size;}template<classT>boolMYStack<T>::Empty(){return_size?false:true;}template<classT>size_tMYStack<T>::Size(){return_size;}template<classT>voidMYStack<T>::Print(){//size_tplen=q1.size();//while(plen--)//{//cout<<q1.front()<<"";//q1.pop();//}size_tplen=q2.size();while(plen--){cout<<q2.front()<<"";q2.pop();}plen=q1.size();while(plen--){cout<<q1.front()<<"";q1.pop();}}

注释掉的部分也可以实现，它的原理是不管第（3）步是出栈还是入栈，都把剩下的元素从Q2出栈入栈到Q1，输出的时候只用输出Q1中的元素。但是它的效率较低。如果有这种情况：1，2，3.....100000入栈，然后1，2，3......100000出栈，这会导致Q1和Q2频繁的出栈和入栈，效率非常之低。

优化方法就是没有注释部分。它的实现就是入栈都是Q1入队列，出栈后不把Q2的元素移到Q1，这样的话效率就会提高，只是在输出的时候要先输出Q2里的元素，再输出Q1里的元素。因为Q1里的元素总是栈顶的元素。