# 從零開始學Python (23) — 資料結構模組deque：旁人來來去去像行雲流水

#### Day 23 資料結構模組deque：旁人來來去去像行雲流水

註：本篇文章同步刊載於iT邦幫忙，為鐵人賽之系列文章。  
[https://ithelp.ithome.com.tw/articles/10247295](https://ithelp.ithome.com.tw/articles/10247295)

先來解一下上次的練習吧！  
我們唯一需要動的應該只有calculate的函式，  
當 p1 < p2 時，將兩個值交換即可。  
別忘了交換應該要連同Entry裡面的值都一起換(price1/price2)。

```python
*### calculate函式用來接受按鈕事件，取得商品價格及折扣方式，計算後輸出*  
def calculate():  
    *# 每次要計算時，都讓按鈕顯示計算哪一個折扣法*  
    btnstr.set('計算' + radiostr.get() + '中')  
    *# 用try...except...的方式來避免掉輸入的不是數字*  
    try:  
        choice = radiostr.get() *# radiobutton的選擇項*  
        p1 = int(price1.get())  
        p2 = int(price2.get())  
        if p1 <= 0 or p2 <= 0: *# 如果輸入<=0的數字也當成例外處理*  
            raise Exception()  
        if p1 < p2:  
            p1, p2 = p2, p1  
            price1.set(str(p1))  
            price2.set(str(p2))  
...(下面沒有變動XD)
```

我們今天要來談談deque的應用，  
我們前面已經在[第十一篇](https://ithelp.ithome.com.tw/articles/10243343)的部分提到過deque的用法，這篇主要要來補充deque作為queue時的常見狀況。

一般我們提到兩種資料結構：  
queue(佇列)或stack(堆疊)的概念，  
其實就是先進先出(FIFO, First-In-First-Out)或  
先進後出(First-In-Last-Out)的區別。

queue就好像排隊一樣，當然是先排的先被服務到(除非有人插隊XD)；  
stack則像是一疊文件一樣，假設你都拿最上面的，  
當老闆又往上放新的文件(工作)給你的時候，  
你再拿就會拿到最新放上去的囉！  
這兩者在不同的程式語言有時候會有不同的稱呼和變形，  
但本質是不變的。

那麼，什麼狀況下我們寫程式會容易用到queue(deque)呢?  
最常見的狀況是遇到一個Tree(樹)的問題的時候！  
那，什麼是樹呢？  
好問題！這個問題應該要用比較長的篇幅解釋，  
所以請讀者參閱拙作[從LeetCode學演算法的第十四篇](https://ithelp.ithome.com.tw/articles/10213276)，  
下面我們再繼續。

不囉嗦，我們直接上一道題目作為範例吧！  
上面的連結應該已經介紹過二元樹了，  
最簡單來說，一棵二元樹就是由根節點(root)，  
及左子樹(left tree)/右子樹(right tree)所構成。  
每個節點上有可能連結左右節點，  
也可能沒有連接，稱為NIL，在Python為None。  
如果我們今天想要按照一層一層順序來走遍整個樹，  
並分層記錄的話，該怎麼做呢？  
這個問題通常被稱為Level-order Traversal。(層序遍歷)  
讀者可以前往LeetCode的題目看更詳細的描述。  
[https://leetcode.com/problems/binary-tree-level-order-traversal/](https://leetcode.com/problems/binary-tree-level-order-traversal/)  
我們可以先走第一層，再走第二層，以此類推，  
那麼這中間走完第一層時，怎麼知道第二層有哪些節點呢？  
按順序的話，我們應該將第一層的每個節點的左節點/右節點，  
放入到一個可以按照放入的順序處理的資料結構，  
接著再從這個資料結構裡一個一個拿出來(這時候是第二層了!)，  
找每一個的左右節點，再放進去……  
咦？這個資料結構不就是queue嗎XD？

我們在解題和寫程式的時候，  
可以先把要怎麼做大略寫出來，  
再根據這個概念和做法，寫出具體的程式。

以這個問題來說，  
題目應該會給出這個二元樹的根節點root，  
接著要做的事情就如上面說的一樣，但我們需要一些細部的東西：

1. 開一個res(result)作為存放答案用的串列。
    
2. 我們先檢查root是否存在，有些題目壞壞的會給None，  
    如果不存在就直接回傳空的答案給它!
    
3. 將root放入我們檢查的資料結構(因為它是第一層)，我們先叫它q吧!
    
4. 開始一個迴圈，當q裡面還有節點時，代表還要繼續。
    
5. 我們先記下q裡面的個數(命名為cnt)，後面放進去q的都是下一層的節點。
    
6. 接著先設定一個level變數，用以記錄這層的節點值們。
    
7. 在裡面再開一個迴圈，這次直接指定跑cnt次，  
    這樣所有這層的節點都會被我們取出來。
    
8. 內層迴圈中，每次從q取出一個節點(popleft)，  
    將節點值(.value)append到level中，
    
9. 檢查左節點，如果不是None的話就將節點放到q裡。
    
10. 檢查右節點，做相同的事情XD
    
11. 內層迴圈結束後，這時候我們拿到一整層的節點值，  
    我們應該要將其append到res這個結果裡。
    
12. 最後全部處理完後，可以將res回傳。
    

好啦!經過上面的步驟，有沒有發現我們其實已經把程式寫完了呢？  
只要按著順序對照，應該可以順利寫出答案。

那麼，我們就來看看實際的做法：

```python
*# Definition for a binary tree node.*  
*# class TreeNode:*  
*#     def __init__(self, x):*  
*#         self.val = x*  
*#         self.left = None*  
*#         self.right = None*
```

```python
from collections import deque
```

```python
class Solution:  
    def levelOrder(self, root: TreeNode) -> List[List[int]]:  
        res = [] *# result，用以記錄結果*  
        if not root: return res *# 我們有提過，if not可以用來檢查東西是不是空的*  
        q = deque([root]) *# deque的初始化，要以list的形式放入*  
        while q: *# 當q還有節點(同樣這相當於檢查是不是空的)*  
            cnt = len(q) *# deque支援len的操作(取長度)*  
            level = [] *# 記錄每層的節點值*  
            for _ in range(cnt): *# _沒有特別意思，通常是當沒有要在迴圈內用到時可以使用*  
                n = q.popleft() *# popleft等於從deque的左邊取出，也就是queue的用法*  
                level.append(n.val) *# 取值*  
                if n.left: q.append(n.left) *# 將左節點放入q*  
                if n.right: q.append(n.right) *# 將右節點放入q*  
            res.append(level) *# 每層完成後，要將一整層的節點值list放到res中*  
          
        return res *# 回傳，結束！*
```

應該不算太難(吧)…?  
請務必要看完樹的那篇定義再來看這篇喲！  
總言之，deque作為queue使用時，主要會用popleft()跟append()來操作，  
同時它會適合按先後順序放入及取出的情況。

練習題目的話，  
讀者可以再嘗試看看LeetCode的另一題：  
101\. Symmetric Tree

那麼，我們就明天見囉！

\*\*工商時間：  
\*\*抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)  
在[**Python Taiwan的連結第100篇的文章**](https://www.facebook.com/groups/pythontw/permalink/10160354153893438/)底下，  
**公開分享到你的臉書、按讚該篇文章、並留言告訴我說，**  
**「你最喜歡這一整個系列的哪一篇？為什麼？」或  
「除了從LeetCode學演算法系列以外，  
你還想要看到關於什麼方向的文章？」**  
**超過20則留言的話**(有完成以上步驟的才算)，我們就抽一組  
**「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」  
課程的免費兌換券進行贈送！**

期限嘛…就延長到滿人數吧XDD (不然也沒辦法哈哈)

容筆者工商一下，  
**「從Leetcode學演算法｜進階篇」開放預購啦！  
這次選了40道難度加深的LeetCode題目，  
同樣也會細部解說對應的技巧及須要掌握的演算法！  
同時這次購買進階篇的話，  
額外還加贈「從Leetcode學演算法｜面試篇」**！  
當中包含了**面試準備須知分享**，**及訪談國內外不同經驗的工程師**，  
讓你不論是**想走前端/後端/一般軟工**或者是**想找國外的工作**，  
是**初學想轉職**還是**正在工作**，都能夠從中得到收穫呦！  
有興趣的朋友可以使用下面的早鳥優惠～  
**「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」**：  
[https://bit.ly/advleetcode](https://bit.ly/advleetcode)

**「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：**  
[https://bit.ly/allleetcode](https://bit.ly/allleetcode)

請幫我隨手點開下面的**SHOW EMBED**並按5個like～  
喜歡的話也可以幫我拍拍手～  
(按讚不用錢，感謝支持寫作~)

<iframe src="https://button.like.co/in/embed/desolve/button/" width="485" height="212"></iframe>