0Pricing
Coding Interview Prep · レッスン

キューと collections.deque

両端から高速に push と pop を行います

「キューと collections.deque」はCoddyKit上の無料Coding Interview Prepレッスンです。 これはレッスン3/4です。 下記で完全なレッスンを無料で読むことができます。その後、ブラウザ内の組み込みコードエディタと24時間対応のAIチューターでハンズオン演習できます。 これはCoding Interview Prep学習パスの一部であり、ウェブとCoddyKitアプリ全体で進捗が同期されます。 Coding Interview Prepコースには全4レッスンが含まれています。

先入れ先出し

キューは、お店の行列のように、到着した順番で要素を処理します。先に入った要素が先に出ます。

リストを使わない理由

リストの先頭からポップすることもできますが、pop(0) は他のすべての要素を左に移動するため O(n) です。大きな入力には遅すぎます。

q = []
q.pop(0)  # O(n), avoid this

collections.deque を使う

collections の deque は両端キューで、両端からの追加と削除を O(1) で行えます。コンテストでまず使うべき構造です。

from collections import deque
q = deque()

末尾にエンキューする

リストと同じように、append で新しい要素を右端に追加します。ここがキューの末尾です。

q.append(1)
q.append(2)

先頭からデキューする

popleft で左端から最も古い要素を削除します。これは定数時間で実行され、正しい FIFO の動作になります。

first = q.popleft()  # returns 1

両端を利用できる

deque は appendleft と右端からの pop にも対応しています。この柔軟性により、1 つの構造をスタックとしてもキューとしても使えます。

q.appendleft(0)
last = q.pop()

ポップする前に確認する

空の deque から削除するとエラーが発生するため、ループでは while q で確認して安全に走査してください。

while q:
    x = q.popleft()

キューは BFS を支える

コンテストで最も一般的な用途は BFS です。始点ノードをエンキューし、先頭から取り出して隣接ノードを追加する処理を続けます。

小さな BFS の骨組み

このループはノードを層ごとに訪問します。各隣接ノードは追加され、後で到着した順番に処理されます。

while q:
    node = q.popleft()
    for nb in graph[node]:
        q.append(nb)

deque のサイズを制限する

maxlen を指定すると、deque が満杯になったときに最も古い要素を削除します。スライディングウィンドウや最近の履歴の追跡に最適です。

window = deque(maxlen=3)

1 つの構造で多くの役割を担う

deque は両端で高速だと覚えておきましょう。キュー、スタック、スライディングバッファが必要なときは、deque を使うと便利です。

確認問題

キューから先頭の要素を高速に削除する必要があります。どの選択肢が適切でしょうか。

まとめ：deque は高速なキュー

collections.deque について学びました。append と popleft による O(1) の FIFO、両端の利用、ウィンドウのための maxlen が特徴です。BFS の基盤となる構造です。🎯

よくある質問

「キューと collections.deque」レッスンは無料ですか？

はい。「キューと collections.deque」の完全なテキストはこのウェブで無料で読めます。インタラクティブに演習し（組み込みコードエディタと24時間対応のAIチューター）、Coding Interview Prepコースの残りをアンロックするには、CoddyKit PROにアップグレードしてください。 Coding Interview Prepコースには全4レッスンが含まれています。

「キューと collections.deque」で何を学びますか？

両端から高速に push と pop を行います ブラウザで直接実行するハンズオンコードでCoding Interview Prepを演習し、24時間対応のAIチューターがレッスンを進める中での質問に答えます。

Coding Interview Prepを始めるのに経験は必要ですか？

事前経験は必要ありません。CoddyKitのCoding Interview Prepは初級者から上級者向けに構成されているため、ここから始めるか最初から始めて、自分のペースで進むことができます。 これはレッスン3/4です。

「キューと collections.deque」レッスンにはどのくらい時間がかかりますか？

ほとんどのCoddyKitレッスンは約5～10分かかります。各レッスンはコンパクトでインタラクティブなので、着実に進歩し、ウェブとアプリ全体で正確に前回の場所から再開できます。

このCoding Interview Prepレッスンでコードを書いて実行できますか？

はい。すべてのCoding Interview Prepレッスンに組み込みコードエディタが含まれているため、ブラウザでリアルコードを書いて実行し、即座のAIフィードバックを取得できます。ローカル設定は不要です。

このコースのすべてのレッスン

  1. 括弧の対応確認に使うスタック
  2. 単調スタック: 次に大きい要素
  3. キューと collections.deque
  4. Deque によるスライディングウィンドウ最大値
← Coding Interview Prepに戻る