下面这段代码是我定义的Stack类模板，接下来介绍几种用2个该Stack类实现队列Queue的几种方法。

template<classT,intDEFAULT_CAPACITY=0>classStack{public:Stack();Stack(constStack<T>&st);Stack&operator=(constStack<T>&st);~Stack();public:voidPush(constT&data);voidPop();T&Top();T&End();boolEmpty();size_tSize();voidPrint();protected:voidCheckCapacity();protected:T*_arr;size_t_top;size_t_capacity;};

声明：为了实现除“入队”“出队”之外更多的功能，比如“打印”等，我将上面那个已造好的“轮子”Stack做了扩展，增加了一些成员方法。而如果你关注的重点是push和pop的算法，那么其实并不需要在意我造的下面这个“轮子”。可以直接跳过下面的代码，并把所有我使用的Stack类型当作库里的stack即可.

扩展后的Stack:

template<classT,intDEFAULT_CAPACITY=0>classStack{public:Stack():_arr(NULL),_top(0),_capacity(0){}Stack(constStack<T>&st):_arr(newT[st._capacity]),_top(st._top),_capacity(st._capacity){for(size_ti=0;i<_capacity;i++){_arr[i]=st._arr[i];}}Stack&operator=(constStack<T>&st){if(st._arr!=_arr){delete[]_arr;_arr=newT[st._capacity];for(size_ti=0;i<st._capacity;i++){_arr[i]=st._arr[i];}_top=st._top;_capacity=st._capacity;}return*this;}~Stack(){if(_arr!=NULL){delete[]_arr;}}public:voidPush(constT&data){CheckCapacity();_arr[_top]=data;++_top;}voidPop(){--_top;}T&Top(){return_arr[_top-1];}T&End(){return_arr[0];}boolEmpty(){if(0==_top){returntrue;}else{returnfalse;}}size_tSize(){return_top;}voidPrint(){for(size_ti=0;i<_top;i++){cout<<_arr[i]<<"";}cout<<endl;}voidRePrint(){if(0==_top){return;}for(inti=_top-1;i>=0;i--){cout<<_arr[i]<<"";}cout<<endl;}protected:voidCheckCapacity(){if(_top==_capacity){_capacity=_capacity+3;T*tmp=newT[_capacity];for(size_ti=0;i<_top;i++){tmp[i]=_arr[i];}delete[]_arr;_arr=tmp;}}protected:T*_arr;size_t_top;size_t_capacity;};

--------------------------------------------------------------------------------

一、普通版本

栈的特点是“先入后出”，而队列的特点是“先入先出”。

所以可以定义一个类Queue,包含2个成员对象：

一个栈_stack1存放数据，另一个栈_stack2用来临时存放数据，通过一些压栈出栈的成员方法就可以实现对队列的入队、出队操作。

实现的2个栈组成的队列如下图所示，现在要将一组数据【1 2 3 4 5】放入队列中：

先将这组数依次压入_stack1中，然后再将_stack1中的元素依次出栈压入_stack2中：

这时候，_stack2中的元素依次出栈，就相当于队列的出队操作了。

用代码实现：

定义一个类模板Queue:

