線性表（四） 棧、隊列

在介紹了線性表的兩種形式：順序表和連結清單後，我們接下來學習兩種特殊的受限制的線性表：棧（LIFO線性表）和隊列（FIFO線性表）。

棧

棧是限定僅在一端進行插入或删除操作的線性表。雖然這個限制減小了棧的靈活性，但是也使得棧更有效，更容易實作。棧還有一個名字，稱為LIFO（後進先出）線性表，意味着棧存儲和删除元素的順序與元素到達的順序相反。習慣上我們稱棧的可通路元素為棧頂元素(top)，元素插入棧稱為入棧(push)，删除元素稱為出棧(pop)。由于棧是一種特殊的線性表，是以棧的實作形式也有以下兩種：順序棧和鍊式棧，下文将對這兩種實作分别論述。

棧ADT

根據前面棧的簡介，我們很友善定義出棧的ADT：

template <typename E> class Stack
{
private:
    void operator =(const Stack&) {}
    Stack(const Stack&) {}

public:
    Stack() {}
    virtual ~Stack() {}
    virtual void clear() = 0;
    virtual void push(const E& it) = 0;
    virtual E pop() = 0;
    virtual const E& topValue() const = 0;
    virtual int length() const = 0;
};
           

順序棧

順序棧的實作，本質上是順序表實作的簡化。唯一重要的是，确定應該用數組的哪一端表示棧頂，顯然，為了減少棧操作的時間消耗，我們應該當棧中有n個元素時把位置n-1作為棧頂，即選用線性表的末尾作為棧頂。具體實作中，我們将top定義為表示棧中的第一個空閑位置，是以，空棧的top為0。根據top的定義，我們的push首先把一個值插入到棧頂位置，然後把top加1，同樣，pop首先把top減1，然後删除棧頂元素。

下面給出順序棧類的實作：

template <typename E> class AStack: public Stack<E>
{
private:
    int maxSize;
    int top;
    E *listArray;

public:
    AStack(int size=defaultSize)
    { maxSize = size; top = 0; listArray = new E[size]; }

    ~AStack() { delete [] listArray; }
    
    void clear() { top = 0; }
    
    void push(const E& it)
    {
        Assert(top != maxSize, "Stack is full");
        listArray[top++] = it;
    }

    E pop()
    {
        Assert(top != 0, "Stack is empty");
        return listArray[--top];
    }

    const E& topValue() const
    {
        Assert(top != 0, "Stack is empty");
        return listArray[top-1];
    }

    int length() const { return top; }
};
           

如何類比順序棧和順序表呢？我們可以發現，順序棧中的top簡直和順序表中的curr一毛一樣，元素的增删查都要通過它。事實上，這是因為top和curr的定義均為目前元素指針，理所當然我們要目前位置指針來進行對象操作了。由于數組是固定大小的，我們的增删查操作進行前要分别進行判滿和判空處理。還有一點需要注意，由于是順序棧，是以在對象的銷毀和表的複原操作上非常簡單，銷毀我們隻需要delete掉給listArray配置設定的數組空間，clear我們僅需要将top指針指向0号位置即可。包括删除操作，我們并不需要真正去修改要删除結點的存儲内容，反正我們有棧頂封着，上面那些元素隻是單純的記憶體單元，存儲的是啥不幹我們的順序棧的事。

順便一提，當需要實作多個棧時，可以充分利用順序棧單向延伸的特性。是以，可以使用一個數組來存儲兩個棧，每個棧從各自的端點向中間延伸，如下圖，這樣浪費的空間就會減少。但是，隻有當兩個棧的空間需求有相反的關系時，這種方法才奏效。即最好一個棧增長時另一個棧縮短。當需要從一個棧中取出元素放入另一個棧中時，這種方法非常有效。

鍊式棧

相應的，鍊式棧的實作是對連結清單實作的簡化。我們之前介紹過的可利用空間表實際上就是一個鍊式棧的執行個體。其元素隻能在表頭進行插入和删除。由于空棧或隻有一個元素的棧都不需要特殊情形的結點，是以它不需要表頭結點。

下面我們給對外連結式棧的實作：

template <typename E> class LStack: public Stack<E>
{
private:
    Link<E>* top;
    int size;

public:
    LStack(int sz=defaultSize)
    { top = NULL; size = 0 }

    ~LStack() { clear(); }

    void clear() // 這裡本人有些不解，咋複原和銷毀成一樣了呢？
    {
        while(top != NULL)
        {
            Link<E>* temp = top;
            top = top->next;
            delete temp;
        }
        size = 0;
    }

    void push(const E& it)
    {
        top = new Link<E>(it, top);
        size++;
    }

    E pop()
    {
        Assert(top != NULL, "Stack is empty");
        E it = top->element;
        Link<E>* ltemp = top->next;
        delete top;
        top = ltemp;
        size--;
        return it;
    }

    const E& topValue() const
    {
        Assert(top != 0, "Stack is empty");
        return top->element;
    }

    int length() const { return size; }
};
           

