用两个栈模拟队列的思想就是“倒水思想”，这里我们用自定义类型模拟出线性表，再用线性表做容器实现栈的数据结构，最后用栈来实现队列，代码如下：

#include<iostream>#include<string>#include<cassert>struct__TrueType//类型萃取{boolGet(){returntrue;}};struct__FalseType{boolGet(){returnfalse;}};template<class_Tp>structTypeTraits{typedef__FalseType__IsPODType;};template<>structTypeTraits<bool>{typedef__TrueType__IsPODType;};template<>structTypeTraits<char>{typedef__TrueType__IsPODType;};template<>structTypeTraits<unsignedchar>{typedef__TrueType__IsPODType;};template<>structTypeTraits<short>{typedef__TrueType__IsPODType;};template<>structTypeTraits<unsignedshort>{typedef__TrueType__IsPODType;};template<>structTypeTraits<int>{typedef__TrueType__IsPODType;};template<>structTypeTraits<unsignedint>{typedef__TrueType__IsPODType;};template<>structTypeTraits<long>{typedef__TrueType__IsPODType;};template<>structTypeTraits<unsignedlong>{typedef__TrueType__IsPODType;};template<>structTypeTraits<longlong>{typedef__TrueType__IsPODType;};template<>structTypeTraits<unsignedlonglong>{typedef__TrueType__IsPODType;};template<>structTypeTraits<float>{typedef__TrueType__IsPODType;};template<>structTypeTraits<double>{typedef__TrueType__IsPODType;};template<>structTypeTraits<longdouble>{typedef__TrueType__IsPODType;};template<class_Tp>structTypeTraits<_Tp*>{typedef__TrueType__IsPODType;};template<classT>//自定义类型实现线性表classSeqList{public:SeqList():_size(0),_capacity(10),_array(newT[_capacity]){memset(_array,0,sizeof(T)*_capacity);}SeqList(constT&x):_size(1),_capacity(10),_array(newT[_capacity]){_array[0]=x;}SeqList(constSeqList&x){_array=newT[x._size];my_memcpy(_array,x._array,sizeof(T)*x._size);_capacity=x._size;_size=_capacity;}voidPushBack(constT&x){_CheckCapacity();_array[_size++]=x;}voidPushFront(constT&x){_CheckCapacity();for(size_ti=_size;i>1;i--){_array[_size]=_array[_size-1];}_size++;_array[0]=x;}voidPopBack(){_size--;}voidPopFront(){assert(_size);for(size_ti=0;i<_size-1;i++){_array[i]=_array[i+1];}_size--;}size_tSize(){return_size;}SeqList&operator=(SeqListl){swap(_array,l._array);swap(_size,l._size);swap(_capacity,l._capacity);return*this;}~SeqList(){if(_array){delete[]_array;}}T&operator[](constsize_tt){return_array[t];}private:void_CheckCapacity(){if(_size>=_capacity){_capacity*=3;T*tmp=newT[_capacity];memcpy(tmp,_array,sizeof(T)*_capacity);delete[]_array;_array=tmp;}}voidmy_memcpy(T*dst,constT*src,size_tsize){if(TypeTraits<T>::__IsPODType().Get()){memcpy(dst,src,size*sizeof(T));}else{for(size_ti=0;i<size;++i){dst[i]=src[i];}}}size_t_size;size_t_capacity;T*_array;};template<classT,typenameContianer=SeqList<T>>//适配器实现栈classStack{public:voidPush(constT&x){_con.PushBack(x);}voidPop(){_con.PopBack();}size_tSize(){return_con.Size();}boolEmpty(){returnSize()==0;}T&top(){return_con[Size()-1];}protected:Contianer_con;};template<classT,typenamecontainer=Stack<T>>//以栈为适配器，实现队列classQueue{public:boolEmpty(){return(_InStack.Empty()&&_OutStack().Empty());}size_tSize(){return_InStack.Size()+_OutStack.Size();}voidPush(constT&x){_InStack.Push(x);}voidPop(){size_tMoveCount=_InStack.Size()-1;for(size_tiCount=MoveCount;iCount>0;--iCount){Ttemp=_InStack.top();_OutStack.Push(temp);_InStack.Pop();}_InStack.Pop();while(false==_OutStack.Empty()){Ttemp=_OutStack.top();_InStack.Push(temp);_OutStack.Pop();}}T&Front(){return_InStack.top();}T&Back(){size_tMoveCount=_InStack.Size()-1;for(size_tiCount=MoveCount;iCount>0;--iCount){Ttemp=_InStack.top();_OutStack.Push(temp);_InStack.Pop();}Tret=_InStack.top();while(false==_OutStack.Empty()){Ttemp=_OutStack.top();_Instack.Push(temp);_OutStack.Pop();}returnret;}voidPrintQueue(){size_tMoveCount=_InStack.Size();for(size_tiCount=MoveCount;iCount>0;--iCount){Ttemp=_InStack.top();_OutStack.Push(temp);_InStack.Pop();}while(false==_OutStack.Empty()){Ttemp=_OutStack.top();_InStack.Push(temp);cout<<"<-"<<temp;_OutStack.Pop();}cout<<endl;}private:container_InStack;container_OutStack;};

测试用例如下：

voidTest(){Queue<int>q1;q1.Push(1);q1.Push(2);q1.Push(3);q1.Push(4);q1.Push(5);q1.Push(6);q1.PrintQueue();q1.Pop();q1.PrintQueue();}

如有什么不足或疑问，希望指教