template<classT>classQueue{Queue():_size(0){}voidPush(constT&data)//入队{_stack1.Push(data);++_size;}voidPop()//出队{Converse(_stack2,_stack1);_stack2.Pop();Converse(_stack1,_stack2);--_size;}protected:voidConverse(Stack<T>&dst,Stack<T>&src)//src->dst{while(size--){dst.Push(src.Top());src.Pop();}}protected:Stack<T>_stack1;Stack<T>_stack2;size_t_size;};

其中，

成员方法Converse():作用是将栈src中的内容依次出栈，压入栈dst中。

成员方法Push（） :入队操作，每次将元素data存入成员对象_stack1中。

成员方法Pop() :出队操作，弹出第一个送入的元素。其中，第二个Converse的作用是还原。

可以看出，这种入队、出队的算法，需要保证元素始终在_stack1中维护，而只有在出栈的时候用到_stack2临时存放数据。

采用这种方式实现的队列，可以实现正常的入队、出队操作，但应该注意到，其中出队操作需要进行两次压栈，我们可以对一个细节稍作优化，进一步提高出队操作的执行效率。

下图为优化后的出队操作：

区别在于，在出队操作时，将_stack1中的(_size - 1)个元素弹出并压入_stack2中。

弹出后，也不需要将_stack2的元素“倒回”_stack1中。

二、代码优化

具体的实现步骤为：

出队操作时：

而是在每次执行出队的时候进行一次判断：

若_stack2为空，则将_stack1中的(_size - 1)个元素弹出并压入_stack2中，并弹出_stack中剩下的那个元素（就是我上面说的那个步骤）；

若_stack2不为空，则弹出_stack2中最顶层的元素。

在入队操作时，判断_stack1是否为空：

若为空，则先将_stack2中的元素依次弹出并压入_stack1中，然后再将入栈元素压入_stack1中（左图）

否则，直接将入栈元素压入_stack1中

优化后的方案用代码实现如下：

template<classt>classqueue{public:queue():_size(0){}queue(constqueue&que){_stack1=que._stack1;_size=que._size;}public:voidPush(constt&data){if(_stack1.Empty()&&!_stack2.Empty()){Converse(_stack1,_stack2);}_stack1.Push(data);++_size;}voidPop(){if(_stack2.Empty()){if(_stack1.Empty()){return;}RemainConverse(_stack2,_stack1);_stack1.Pop();}else{_stack2.Pop();}--_size;}voidPrint(){_stack1.Print();_stack2.RePrint();}boolEmpty(){return(0==_size);}t&Front(){if(_stack1.empty()){return_stack2.top();}else{return_stack1.end();}}t&Back(){if(_stack1.Empty()){return_stack2.End();}else{return_stack1.Top();}}size_tSize(){return_size;}protected:voidRemainConverse(Stack<t>&dst,Stack<t>&src){size_tcount=src.Size()-1;while(count--){dst.Push(src.Top());src.Pop();}}voidConverse(Stack<t>&dst,Stack<t>&src)//src->dst{while(!src.Empty()){dst.Push(src.Top());src.Pop();}}protected:Stack<t>_stack1;Stack<t>_stack2;size_t_size;};intmain(){queue<int>que1;que1.Push(1);que1.Push(2);que1.Push(3);que1.Push(4);que1.Print();que1.Pop();que1.Print();que1.Push(5);que1.Print();return0;}

到目前我们已经实现了2种不同的方式实现这个队列。

这两种方法相比，第一种方法每次进行出队操作都要移动2次栈中的全部数据

而对于第二种方法实现的队列，如果连续进行入队或者出队操作，则不需要移动2个栈中的数据，能一定程度上提高效率。

三、进一步优化

可以看出，_stack1和_stack2中全部元素（或者说，全部元素-1）转移的次数越少，程序的执行效率就越高。

还有一种方法可以进一步减少_stack1和_stack2中全部元素交换的次数：

出队：

检测_stack2是否为空：

若为空，则将_stack1中的元素依次弹出并压入_stack2中，

若不为空，则弹出_stack2中栈顶的元素

入队：

将元素压入_stack。

可以看出，这种实现方式入队永远是从_stack2中弹出元素，出队永远是向_stack1中压入元素

而只有当入栈时检测到_stack2为空时，才执行2个栈之间全部元素的转移。

用如下的图能更形象地表示：

实现代码如下：

template<classT>classQueue{public:Queue():_size(0){}Queue(constQueue&que){_stack1=que._stack1;_size=que._size;}public:voidPush(constT&data){_stack1.Push(data);++_size;}voidPop(){if(_size==0)//异常{return;}if(_stack2.Empty()){Converse(_stack2,_stack1);}_stack2.Pop();--_size;}voidPrint(){_stack2.RePrint();_stack1.Print();}boolEmpty(){return(0==_size);}T&Front(){if(_stack2.Empty()){return_stack2.End();}else{return_stack2.Top();}}T&Back(){return_stack1.Top();}size_tSize(){return_size;}protected:voidConverse(Stack<T>&dst,Stack<T>&src){while(!src.Empty()){dst.Push(src.Top());src.Pop();}}protected:Stack<T>_stack1;Stack<T>_stack2;size_t_size;};

四、总结

这里一共提供了3种方法：