這裡我們做一個小小的總結：類的形式實作資料結構極大的友善了我們将資料結構進行類比以及對資料結構元件的統一管理，我們編寫每一個操作時隻要思考private修飾符下方的成員屬性如何維護以及判空和判滿即可，十分友善記憶和編寫。我們同時采用繼承ADT類的形式，規範了資料結構的接口，使得編寫的代碼既不會遺漏什麼關鍵操作，又符合一定的規範，友善使用者使用。

另外我們可以看到，鍊式棧的增删查操作的具體代碼簡直就是連結清單的複刻，對此我們可以對比學習，統一記憶。

注：我們本例代碼中使用到的Link類沿用了之前我們在單連結清單定義時Link類的定義，如果讀者有疑問請點選這裡

棧的應用

大多數情況下，我們看不到棧的最廣泛應用，這就是大多數程式設計語言運作環境都有的子程式調用。子程式調用是通過把有關子程式的必要資訊(包括傳回位址、參數、局部變量)存儲到一個棧中實作的，這塊資訊稱為活動記錄(activation record)；子程式調用把活動記錄壓入棧，每次從子程式中傳回時，就從棧中彈出一個活動記錄。下面從編譯器的角度，以遞歸階乘函數為例解釋這一過程。（如果學過彙編或者計算機組成原理PC指針與寄存器這塊，下面這段話将不難了解）

考慮用4來調用fact：用

來表示程式調用fact的指令所在的位址。是以，在第一次調用fact時，必須把位址

存放到棧中，并且把4傳遞給fact。程式接下來再對fact進行一次遞歸調用，這次參數值變為3。把做這次調用的指令位址記為

，該位址

連同n的目前值(4)被儲存到棧中，此時調用函數fact所用的輸入參數3。

利用類似的方式，程式遞歸調用直至到達了fact的初始狀态(n=1)，此時将不會有活動記錄入棧，将開始展開遞歸：每一次從fact傳回都将彈出棧所儲存的n的目前值，以及函數調用所傳回的位址。通過存儲n的目前值，使得fact的傳回值逐次累積，并且傳回最後結果。（對這一問題的深刻了解有助于遞歸程式的設計，因為遞歸程式設計中最難的部分就是思考如何儲存和傳回結果——劉汝佳紫書）

從上述過程可以看出，由于需要生成一個活動記錄，并把它壓入棧中，一個遞歸程式的時空開銷是十分巨大的，是以多數情況下，我們在享用遞歸程式帶來的代碼簡潔性清晰性的同時，還要思考這種遞歸的設計與我們設計程式的目标是否相符。

ps：最後附上兩道比較經典的棧的基礎題鐵軌 矩陣鍊乘，分别考察了棧的後進先出特性，以及棧在解析表達式中的應用。

隊列

同棧一樣，隊列也是一種受限的線性表。它又被稱作FIFO(先進先出)線性表，對應的基本操作為入隊(enqueue)和出隊(dequeue)，這一點我們可以很直覺的和真實生活中的排隊現象做類比，話不多說，上ADT定義：

template <typename E> class Queue
{
private:
    void operator =(const Queue&) {}
    Queue(const Queue&) {}

public:
    Queue() {}
    virtual ~Queue() {}
    virtual void clear() = 0;
    virtual void enqueue(const E&) = 0;
    virtual E dequeue() = 0;
    virtual const E& frontValue() const = 0;
    virtual int length() const = 0;
};
           

同樣的對于隊列，我們也有順序隊列和鍊式隊列。出于操作友善，對于隊列我們需要兩個指針front和rear分别訓示隊列和隊尾。

順序隊列

順序隊列的實作我們與正常的線性結構略微有些不同。實體上，其存儲仍為一個數組，邏輯上則展現為環形隊列（其具體原因涉及到隊列的移動問題，為了減少每次入隊出隊時帶來的不必要的移動時間成本，故我們采用這種形式）。

所幸的是，有些數論基礎的人會發現，環形隊列的數組下标的循環可以對應到數的循環問題，在數論中就是将數取模。是以我們使用取模操作，可以很容易實作順序隊列邏輯上的循環。（在這種方法中，數組中的位置編号從0到size-1，size-1被定義為位置0，即等價于位置size%size的前驅）

