キューの実装とdeque
Pythonのdequeでキューを構築し、循環キューを実装して、単調dequeを使ったスライディングウィンドウの最大値を求めます。
「キューの実装とdeque」はCoddyKit上の無料DSA Interview Prepレッスンです。 これはレッスン2/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはDSA Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 DSA Interview Prepコースには全4レッスンが含まれています。
キューデータ構造
キューは、先入れ先出し（FIFO）のデータ構造です。最初に enqueue された要素が最初に dequeue されます。店のレジ待ちの列をイメージしてください。基本操作は、enqueue（末尾に追加）と dequeue（先頭から削除）です。キューを効率的にするには、どちらも O(1) でなければなりません。
Python のリストをキューとして使うのは簡単そうですが、適切ではありません。list.pop(0) は、すべての要素を移動させるため O(n) かかります。正しい選択肢は collections.deque です。これは O(1) の appendleft、append、popleft、pop を提供します。
from collections import deque
queue = deque()
# Enqueue (add to rear)
queue.append(10)
queue.append(20)
queue.append(30)
print('Queue:', queue) # deque([10, 20, 30])
# Peek front
print('Front:', queue[0]) # 10
# Dequeue (remove from front)
print('Dequeued:', queue.popleft()) # 10
print('Queue after:', queue) # deque([20, 30])deque を使った Queue クラス
deque を名前付きの操作を持つ Queue クラスでラップし、面接官が期待する形に合わせます。内部では、enqueue が append を呼び出し、dequeue が popleft を呼び出します。peek 操作は、要素を削除せずに queue[0] を読み取ります。
from collections import deque
class Queue:
def __init__(self):
self._data = deque()
def enqueue(self, val):
self._data.append(val)
def dequeue(self):
if self.is_empty():
raise IndexError('dequeue from empty queue')
return self._data.popleft()
def peek(self):
if self.is_empty():
raise IndexError('peek at empty queue')
return self._data[0]
def is_empty(self):
return len(self._data) == 0
def __len__(self):
return len(self._data)
q = Queue()
q.enqueue(1); q.enqueue(2); q.enqueue(3)
print(q.peek()) # 1
print(q.dequeue()) # 1
print(len(q)) # 2キューを使った BFS
キューの典型的な応用は、幅優先探索（BFS）です。ルートを enqueue し、キューが空でない間、ノードを dequeue して処理し、未訪問の隣接ノードを enqueue します。ノードをレベルごとに処理するため、BFS は重みなしグラフの最短経路を自然に見つけられます。キューに入っているノードは、常に高々2つの隣接レベルに属します。
from collections import deque
def bfs(graph, start):
visited = {start}
queue = deque([start])
order = []
while queue:
node = queue.popleft()
order.append(node)
for neighbour in graph[node]:
if neighbour not in visited:
visited.add(neighbour)
queue.append(neighbour)
return order
graph = {0:[1,2], 1:[0,3,4], 2:[0,5], 3:[1], 4:[1], 5:[2]}
print(bfs(graph, 0)) # [0, 1, 2, 3, 4, 5]循環キュー（LeetCode 622）
LeetCode 622「循環キューの設計」：末尾が先頭につながる、固定容量のキューを実装します。サイズ k の配列と、head、tail という2つのポインタを使います。tail で enqueue し、head で dequeue し、位置は k を法として計算します。count 変数によって、空の場合と満杯の場合を区別します（それ以外では、どちらも k を法とすると head == tail になります）。
class MyCircularQueue:
def __init__(self, k):
self.data = [0] * k
self.head = 0
self.tail = 0
self.count = 0
self.k = k
def enQueue(self, value):
if self.isFull(): return False
self.data[self.tail] = value
self.tail = (self.tail + 1) % self.k
self.count += 1
return True
def deQueue(self):
if self.isEmpty(): return False
self.head = (self.head + 1) % self.k
self.count -= 1
return True
def Front(self):
return -1 if self.isEmpty() else self.data[self.head]
def Rear(self):
return -1 if self.isEmpty() else self.data[(self.tail - 1) % self.k]
def isEmpty(self): return self.count == 0
def isFull(self): return self.count == self.k
cq = MyCircularQueue(3)
print(cq.enQueue(1), cq.enQueue(2), cq.enQueue(3)) # True True True
print(cq.enQueue(4)) # False (full)
print(cq.Rear()) # 3
print(cq.isFull()) # True
print(cq.deQueue()) # True
print(cq.enQueue(4)) # True単調デックによるスライディングウィンドウの最大値
LeetCode 239「スライディングウィンドウの最大値」：サイズ k の各ウィンドウについて、最大要素を求めます。総当たり法の計算量は O(n*k) です。O(n) の方法では、インデックスを格納する単調減少 dequeを使います。新しい要素ごとに、ウィンドウの外側に出たインデックスを先頭から削除し、値が小さいインデックスを末尾から削除します（それらが将来のどのウィンドウでも最大値になることはないためです）。先頭には常に最大値が入ります。
from collections import deque
def maxSlidingWindow(nums, k):
dq = deque() # stores indices, decreasing values
result = []
for i, n in enumerate(nums):
# Remove indices outside window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove smaller elements from back
while dq and nums[dq[-1]] < n:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return result
print(maxSlidingWindow([1,3,-1,-3,5,3,6,7], 3))
# [3, 3, 5, 5, 6, 7]キューに list ではなく deque を使う理由
Python の list.pop(0) は、残りのすべての要素を1つ左へ移動する必要があるため、先頭要素の削除に O(n) かかります。n 回の挿入と n 回の削除では、合計 O(n²) になります。collections.deque は固定サイズのブロックからなる双方向連結リストであり、popleft はポインタを調整するだけなので O(1) です。10^5 個のノードを持つグラフで BFS を行う場合、O(n) と O(n²) の違いは、100 ms と 100 秒の違いになります。
import timeit
n = 10000
# Using list (O(n) per popleft)
list_time = timeit.timeit(
stmt='q = list(range(n)); [q.pop(0) for _ in range(n)]',
globals={'n': n}, number=10
)
# Using deque (O(1) per popleft)
from collections import deque
deque_time = timeit.timeit(
stmt='q = deque(range(n)); [q.popleft() for _ in range(n)]',
globals={'n': n, 'deque': deque}, number=10
)
print(f'List: {list_time:.4f}s')
print(f'Deque: {deque_time:.4f}s')
print(f'Speedup: {list_time / deque_time:.1f}x')二分木のレベル順走査（LeetCode 102）
LeetCode 102「二分木のレベル順走査」：すべてのノードの値をレベルごとに返します。キューを使い、各レベルの開始時にキューのサイズを記録します。これは、そのレベルにあるノード数です。記録した数と同じだけノードを dequeue し、それらの値を集めながら子ノードを enqueue します。キューが空になるまで繰り返します。
from collections import deque
class TreeNode:
def __init__(self, val=0, left=None, right=None):
self.val = val
self.left = left
self.right = right
def levelOrder(root):
if not root:
return []
result = []
queue = deque([root])
while queue:
level = []
level_size = len(queue)
for _ in range(level_size):
node = queue.popleft()
level.append(node.val)
if node.left: queue.append(node.left)
if node.right: queue.append(node.right)
result.append(level)
return result
root = TreeNode(3, TreeNode(9), TreeNode(20, TreeNode(15), TreeNode(7)))
print(levelOrder(root)) # [[3], [9, 20], [15, 7]]heapqを使った優先度付きキュー
Pythonのheapqモジュールは最小ヒープ（優先度付きキュー）を提供します。最小の要素が常に先にデキューされます。heapq.heappush(h, item)はO(log n)で要素を追加し、heapq.heappop(h)はO(log n)で最小要素を削除します。Dijkstra法やtop-k問題のようなタスクでは、heapqを通常のキューの代わりに使用できます。
import heapq
pq = []
heapq.heappush(pq, 5)
heapq.heappush(pq, 1)
heapq.heappush(pq, 3)
heapq.heappush(pq, 2)
print('Min:', heapq.heappop(pq)) # 1
print('Min:', heapq.heappop(pq)) # 2
print('Min:', heapq.heappop(pq)) # 3
# Tasks with priorities
tasks = [(2, 'send email'), (1, 'fix bug'), (3, 'write docs')]
heapq.heapify(tasks)
while tasks:
priority, task = heapq.heappop(tasks)
print(f'Priority {priority}: {task}')ウォールペーパーパターン：Word Ladderにおけるキュー
LeetCode 127「Word Ladder」では、辞書に含まれる単語だけを使い、1文字ずつ置換してある単語を別の単語に変換するための最小回数を求めます。これは、1文字だけ異なる単語同士を辺で結んだグラフとしてモデル化できます。このグラフに対してBFSを行うと最短経路（最小ステップ数）が求まり、計算量はO(n * L²)です。ここでnは辞書のサイズ、Lは単語の長さです。
from collections import deque
def ladderLength(beginWord, endWord, wordList):
word_set = set(wordList)
if endWord not in word_set:
return 0
queue = deque([(beginWord, 1)])
visited = {beginWord}
while queue:
word, steps = queue.popleft()
for i in range(len(word)):
for ch in 'abcdefghijklmnopqrstuvwxyz':
new_word = word[:i] + ch + word[i+1:]
if new_word == endWord:
return steps + 1
if new_word in word_set and new_word not in visited:
visited.add(new_word)
queue.append((new_word, steps + 1))
return 0
print(ladderLength('hit', 'cog', ['hot','dot','dog','lot','log','cog'])) # 5両端キューとしてのdeque
collections.dequeは両端キュー（deque）です。両端のどちらからでも効率的に要素を追加・削除できます。先頭にはappendleftとpopleft、末尾にはappendとpopを使用します。これにより、dequeはFIFOキュー（appendright + popleft）としても、LIFOスタック（append + pop）としても機能します。スライディングウィンドウの最大値を求める処理では両端を使い、左側から古いインデックスを、右側から小さい値を削除します。
from collections import deque
dq = deque([3, 4, 5])
dq.appendleft(2) # add to front: [2,3,4,5]
dq.appendleft(1) # add to front: [1,2,3,4,5]
dq.append(6) # add to rear: [1,2,3,4,5,6]
print(dq.popleft()) # 1 (from front)
print(dq.pop()) # 6 (from rear)
print(list(dq)) # [2, 3, 4, 5]まとめ：キューとdequeとヒープの違い
問題に合ったツールを選択してください。FIFO処理やBFSには通常のキュー（deque）を使用します。スライディングウィンドウの最大値または最小値が必要な場合は単調dequeを使用します。単調dequeは、不要になった要素を削除してソート順の不変条件を維持します。順序に関係なく全体の最小値または最大値が必要な場合は、Dijkstra法やtop-k問題のように優先度付きキュー（heapq）を使用します。どのツールを、なぜ選ぶべきかを理解することは、面接で問われる重要なスキルです。
理解度チェック
このレッスンで扱ったData Structures & Algorithms — Coding Interview Prepの概念について、理解度を確認しましょう。
レッスンのまとめ
このレッスンでは、collections.dequeはO(1)のエンキューとデキューを提供するため、Pythonで正しいキュー実装になります。また、BFSはキューを使ってノードをレベルごとに処理し、重みなしグラフの最短経路を見つけます。さらに、単調減少dequeは、不要になったインデックスを削除することで、O(n)でスライディングウィンドウの最大値を求めます。次は、単調スタックパターンを詳しく見ていきます。
よくある質問
「キューの実装とdeque」レッスンは無料ですか？
はい。「キューの実装とdeque」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、DSA Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 DSA Interview Prepコースには全4レッスンが含まれています。
「キューの実装とdeque」で何を学びますか？
Pythonのdequeでキューを構築し、循環キューを実装して、単調dequeを使ったスライディングウィンドウの最大値を求めます。 ブラウザで直接実行するハンズオンコードでDSA Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。
DSA Interview Prepを始めるのに経験は必要ですか？
事前経験は必要ありません。CoddyKitのDSA Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン2/4です。
「キューの実装とdeque」レッスンにはどのくらい時間がかかりますか？
ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。
このDSA Interview Prepレッスンでコードを書いて実行できますか？
はい。すべてのDSA Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。
このコースのすべてのレッスン
- スタックの実装と応用
- キューの実装とdeque
- 単調スタックパターン
- スタックとキューの相互シミュレーション