上一篇講到堆疊這個資料結構，我們說他是單一開口，即「後進先出」。

那麼有沒有個資料結構提供兩個開口呢？
有！他就是今天的主題「佇列」。

假設你在7-11要結帳，你會怎麼做？
如果有其他人在等待結帳，你一定會先排到隊伍最後面。

什麼時候可以結帳呢？
一定是隊伍前面的人都離開隊伍完成結帳後，才輪到你。

排隊這件事就是生活中的「佇列」啦！

佇列介紹

佇列的概念是後進後出（LILO, Last In Last Out）、先進先出（FIFO, First In First Out）。

佇列只要使用一個列表就可以實作出來了，當然我們還需要幾個變數用來記錄他的特徵，例如：front, end, size。另外，為了提高可讀性，我們會將堆疊的行為包裝成函式，例如：push, pop

• size：回傳佇列的資料數量
• front：紀錄佇列最前端的資料索引值
• back：紀錄佇列最後端的資料索引值
• push(data)：新增資料
• pop()：移除資料

queue = []
size = 0
front = -1
back = -1

def push(data):
    if (front == -1):
        front = 0
    queue.append(data)
    back += 1
    size += 1

def pop():
    if (front != -1):
        front += 1
        size -= 1
        
def getFront():
    if front < 0:
        return None
    else:
        return queue[front]

如果稍微了解物件導向的概念，以上這個程式碼可以轉化成一個類別與類別方法，如此一個程式內就可以允許多個佇列同時運行。

不知道你有沒有發現一個問題？
當執行 pop() ，列表前方的空間就再也不會被使用到了！
不覺得空間被浪費嗎？
接著我們來改良一下這個佇列的寫法吧！

改良版佇列

改良版的佇列叫做「環狀佇列」。
簡單來說，將列表想像成一個圓環，如此就沒有空間會永遠不再被使用。

那要怎麼實作呢？核心概念就是「模運算mod」。
假設佇列最多同時出現 n 筆資料，即列表索引值為 0 ~ n-1

• 當 front 超過 n-1，則將 front 改為 front % n
• 當 back 超過 n-1，則將 back 改為 back % n

要特別注意的是列表大小要設的足夠大，其餘所有行為其實都相同，只是多了上述的判斷。

這樣我們就可以更完善利用空間。

未來我們提到「廣度優先搜尋 BFS」時，會再見到佇列。

下一篇開始，我們會介紹新的內建資料結構「字典 Dict」。