和所有順序線性表類似，我們還需要考慮的是順序隊列的判空和判滿問題。我們不妨假設front存儲隊列中隊首元素的位置号，rear存儲隊尾元素的位置号。如果front和rear位置相同，則表示隊列中隻有一個元素；當rear比front小1則表示隊列為空。那麼我們在來考慮隊滿的情況，當一個有n個可用位置的隊列含有n個元素，如果隊首元素在位置0，則隊尾元素一定在位置size-1。我們發現，這種定義下我們并不能區分隊滿和隊空的情況。那麼是不是修改定義就可以解決問題呢？我們吃驚的發現，無論我們如何修改front和rear的定義，都不能解決這一問題。這就涉及到鴿籠原理了，如果數組有n個位置，則隊列中最多可以存儲n個元素(可以定義為front和rear之差)，但隊列卻可以有n+1種不同的狀态(有0到n個元素)。也就是說，如果我們用front的rear的相對值來定義隊列的狀态，則必然有兩種不能區分。

ps：這一問題讓部落客聯想到動态規劃問題求解中狀态的定義問題，求解一個動态規劃問題的關鍵首先在于能不能設計出一種能不重不漏描述解狀态空間的狀态定義。

對于環形隊列的沖突，我們可以采用以下兩種解決方案：

1.用一個布爾變量來訓示隊列是否為空

2.設定數組的大小為n+1，但是隻需存儲n個元素。

本篇給出的代碼示例采用第二種形式。

template <typename E> class AQueue: public Queue<E>
{
private:
    int maxSize;
    int front;
    int rear;
    E *listArray;

public:
    AQueue(int size=defaultSize)
    {
        maxSize = size+1; 
        // 輸入是使用者想要的隊列最大長度size，maxSize則是實際開的數組大小，十分人性化
        rear = 0; front = 1;
        listArray = new E[maxSize];
    }

    ~AQueue() { delete [] listArray; }
    
    void clear() { rear = 0; front = 1; }
    
    void enqueue(const E& it)
    {
        Assert(((rear+2) % maxSize) != front, "Queue is full");
        rear = (rear+1) % maxSize;
        listArray[rear] = it;
    }

    E dequeue()
    {
        Assert(length() != 0, "Queue is empty");
        E it = listArray[front];
        front = (front+1) % maxSize;
        return it;
    }

    const E& frontValue() const
    {
        Assert(length() != 0, "Queue is empty");
        return listArray[front];
    }

    int length() const
    { return ((rear+maxSize) - front + 1) % maxSize; }
};
           

注意：順序隊列的指針移動不是簡單的加1，還要取模，因為它是環狀的。（rear = (rear+1) % maxSize; front = (front+1) % maxSize;）;我們還需注意，enqueue中判滿的方法是(rear+2) % maxSize ?=  front;

鍊式隊列

鍊式隊列的實作不過是對連結清單實作做了簡單的修改，為了簡化實作方式和相關操作，我們同樣可以使用一個頭結點。在初始化的時候，front和rear同時指向頭結點，之後front總是指向頭結點，而rear指向隊列的尾結點。enqueue和dequeue分别使用的是rear和front指針(腦補一下排隊場景就不會弄混)。下面是代碼是實作：

template <typename E> class LQueue: public Queue<E>
{
private:
    Link<E>* front;
    Link<E>* rear;
    int size;

public:
    LQueue(int sz = defaultSize)
    { front = rear = new Link<E>(); size = 0; }

    ~LQueue()
    { clear(); delete front; }

    void clear()
    {
        while(front->next != NULL) // 這樣之後隊列為空，隻剩下一個頭結點，裡面内容為啥不重要
        {
            rear = front;
            delete rear;
            front = front->next;
        }
        rear = front;
        size = 0;
    }

    void enqueue(const E& it)
    {
        rear->next = new Link<E>(it, NULL);
        rear = rear->next;
        size++;
    }

    
    E dequeue()
    {
        Assert(size != 0, "Queue is empty");
        E it = front->next->element;
        Link<E>* ltemp = front->next;
        front->next = ltemp->next; // 此處要特别注意，别寫成front = front->next;
                                   // 删除的是第一個隊列元素，而front是頭結點，不為任何元素
        if(rear == ltemp) rear = front; // 删除的時候一般都要特别判斷删除末尾元素（類比連結清單）
        delete ltemp;
        size--;
        return it;
    }

    
    const E& frontValue() const
    {
        Assert(size != 0, "Queue is empty");
        return front->next->element;
    }

    int length() const { return size; } // 源代碼此處有一個virtual，我不是很了解
};
           

注：鍊式隊列的實作中，clear和dequeue函數可以關注一下，略微有些不同尋常。

ps：對于隊列及其應用還想加深一下的讀者可以看一下并行程式模拟這道題，用到了雙端隊列以及隊列在管理程序方面的作用。