上一篇，介紹了「堆疊」，這篇我們來介紹「佇列 Queue」！

他們的性質其實非常相似，我們來看看吧！

佇列 Queue

佇列是一個「先進先出」的資料結構。什麼意思呢？簡單來說，就是一個隊伍！去便利商店結帳時，如果你排得越前面，是不是就代表你會越早結帳，這個就是佇列的特性！

如果以物件來思考，佇列就是一個只支援 pushBack(), popFront(), getFront() 的資料結構。
因為佇列的增刪節點方式只有一種，因此習慣上會以 push() / enqueue(), pop() / dequeue() 來代替。

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

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

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

void Queue::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 Queue::pop() {
    if (head == NULL)
    {
        return -1;
    }
    int toBeReturn = head -> data;
    if (head -> next == NULL)
    {
        delete head;
        head = NULL;
        return toBeReturn; 
    }
    else 
    {
        SLLNode *tmp = head;
        head = tmp -> next;
        delete tmp;
        return toBeReturn; 
    }
}

環狀佇列

你有想過用陣列來實作佇列嗎？其實是可行的。
但是這會產生一個問題：當資料被 pop()，這個空間就不會再被使用了。因為資料會被新增在陣列最後，因此我們要想辦法改良，使空間不會被浪費，而解決方法就是使用「環狀佇列」。

環狀佇列的核心就是「模運算（%）」。
當 front 或 end 這兩個紀錄頭尾索引值的變數超過陣列大小時，我們對他做模運算（front % arrSize, end % arrSize）。如此就可以確保空間有被做適當的利用，且達到佇列的要求。

堆疊跟佇列是常用的資料結構，常常會搭配其他的資料結構使用，因此要熟悉。

下一篇，我們將介紹稍微進階的鏈結串列類別方法。