????用兩個棧模擬隊列的思想就是“倒水思想”，這里我們用自定義類型模擬出線性表，再用線性表做容器實現棧的數據結構，最后用棧來實現隊列，代碼如下：

#include<iostream> #include<string> #include<cassert> struct?__TrueType//類型萃取 {bool?Get(){return?true;} }; struct?__FalseType {bool?Get(){return?false;} };template?<class?_Tp> struct?TypeTraits {typedef?__FalseType???__IsPODType; };template?<> struct?TypeTraits<?bool> {typedef?__TrueType?????__IsPODType; };template?<> struct?TypeTraits<?char> {typedef?__TrueType?????__IsPODType; };template?<> struct?TypeTraits<?unsigned?char?> {typedef?__TrueType?????__IsPODType; };template?<> struct?TypeTraits<?short> {typedef?__TrueType?????__IsPODType; };template?<> struct?TypeTraits<?unsigned?short?> {typedef?__TrueType?????__IsPODType; };template?<> struct?TypeTraits<?int> {typedef?__TrueType?????__IsPODType; };template?<> struct?TypeTraits<?unsigned?int?> {typedef?__TrueType?????__IsPODType; };template?<> struct?TypeTraits<?long> {typedef?__TrueType?????__IsPODType; };template?<> struct?TypeTraits<?unsigned?long?> {typedef?__TrueType?????__IsPODType; };template?<> struct?TypeTraits<?long?long?> {typedef?__TrueType?????__IsPODType; };template?<> struct?TypeTraits<?unsigned?long?long> {typedef?__TrueType?????__IsPODType; };template?<> struct?TypeTraits<?float> {typedef?__TrueType?????__IsPODType; };template?<> struct?TypeTraits<?double> {typedef?__TrueType?????__IsPODType; };template?<> struct?TypeTraits<?long?double?> {typedef?__TrueType?????__IsPODType; };template?<class?_Tp> struct?TypeTraits<?_Tp*> {typedef?__TrueType?????__IsPODType; };template?<class?T>//自定義類型實現線性表 class?SeqList { public:SeqList():_size(0),_capacity(10),_array(new?T[_capacity]){memset(_array,?0,?sizeof(T)*_capacity);}SeqList(const?T?&x):_size(1),_capacity(10),_array(new?T[_capacity]){_array[0]?=?x;}SeqList(const?SeqList?&?x){_array?=?new?T[x._size];my_memcpy(_array,?x._array,?sizeof(T)*x._size);_capacity?=?x._size;_size?=?_capacity;}void?PushBack(const?T?&?x){_CheckCapacity();_array[_size++]?=?x;}void?PushFront(const?T?&?x){_CheckCapacity();for?(size_t?i?=?_size;?i?>?1;?i--){_array[_size]?=?_array[_size?-?1];}_size++;_array[0]?=?x;}void?PopBack(){_size--;}void?PopFront(){assert(_size);for?(size_t?i?=?0;?i?<?_size?-?1;?i++){_array[i]?=?_array[i?+?1];}_size--;}size_t?Size(){return?_size;}SeqList?&?operator?=?(SeqList??l){swap(_array,?l._array);swap(_size,?l._size);swap(_capacity,?l._capacity);return?*this;}~SeqList(){if?(_array){delete[]?_array;}}T&?operator?[]?(const?size_t?t){return?_array[t];} private:void?_CheckCapacity(){if?(_size?>=?_capacity){_capacity?*=?3;T?*?tmp?=?new?T[_capacity];memcpy(tmp,?_array,?sizeof(T)*_capacity);delete[]?_array;_array?=?tmp;}}void?my_memcpy(T*?dst,?const?T*?src,?size_t?size){if?(TypeTraits?<T>::__IsPODType().Get()){memcpy(dst,?src,?size*sizeof?(T));}else{for?(size_t?i?=?0;?i?<?size;?++i){dst[i]?=?src[i];}}}size_t?_size;size_t?_capacity;T?*_array; }; template?<class?T,typename?Contianer?=?SeqList<T>?>//適配器實現棧 class?Stack { public:void?Push(const?T?&?x){_con.PushBack(x);}void?Pop(){_con.PopBack();}size_t?Size(){return?_con.Size();}bool?Empty(){return?Size()?==?0;}T&top(){return?_con[Size()?-?1];} protected:Contianer?_con; }; template?<class?T,typename?container?=?Stack<T>?>//以棧為適配器，實現隊列 class?Queue { public:bool?Empty(){return?(_InStack.Empty()?&&?_OutStack().Empty());}size_t?Size(){return?_InStack.Size()?+?_OutStack.Size();}void?Push(const?T?&x){_InStack.Push(x);}void?Pop(){size_t?MoveCount?=?_InStack.Size()?-?1;for?(size_t?iCount?=?MoveCount;?iCount?>?0;?--iCount){T?temp?=?_InStack.top();_OutStack.Push(temp);_InStack.Pop();}_InStack.Pop();while?(false?==?_OutStack.Empty()){T?temp?=?_OutStack.top();_InStack.Push(temp);_OutStack.Pop();}}T&?Front(){return?_InStack.top();}T&?Back(){size_t?MoveCount?=?_InStack.Size()?-?1;for?(size_t?iCount?=?MoveCount;?iCount?>?0;?--iCount){T?temp?=?_InStack.top();_OutStack.Push(temp);_InStack.Pop();}T?ret?=?_InStack.top();while?(false?==?_OutStack.Empty()){T?temp?=?_OutStack.top();_Instack.Push(temp);_OutStack.Pop();}return?ret;}void?PrintQueue(){size_t?MoveCount?=?_InStack.Size();for?(size_t?iCount?=?MoveCount;?iCount?>?0;?--iCount){T?temp?=?_InStack.top();_OutStack.Push(temp);_InStack.Pop();}while?(false?==?_OutStack.Empty()){T?temp?=?_OutStack.top();_InStack.Push(temp);cout?<<?"<-"?<<?temp;_OutStack.Pop();}cout?<<?endl;} private:container?_InStack;container?_OutStack; };

????測試用例如下：

void?Test() {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();}

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

轉載于:https://blog.51cto.com/10743407/1761921

總結

以上是生活随笔為你收集整理的【干货】容器适配器实现两个栈模拟队列的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。