用兩個棧實現一個隊列——7

   用兩個棧實現一個隊列，并實現兩個函數appendTail和deleteHead，分別完成在隊列尾部插入結點和在隊列頭部刪除結點的功能。

    棧的特點是“先進后出，后進先出”，而隊列的特點是“先進先出，后進后出”，因此可以想到只用一個棧是無法完成的，所以會需要兩個棧，先將輸入的數據都依次放入一個棧stack1中，但是先進去的數據會被壓在棧底，而棧底的數據是需要最先被取出的，可畫圖如下：

當要完成在隊列頭部刪除結點這就要用到另外一個棧stack2了，可以將第一個棧stack1的棧頂元素依次取出放進另外的棧stack2中，這樣stack1中的棧底元素就變成了stack2中的棧頂元素，當需要刪除隊列頭部結點的時候就可以pop出stack2的棧頂元素；

而需要在隊列尾部插入結點就往stack1中壓入數據：

也就是相當于，當stack2不為空的時候，要刪除隊列頭部的結點就從stack2的棧頂中取出數據，如果stack2為空的時候就將stack1中的數據全部都從棧頂取出依次放入stack2中，然后再取出stack2的棧頂元素；而要在隊列尾部插入結點的時候就直接往stack1里面push數據，這并不影響刪除隊列首部的結點，因為每次push數據都往stack1里面放，而當stack2不為空的時候從stack2中pop數據，二者并不影響；

程序如下：

#include <iostream>
#include <vector>
using namespace std;

template <class T>
class Queue
{
private:
    vector<T> _stack1;         //定義隊列的成員變量直接使用庫類vector
    vector<T> _stack2;
    
public:
    Queue()        //直接用類的默認構造函數，這里會自動調用庫vector中的構造函數創建兩個棧
    {}  

    //當需要向隊列尾部放數據的時候，直接在棧1中push數據就可以了
    void appendTail(T data)
    {   
        _stack1.push_back(data);
    }   

    //當要刪除隊列頭部的數據的時候
    void deleteHead()
    {   
        //先要判斷棧2中是否有數據，如果有就直接取出棧頂的元素，此時就為隊首的數據
        if(!_stack2.empty())
        {
            _stack2.pop_back();
        }
        else//若棧2為空，則需要將棧1中的數據調換到棧2中，以保證先進棧1的數據放在棧2的頂部
        {
            while(!_stack1.empty())
            {
                _stack2.push_back(_stack1.back());
                _stack1.pop_back();
            }
            if(!_stack2.empty())
                _stack2.pop_back();
            else
            {
                cout<<"the queue is empty..."<<endl;
                return;
            }   
        }
        cout<<"the new head is "<<_stack2.back()<<endl;
    }
     
 //為了觀察方便，這里定義一個打印隊列的函數，這個函數其實也就是在完成兩個棧實現隊列的過程   
    void print_queue()
    {
    //這里要注意的是不能直接使用對象的成員變量stack1和stack2，因為這樣會更改對象的數據，而
    //我們只是需要打印數據并不希望更改它，因此可以使用vector庫中的拷貝構造函數再構造出
    //兩個臨時棧
        vector<T> tmp1(_stack1);
        vector<T> tmp2(_stack2);

        cout<<"head ";
        if(tmp2.empty())//當棧2為空的時候需要將棧1的數據挪到棧2再取出
        {
            while(!tmp1.empty())
            {
                tmp2.push_back(tmp1.back());
                tmp1.pop_back();
            }
            while(!tmp2.empty())
            {
                cout<<tmp2.back()<<" ";
                tmp2.pop_back();
            }
        }
        else
        {
        //當棧2不為空的時候先取出棧2的數據，然后再將棧1的數據放入棧2再取出
            while(!tmp2.empty())
            {
                cout<<tmp2.back()<<" ";
                tmp2.pop_back();
                if(tmp2.empty())
                {
                    while(!tmp1.empty())
                    {
                        tmp2.push_back(tmp1.back());
                        tmp1.pop_back();
                    }
                }
            }
        }
        cout<<"tail"<<endl;
        }
};

int main()
{
    Queue<char> queue;
    queue.appendTail('a');
    queue.appendTail('b');
    queue.appendTail('c');
    queue.appendTail('d');
    queue.appendTail('e');
    queue.print_queue();

    queue.deleteHead();
    queue.deleteHead();
    queue.print_queue();

    queue.appendTail('f');
    queue.appendTail('g');
    queue.appendTail('h');
    queue.print_queue();

    return 0;
}

因為上面的隊類是模板類，因此實現了代碼復用，隊中的數據可以為任意類型；

運行程序：

《完》