用兩個棧實現(xiàn)一個隊列——7

   用兩個棧實現(xiàn)一個隊列，并實現(xiàn)兩個函數(shù)appendTail和deleteHead，分別完成在隊列尾部插入結(jié)點和在隊列頭部刪除結(jié)點的功能。

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

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

而需要在隊列尾部插入結(jié)點就往stack1中壓入數(shù)據(jù)：

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

程序如下：

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

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

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

    //當要刪除隊列頭部的數(shù)據(jù)的時候
    void deleteHead()
    {   
        //先要判斷棧2中是否有數(shù)據(jù)，如果有就直接取出棧頂?shù)脑兀藭r就為隊首的數(shù)據(jù)
        if(!_stack2.empty())
        {
            _stack2.pop_back();
        }
        else//若棧2為空，則需要將棧1中的數(shù)據(jù)調(diào)換到棧2中，以保證先進棧1的數(shù)據(jù)放在棧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;
    }
     
 //為了觀察方便，這里定義一個打印隊列的函數(shù)，這個函數(shù)其實也就是在完成兩個棧實現(xiàn)隊列的過程   
    void print_queue()
    {
    //這里要注意的是不能直接使用對象的成員變量stack1和stack2，因為這樣會更改對象的數(shù)據(jù)，而
    //我們只是需要打印數(shù)據(jù)并不希望更改它，因此可以使用vector庫中的拷貝構(gòu)造函數(shù)再構(gòu)造出
    //兩個臨時棧
        vector<T> tmp1(_stack1);
        vector<T> tmp2(_stack2);

        cout<<"head ";
        if(tmp2.empty())//當棧2為空的時候需要將棧1的數(shù)據(jù)挪到棧2再取出
        {
            while(!tmp1.empty())
            {
                tmp2.push_back(tmp1.back());
                tmp1.pop_back();
            }
            while(!tmp2.empty())
            {
                cout<<tmp2.back()<<" ";
                tmp2.pop_back();
            }
        }
        else
        {
        //當棧2不為空的時候先取出棧2的數(shù)據(jù)，然后再將棧1的數(shù)據(jù)放入棧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;
}

因為上面的隊類是模板類，因此實現(xiàn)了代碼復(fù)用，隊中的數(shù)據(jù)可以為任意類型；

運行程序：

《完》