用兩個(gè)棧實(shí)現(xiàn)一個(gè)隊(duì)列

思路：

棧s1和棧s2，s1用來Push數(shù)據(jù)，s2用來Pop數(shù)據(jù)

入隊(duì)：數(shù)據(jù)直接壓入棧s1中

出隊(duì)：若s2為空，則把s1中除過最后一個(gè)壓入的元素全部移入s2中，然后彈出s1的棧頂元素

            若s2不為空，直接彈出s2的棧頂元素

#define _CRT_SECURE_NO_WARNINGS 1

#include<iostream>

#include<stack>

#include<assert.h>

using namespace std;

template<typename T>

class Queue

{

public:

                Queue()

                {

                                 //利用庫里面的stack的構(gòu)造函構(gòu)造s1和s2

                }

                Queue( const Queue & que)

                {

                                s1 = que.s1;

                                s2 = que.s2;

                }

                ~Queue()

                {

                                 //利用stack類來完成s1和s2的釋放

                }

                 void Push(const T&t)

                {

                                s1.push( t);

                }

                 void Pop()

                {

                                 assert(s1.size() != 0 || s2.size() != 0);

                                 if (s2.size() == 0)

                                {////把s1中除了棧底元素，其他全部push進(jìn)s2中

                                                 while (s1.size() != 1)

                                                {

                                                                s2.push(s1.top());  

                                                                s1.pop();      

                                                }

                                                s1.pop();

                                }

                                 else

                                {

                                                s2.pop();

                                }

                }

                 T& Front()  //讀取隊(duì)列的隊(duì)首元素

                {

                                 assert(s1.size() != 0 || s2.size() != 0);

                                 if (s2.size() != 0)

                                {

                                                 return s2.top();

                                }

                                 else

                                {

                                                 while (s1.size() != 1)

                                                {

                                                                s2.push(s1.top());

                                                                s1.pop();

                                                }

                                                 return s1.top();

                                }              

                }

                 T& Back()  //讀取隊(duì)列的隊(duì)尾元素

                {

                                 assert(s1.size() != 0 || s2.size() != 0);

                                 if (s1.size() != 0)

                                {

                                                 return s1.top();

                                }

                                 else

                                {

                                                 while (s2.size() != 1)

                                                {

                                                                s1.push(s2.top());

                                                                s2.pop();

                                                }

                                                 return s2.top();

                                }

                } 

                 bool Empty()    //判斷空

                {

                                 if (s2.size() == 0 && s2.size() == 0)

                                {

                                                 return true ;

                                }

                                 else

                                {

                                                 return false ;

                                }

                }

                 size_t Size()

                {

                                 return s1.size() + s2.size();

                }

              template<typename T> 

                 friend ostream &operator<<(ostream& _cout, const Queue <T>&que);

private:

                 stack<T > s1;

                 stack<T > s2;

};

template<typename T>

ostream& operator<<(ostream &_cout, const Queue <T>& que)

{

                 Queue<T >coutque(que);

                 _cout << "Queue:" ;

                 while (coutque.s2.size() > 0)

                {

                                 _cout << coutque.s2.top() << " ";

                                coutque.s2.pop();

                }

                 while (coutque.s1.size() > 0)

                {

                                coutque.s2.push(coutque.s1.top());

                                coutque.s1.pop();

                }

                 while (coutque.s2.size() > 0)

                {

                                 _cout << coutque.s2.top() << " ";

                                coutque.s2.pop();

                }

                 _cout << " " ;

                 return _cout ;

}

void Test()

{

                 Queue<int > que;

                que.Push(1);

                que.Push(2);

                que.Push(3);

                que.Push(4);

                que.Push(1);

                que.Push(2);

                que.Push(3);

                que.Push(4);

                cout << que << endl;

                 /*que.Pop();

                que.Pop();

                que.Pop();

                cout << que << endl;*/

                 /*int head1=que.Front();

                cout << head1<<endl;

                que.Pop();

                int head2 = que.Front();

                cout << head2<<endl;*/

                 /*int tail1 = que.Back();

                cout << tail1 << endl;*/

                 int ret=que.Size();

                cout << ret << endl;

}

int main()

{

                Test();

                 return 0;

}