【Python基礎教學】佇列 & 堆疊【part-15】

哈囉大家好，很感謝你點進本文章，我是一名高中生，是電腦社社團的社長，由於我並不是 Python 這方面非常精通的專家，所以若文章有些錯誤請見諒，也可向我指正錯誤。另外本文章的用意是作為電腦社社團的教材使用而編寫的。

上次我們談到鏈結串列資料結構的概念，上次的 Python 實作上面作者將其定位為進階教學，不過本次所講的資料結構為佇列、堆疊這兩種，那他們的概念其實都蠻基礎蠻簡單的，在實作上也沒有像鏈結串列那麼複雜。

接下來，讓我們進入正題：

佇列（Queue）

佇列（Queue），是一種線性的資料結構，具有先進先出（first in first out：FIFO）的特徵，特色為從一端插入資料至佇列（enqueue），然後在從另一端讀取資料（dequeue）。

Image Source：Python Stack and Queue - Javatpoint

上圖為 enqueue，表示插入資料進入佇列裡面，我們可以看到那個 D，在佇列中插入資料一定是從一端插入進去的。

下圖為 dequeue，表示在佇列中取出資料，我們看到 A，也是從一端中取出來。

看到這裡，你是不是覺得這像是什麼東西呢？是的沒錯，就是「排隊」等餐點的機制，因此 Queue 也稱為列隊、隊列的意思，簡單來說就是一個排好隊的隊伍。

欸，那這個佇列其實不一定要從左邊插入哦，其實你左右兩邊都可以，不過要注意的是，插入的這一端就已經被「插入」給佔用掉了，而取出資料的一端就必須要在插入的對面，以符合先進先出的原則。

那麼接下來就讓我們進入到 python 實作吧！

Python 實作

在 Python 中實作佇列，我們可以使用 list 來達成這個效果。enqueue 能夠用 list.insert(0,data) 來達成，而 dequeue 可以使用 list.pop() 方法。

class Queue():
    def __init__(self):
        self.queue = []

    def enqueue(self, data):
        self.queue.insert(0, data)

    def dequeue(self):
        if self.queue:
            return self.queue.pop()
        return "queue is empty" 

q = Queue()
q.enqueue(1)
q.enqueue(2)
q.enqueue(3)
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())
print(q.dequeue())

dequeue 方法主要是判斷佇列是否存在或是裡面元素不為空，不為空的話就從最後一個索引開始抽取，為空的話就回傳 “queue is empty”。

佇列模組

在 python 中可以直接引入 queue 模組，然後在模組能夠直接使用 Queue() 物件。

from queue import Queue

q = Queue()
for i in range(3):
    q.put(i)

while not q.empty():
    print(q.get())

堆疊（stack）

堆疊在我們之前講解遞迴時有稍微帶過他的基本原理，總之就是字面上意思，如果忘記的話各位可以回去翻遞迴那一篇。

堆疊（stack）也是一個線性資料結構，能夠由下往上堆積資料，就好比想像成你在上地科課的時候，老師教過一個定律叫做疊置定律，它是一種判斷事物年代久遠的方法，越下層的事物年代就越久遠，然後慢慢堆積上來。

Image Source：【Python】Stack(堆疊) 資料結構實作 | 愛喝咖啡Ｘ咖啡程式

將資料插入堆疊裡面的動作稱為堆入（push），堆進去堆疊裡面，肯定是由下往上嘛，如果我們要取出資料，那也因為堆疊的關係，只能從上面慢慢拿，所以堆疊具有 LIFO（last in first out）先進後出的特徵。

註：每個程式語言的遞迴式呼叫就是使用堆疊的原理。

Python 實作

在 Python 實作堆疊，我們同樣也可以使用 list 來進行這個動作。那接下來我們會用到以下兩種方法：

append()：在末端加入資料（符合堆疊原理，就像是在一個杯子裡面不斷丟東西，丟一丟最後索引還是一樣在後面）
pop()：刪除末端資料（最先進去的會疊到最下面，所以索引為 0，後面堆到上面來的索引會增加）

a = []
for i in range(5):
    a.append(i)
print(*a)
for i in range(5):
    print(a.pop())

以上是一個使用列表來達成簡易的堆疊程式碼。

那麼接下來讓我們像上面的範例一樣，自建一個類別來對 Stack 進行相關的操作：

class Stack():
    def __init__(self):
        self.stack = []

    def push(self, data):
        self.stack.append(data)

    def pop(self):
        return self.stack.pop()

stack = Stack()
data = [1,2,3,4,5]
for i in data:
    stack.push(data)
    print(f"Put {i} in stack")

print(f'The stack length : {len(stack.stack)}')

那堆疊實作的部分差不多就是這樣XD，是不是很簡單呢？

總結

佇列（Queue）：
- 佇列是一種先進先出（FIFO）的資料結構，資料從一端插入（enqueue）並從另一端取出（dequeue）。這種結構類似於現實中的排隊情形。
- 可用 Python 的 list 實作佇列，insert(0, data) 用於插入資料，而 pop() 用於取出資料。
- Python 的 queue 模組內建了 Queue 類別，使用 put() 方法插入資料，get() 方法取出資料。
堆疊（Stack）：
- 堆疊是一種先進後出（LIFO）的資料結構，資料像疊放的物品一樣，從上方堆入（push），並只能從上方取出（pop）。
- 可用 Python 的 list 來實作堆疊，append() 方法用於插入資料，而 pop() 方法用於取出資料。
- 也可自建 Stack 類別，push() 用於將資料加入堆疊，pop() 用於移除資料。

屬性	佇列（Queue）	堆疊（Stack）
結構類型	線性資料結構	線性資料結構
插入方式	從一端插入（enqueue）	從上方堆入（push）
取出方式	從另一端取出（dequeue）	從上方取出（pop）
資料進出順序	先進先出（FIFO：First In First Out）	先進後出（LIFO：Last In First Out）
現實類比	排隊等候	疊放的物品
Python 基本實作	用 `list.insert(0, data)` 和 `list.pop()`	用 `list.append(data)` 和 `list.pop()`
內建模組	`queue.Queue`	`collections.deque` 或自訂類別
應用情況	點餐等候系統、伺服器請求處理	遞迴、復原操作（Undo Operation）