介紹完了四種基本增刪節點的類別方法，現在我們要將他們加以應用。
今天的目標是實作一個「堆疊 Stack」！

堆疊 Stack

堆疊是一個「後進先出」的資料結構。什麼意思呢？不妨想想罐裝的品客洋芋片，如果想拿到下層的洋芋片，是不是應該先取出上層的洋芋片呢？就是這個感覺。
如果以物件來思考，堆疊就是一個只支援 pushBack(), popBack(), getBack() 的資料結構。
因為堆疊的增刪節點方式只有一種，因此習慣上會以 push(), pop() 來代替。另外，我們想像的堆疊通常為直立的，因此 getBack() 會以 getTop() 來代替。

// 將鏈結串列的 head 設為私有變數，以確保外人無法觸及
// 想要取得堆疊中的資料，唯有透過 getTop()
class Stack
{
private:
    SLLNode *head;
public:
    Stack();
    bool isEmpty();
    void push(int); 
    int pop(); 
    int getTop();
};

Stack::Stack() { this -> head = NULL; }

bool Stack::isEmpty() { return this -> head == NULL; }

void Stack::push(int _data) {
    if (this -> head == NULL)
    {
        this -> head = new SLLNode(_data);
        this -> head -> next = NULL;
    }
    else 
    {
        SLLNode *cur = this -> head;
        while (cur && cur -> next != NULL) 
        {
            cur = cur -> next;
        }
        cur -> next = new SLLNode(_data);
    }
}

int Stack::pop() {
    if (head == NULL) 
        return -1;
    int toBeReturn;
    if (head -> next == NULL)
    {
        toBeReturn = head -> data;
        delete head;
        head = NULL;
    }
    else
    {
        SLLNode *cur = head;
        SLLNode *prev;
        while (cur && cur -> next != NULL)
        {
            prev = cur;
            cur = cur -> next;
        }
        toBeReturn = cur -> data;
        delete cur;
        prev -> next = NULL;
    }
    return toBeReturn;
}

雖然鏈結串列可以實作堆疊，但是當資料不回無限增加時，我們其實可以用一個陣列搭配一個變數 int top 去實作堆疊。不過，鏈結串列確實可以實作堆疊。

下一篇就來介紹堆疊的兄弟「佇列」！