用兩個隊列實作棧

使用兩個隊列實作一個棧 

這個棧的聲明如下：

template<typename T>

class Stack_by_queue

{

    public:

        Stack_by_queue(){};

        ~Stack_by_queue(){};

        void append_tail(const T& node);

        T delete_head();

        void Show_Stack(void);//從棧頂依次向棧低顯示輸出資料

    protected:

    private:

        queue<T> queue1;

        queue<T> queue2;

}; 

分析：棧的特性是先進後出，舉一個序列1,2,3,4來說，我們試着往一個queue1裡面push進去，這時候queue1的隊頭是1，隊尾是4，這時候要實作delete_head的話，對應的棧應該删除4，對于queue1的隊尾，前面的1,2,3，都是不需要的。 

實作dalete_head解決方法就是，依次彈出1,2,3并且壓入queue2中，queue1裡面隻儲存4，這時候要delete_head的話，對queue1進行pop操作就行了，然後queue1為空（注意這個狀态）,然後我要繼續delete_head,這個時候也是按照上面的思路，将queue2的1,2依次彈出，壓入queue1裡面，知道剩下最後一個隊尾元素3，将它pop掉就行了！這時候的狀态是queue1不為空，queue2為空。 

實作append_tail的話也容易。注意上面的删除頭以後的兩種狀态其實可以可以歸結為一種，那就是其中一個queue為空，另一個可以為空（這個時候模拟的stack就是空），或者不為空，append_tail來說，隻需往非空的queue裡面添到隊尾就行了，若是都為空，随便選一個即可 

#include <queue>
#include <iostream>
using namespace std;
template<typename T>
class Stack_by_queue
{
    public:
        Stack_by_queue(){};
        ~Stack_by_queue(){};
        void append_tail(const T& node);
        T delete_head();
        void Show_Stack(void);
    protected:
    private:
        queue<T> queue1;
        queue<T> queue2;
};
template<typename T>
void Stack_by_queue<T>::Show_Stack(void)
{
    queue<T> Q1(queue1);
    queue<T> Q2(queue2);
    T tmp;
    cout<<"\n this is Show_Stack!從棧頂到棧底顯示資料\n";
    while(!Q1.empty() || !Q2.empty())
    {
           if(Q1.empty() && !Q2.empty())
        {
            //2->1
            if (Q2.size() < 1)
            {
                return ;
            }
            while(Q2.size() != 1)
            {
                tmp = Q2.front();
                Q2.pop();
                Q1.push(tmp);
            }
            cout<<Q2.front()<<"  ";
            Q2.pop();
        }
        if(!Q1.empty() && Q2.empty())
        {
            //1->2
            if (Q1.size() < 1)
            {
                return ;
            }
            while(Q1.size() != 1)
            {
                tmp = Q1.front();
                Q1.pop();
                Q2.push(tmp);
            }
            cout<<Q1.front()<<"  ";
            Q1.pop();

        }
    }

}
//保證在所有的過程中，至少隊列有一個是空的
template<typename T>
T Stack_by_queue<T>::delete_head()
{
    T tmp;
    if(queue1.empty() && !queue2.empty())
    {
        //2->1
        if (queue2.size() < 1)
        {
        return -1;
        }
        while(queue2.size() != 1)
        {
            tmp = queue2.front();
            queue2.pop();
            queue1.push(tmp);
        }
        tmp = queue2.front();
        queue2.pop();
        return tmp;
    }
    if (!queue1.empty() && queue2.empty())
    {
        //1->2
        T tmp;
        if (queue1.size() < 1)
        {
            return -1;
        }
        while(queue1.size() != 1)
        {
            tmp = queue1.front();
            queue1.pop();
            queue2.push(tmp);
        }
        tmp = queue1.front();
        queue1.pop();
        return tmp;
    }
    else
        return -1;
}
template<typename T>
void Stack_by_queue<T>::append_tail( const T& node )
{
    //保證有一隊列為空，若全為空，則隊空,任選一個隊列就行
    if (queue1.empty() && !queue2.empty())
        queue2.push(node);
    if (!queue1.empty() && queue2.empty())
        queue1.push(node);
    if (queue1.empty() && queue2.empty())
        queue1.push(node);
    else
        return;
}
int main()
{
    Stack_by_queue<char> my_stack;
    my_stack.append_tail('a');
    my_stack.append_tail('b');
    my_stack.append_tail('c');
    my_stack.Show_Stack();


    my_stack.delete_head();
    my_stack.delete_head();
    my_stack.Show_Stack();

    my_stack.append_tail('d');
    my_stack.append_tail('e');
    my_stack.Show_Stack();

    my_stack.delete_head();
    my_stack.Show_Stack();

    my_stack.append_tail('f');
    my_stack.Show_Stack();
}
/**************************
運作結果：

 this is Show_Stack!從棧頂到棧底顯示資料
c  b  a
 this is Show_Stack!從棧頂到棧底顯示資料
a
 this is Show_Stack!從棧頂到棧底顯示資料
e  d  a
 this is Show_Stack!從棧頂到棧底顯示資料
d  a
 this is Show_Stack!從棧頂到棧底顯示資料
f  d  a


***************************/