註：本文同步刊載在Medium，若習慣Medium的話亦可去那邊看呦！

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

### 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的應用，
我們前面已經在第十一篇的部分提到過deque的用法，這篇主要要來補充deque作為queue時的常見狀況。

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

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

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

不囉嗦，我們直接上一道題目作為範例吧！
上面的連結應該已經介紹過二元樹了，
最簡單來說，一棵二元樹就是由根節點(root)，
及左子樹(left tree)/右子樹(right tree)所構成。
每個節點上有可能連結左右節點，
也可能沒有連接，稱為NIL，在Python為None。
如果我們今天想要按照一層一層順序來走遍整個樹，
並分層記錄的話，該怎麼做呢？
這個問題通常被稱為Level-order Traversal。(層序遍歷)
讀者可以前往LeetCode的題目看更詳細的描述。
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回傳。

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

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

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

from collections import deque

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

那麼，我們就明天見囉！