キュー

キューは後ろに追加し、前から取り出す先入れ先出し（FIFO）の構造です。enqueue で追加し、dequeue で取り出します。到着順が取り出し順になります。

コーヒーの列なら新しい客は後ろに並び、先頭から注文します。スケジューラー、メッセージバッファー、印刷待ち、幅優先探索は、この規則で待つ仕事を管理します。

キューの仕組み

enqueue(val) は後ろに val を追加し、dequeue() は前の要素を削除して返します。この実装は有界です。すでに max 個あれば Queue Full、空から取り出せば Queue Empty を送出します。検査は表示コードにもあり、拒否された追加は状態を変えません。

スタックは同じ端で出し入れし、キューは反対の端を使います。片方の端を変えるだけで FIFO と LIFO が入れ替わります。

表示コードは通常の Python リストと pop(0) を使います。残る全要素を左へずらすため、取り出しは O(n) です。これは FIFO の条件ではなく実装の費用です。リングバッファーは配列上で先頭・末尾インデックスを循環させ、collections.deque も両端を O(1) で扱えます。

操作をステップで追う

既定は空、容量 8 です。入力パネルで実行します。

1. enqueue(3)：[3]。先頭と末尾は同じ要素。
2. enqueue(7)：[3, 7]。
3. enqueue(1)：[3, 7, 1]。
4. dequeue()：最初に来た 3 を返し、[7, 1]。
5. dequeue()：7 を返し、[1]。
6. dequeue()：1 を返し、[]。

既定デモはここで終わります。さらに取り出すと Queue Empty となり、状態は変わりません。3、7、1 という到着順で出るのは、このトレースだけの偶然ではなく規則です。

画面の FRONT は最初のセル、BACK は最後のセルを指します。先頭が左へ出ると、残りが一マス左に動きます。ヘッダーの size、front、back も各段階で更新され、上の状態列に対応します。

時間・空間計算量

FIFO は順序を定めます。費用は保存方法で決まります。

リストと deque は待機する n 要素の保存に O(n) の空間を使います。容量 C の固定長リングバッファーは C 個の枠をすべて先に確保するので、待機数にかかわらず O(C) です。

境界ケース

• 満杯への追加：max を検査して Queue Full を送出。有界キューはバックプレッシャーにも使う。スライダー上限 10 は画面幅の制約。
• 空からの取り出し：このレッスンでは例外。事前検査か例外処理が必要。空が通常の制御フローなら、API によっては番兵値を返す。
• 一要素：先頭と末尾が一致し、一回の取り出しで空になる。
• 補充せず取り出す：到着順に空まで進み、その次がアンダーフロー。

よくある間違い

• pop(0) を定数時間と思う。 要素の移動が必要です。規模が大きいなら collections.deque を検討します。
• 後ろから取り出す。 エラーにならなくてもスタックとなり、FIFO が失われます。
• 優先度付きキューを普通のキューと同じと思う。 優先度順に処理し、よく使う実装はヒープです。到着順を保証しません。
• 二つのスタックの間で毎回移し替える。 出力スタックが空の時だけ補充すれば償却 O(1)。毎回搬送すると O(n) になります。