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

目錄（Table of Contents）

[TOC]

---

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

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

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

佇列（Queue）
===

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


Image Source：[Python Stack and Queue - Javatpoint](https://www.javatpoint.com/python-stack-and-queue)


Image Source：[Python Stack and Queue - Javatpoint](https://www.javatpoint.com/python-stack-and-queue)

上圖為 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(堆疊) 資料結構實作 | 愛喝咖啡 Ｘ 咖啡程式](https://lovedrinkcafe.com/python-stack-data-structure/)

將資料插入堆疊裡面的動作稱為堆入（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，是不是很簡單呢？

總結
===

1. 佇列（Queue）：
* 佇列是一種先進先出（FIFO）的資料結構，資料從一端插入（enqueue）並從另一端取出（dequeue）。這種結構類似於現實中的排隊情形。
* 可用 Python 的 list 實作佇列，insert(0, data) 用於插入資料，而 pop() 用於取出資料。
* Python 的 queue 模組內建了 Queue 類別，使用 put() 方法插入資料，get() 方法取出資料。
2. 堆疊（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） |

復原操作就是常聽到的 ctrl + Z，就是一種堆疊的應用，比如說在文件編輯器上打上任何字，等同於把字堆入堆疊當中，想要復原時再把它取出來。

參考資料
===

[用python 實作Queue(dequeue , enqueue) | by jack_DL | Information_Fun | Medium](https://medium.com/%E8%B3%87%E5%B7%A5%E7%AD%86%E8%A8%98/%E7%94%A8python-%E5%AF%A6%E4%BD%9Cqueue-dequeue-enqueue-e7f31da9543a)

[Python Stack and Queue - Javatpoint](https://www.javatpoint.com/python-stack-and-queue)

[【Python】Stack(堆疊) 資料結構實作 | 愛喝咖啡 Ｘ 咖啡程式](https://lovedrinkcafe.com/python-stack-data-structure/)

書籍：演算法：圖解邏輯思維+ Python 程式實作王者歸來(第三版)