Queue 與設計題

介紹

#

設計題要你實作一個 class，每個方法都有時間複雜度的要求。解題的關鍵是先把每個操作需要什麼列出來，再挑能同時滿足的資料結構組合。

模板一：環狀佇列

#

用固定大小的陣列，加上 head（第一個元素的位置）和 count（元素數量），位置都對容量取模：

class CircularQueue:
    def __init__(self, k):
        self.buf = [0] * k
        self.head = self.count = 0

    def push(self, x):
        if self.count == len(self.buf):
            return False
        self.buf[(self.head + self.count) % len(self.buf)] = x
        self.count += 1
        return True

    def pop(self):
        if self.count == 0:
            return False
        self.head = (self.head + 1) % len(self.buf)
        self.count -= 1
        return True

主要參數說明：

#

• 用 head + count 而不是 head + tail 兩個指標：不用另外處理「空」和「滿」時兩個指標重疊的歧義。
• 最後一個元素在 (head + count - 1) % k（LC 622）。

模板二：多個來源交錯輸出

#

把每個來源放進一個 queue，輪到誰就從誰拿；拿完還有剩就放回 queue 尾端：

from collections import deque

q = deque(iter(v) for v in sources if v)     # 每個來源一個 iterator
def next_value():
    it = q.popleft()
    x = next(it)
    ...                                       # 還有剩就 q.append(it)

LC 281 是兩個來源的版本。用 queue 存「還沒用完的來源」，可以直接推廣到 k 個。

模板三：FIFO 配對 + 取消

#

兩邊各一個 queue，配對時兩邊各拿最早的一個。取消時不從 queue 中間刪除，只記到 canceled 集合，配對前再把隊頭已取消的丟掉（lazy deletion）：

while riders and riders[0] in canceled:
    canceled.discard(riders.popleft())

判斷「這個人還在不在等」要用 set，不要對 deque 用 in，那是 O(n)（LC 3829）。

模板四：用 stack 做 queue、用 queue 做 stack

#

• 兩個 stack 做 queue（LC 232）：push 進 inbox；outbox 空的時候才把 inbox 全部倒過去，均攤 O(1)。
• 一個 queue 做 stack（LC 225）：push(x) 之後把前面的 n - 1 個元素轉到尾巴，x 就在隊首。

已經寫過的設計題

#

常見錯誤

#

• 對 deque 或 list 用 in 判斷存在：O(n)。
• 環狀陣列的最後一個位置算錯，忘記減 1 再取模。
• 迭代器的 hasNext 有副作用：可以這樣寫，但要確保連續呼叫多次結果一樣。
• 用 list 直接當 stack 或用 pop(0) 當 queue：能過，但不是題目要的實作，pop(0) 也是 O(n)（LC 225、232）。

相關 LeetCode

#

• LC 622 Design Circular Queue
• LC 281 Zigzag Iterator
• LC 3829 Design Ride Sharing System
• LC 1290 Convert Binary Number in a Linked List to Integer
• LC 225 Implement Stack using Queues
• LC 232 Implement Queue using Stacks
• LC 387 First Unique Character in a String