佇列

習題預習

1. 如何實現一個循環隊列？
2. 如何在低級別的環境中實現一個併發隊列？
3. 如何應用隊列來解決生產者-消費者問題？
4. 如何在Java中實現一個線程安全的隊列？
5. 在C++標準庫中，queue與deque的區別是什麼？

說明知識

Queue是一種資料結構，它遵循"FIFO"(First In First Out)的原則，也就是先進先出，最早被加入的元素會最早被取出。

舉例來說，當你在遊樂園排隊等候乘坐遊戲設施時，就像是一個Queue。當你到達排隊的地方時，你會加入隊伍的尾部，而當遊戲設施開始運作時，則會由隊伍最前端的人先進入遊戲中，後面的人會持續等候，直到他們輪到為止。

其他的例子也包括下載文件時的等待佇列、排隊等候取款機、網路購物車中貨品的支付序列等等。在程式設計中，Queue常常被用在需要按照順序處理相關任務或事件的場景，例如網路服務器的請求處理、多執行緒中的工作排程、事件處理器等等。

彙總重點

1. Queue是一種先進先出（FIFO）的資料結構，表示最先進入Queue的元素會先被取出。
2. Queue可以在頭和尾進行不同的操作：從尾端添加新元素，從頭部移除舊元素。
3. Queue可以被實現為一個陣列，或一個連結串列。
4. 與Stack相對，Queue通常是用於將元素按照一定次序進行處理，例如在作業系統中進行進程調度，傳遞消息等等。
5. Queue具有多種變體，例如帶有優先度的Queue，雙端Queue（Deque）等等。

知識測驗

1. 特定順序遍歷二叉樹（Medium）
   給定一個二叉樹和一個正整數k，按照以下步驟打印出所有節點：
2. 首先打印以根節點為開始的前k個節點。
3. 接著打印所有由前k個節點的子節點分支出去的節點。
4. 重複步驟2，直到沒有更多節點可以打印。
   例如，如果k為2，下圖中二叉樹的節點遍歷順序為：1，2，3，4，5，6。

答案: https://leetcode.com/problems/print-binary-tree-in-order-of-levels/

2. 循環鏈表的環（Medium）
   給定一個循環鏈表，查找並返回其中的環的起始節點。如果不存在環，則返回null。
   例如，下圖中的循環鏈表的環起始節點為3。

答案: https://leetcode.com/problems/linked-list-cycle-ii/

3. 正方形的填充（Medium）
   給定一個大小為N×N的矩陣和一個起始點，從起始點開始按照特定規則將矩陣中的所有位置填充為相同的值。該規則是：將矩陣中每個與起始點相鄰的位置的值改為起始點的值，直到所有相鄰的位置都已被填充。
   例如，下圖中5×5矩陣的起始點為(1,1)，填充後的矩陣如圖所示。

答案 : https://www.codewars.com/kata/rectangle-fill/train/python

4. 塊狀矩陣（Medium）
   給定一個大小為N×N的矩陣和一個坐標(x,y)和一個大小為k的正方形區域。將指定區域中的每個元素加上指定值p，並返回更新後的矩陣。
   例如，下圖中4×4矩陣的(x,y)坐標為(2,2)，k大小為2，p值為3，更新後的矩陣如圖所示。

答案: https://leetcode.com/problems/matrix-block-sum/

5. 充電器安排（Medium）
   給定一個由n個非負整數表示的陣列，表示在不同的位置上有一系列充電器。每個充電器都有一定的充電範圍，可以在指定的位置上充電器。請問至少需要安排多少個新的充電器，才能夠在能達到所有充電需求的前提下，最小化充電器的使用量。
   例如，下圖中線段表示充電器的充電範圍，黑點表示現有充電器的位置。最少需要安排2個新的充電器，位置分別在[1, 5] 和 [8, 12]，才能夠在達到所有充電需求的前提下，最小化充電器的使用量。

答案: https://leetcode.com/problems/minimum-number-of-refueling-stops/