從零開始學Python (23) — 資料結構模組deque：旁人來來去去像行雲流水
Day 23 資料結構模組deque：旁人來來去去像行雲流水
註：本篇文章同步刊載於iT邦幫忙，為鐵人賽之系列文章。
https://ithelp.ithome.com.tw/articles/10247295
先來解一下上次的練習吧！
我們唯一需要動的應該只有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，
接著要做的事情就如上面說的一樣，但我們需要一些細部的東西：
開一個res(result)作為存放答案用的串列。
我們先檢查root是否存在，有些題目壞壞的會給None，
如果不存在就直接回傳空的答案給它!將root放入我們檢查的資料結構(因為它是第一層)，我們先叫它q吧!
開始一個迴圈，當q裡面還有節點時，代表還要繼續。
我們先記下q裡面的個數(命名為cnt)，後面放進去q的都是下一層的節點。
接著先設定一個level變數，用以記錄這層的節點值們。
在裡面再開一個迴圈，這次直接指定跑cnt次，
這樣所有這層的節點都會被我們取出來。內層迴圈中，每次從q取出一個節點(popleft)，
將節點值(.value)append到level中，檢查左節點，如果不是None的話就將節點放到q裡。
檢查右節點，做相同的事情XD
內層迴圈結束後，這時候我們拿到一整層的節點值，
我們應該要將其append到res這個結果裡。最後全部處理完後，可以將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
那麼，我們就明天見囉！
**工商時間：
**抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)
在Python Taiwan的連結第100篇的文章底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話(有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！
期限嘛…就延長到滿人數吧XDD (不然也沒辦法哈哈)
容筆者工商一下，
「從Leetcode學演算法｜進階篇」開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈「從Leetcode學演算法｜面試篇」！
當中包含了面試準備須知分享，及訪談國內外不同經驗的工程師，
讓你不論是想走前端/後端/一般軟工或者是想找國外的工作，
是初學想轉職還是正在工作，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」：
https://bit.ly/advleetcode
「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/allleetcode
請幫我隨手點開下面的SHOW EMBED並按5個like～
喜歡的話也可以幫我拍拍手～
(按讚不用錢，感謝支持寫作~)
