キュー (enqueue / dequeue) を実装する

割り込みされたら、その列は成立しない

窓口に整理券を持った人が5人並んでいます。最後に来た人を先に呼ぶと、先に待っていた人は納得できません。列は、先に来た人から順に処理するという約束で成り立っています。

プリンタの印刷待ち、注文の処理待ち、メッセージの配送待ちでも、この順序を使います。先に入れたものが先に出る入れ物をキューと呼びます。英語では FIFO、先入れ先出しです。追加を enqueue、取り出しを dequeue と呼びます。

入るのは末尾、出るのは先頭

新しく来た人は最後尾に付き、呼ばれるのは先頭の人です。配列の左端を古い人、右端を新しい人とすると、次の動きになります。

waiting = []
waiting.append("整理券12番")
waiting.append("整理券13番")
print(waiting[0])    # 整理券12番
waiting.pop(0)
print(waiting)       # ['整理券13番']

append は末尾に追加し、pop(0) は添字0、つまり先頭を取り出します。waiting[0] は見るだけで、取り出す操作ではありません。JavaScript の配列なら push と shift が対応します。末尾から取り出すと、後から来た人を先に呼ぶスタックの順序になります。

順序が同じでも、処理時間は変わる

配列に10万件ある状態で先頭を1件取り出すと、残る99999件を前へ詰めます。取り出しは件数に比例する O(n) です。末尾への追加は、容量を広げる回も含めて多数の操作を平均すると O(1) になります。

大量の待ち行列では、先頭の位置だけを進める方法や、Python の deque のように両端を効率よく触れる構造を使います。キューは順序の約束であり、必ず配列で作るという意味ではありません。

誰も並んでいないとき

空の列からは誰も取り出せません。Python の空の配列で pop(0) を呼ぶとエラーになります。受付では「待ちなし」と表示するなど、空の状態も扱います。新しく1件入れば、その1件が次に呼ばれる先頭です。

例題で確かめる

印刷ジョブが空のキューに31、32、33の順で届きます。1件印刷し、34が届いて、さらに1件印刷します。左を先頭として追います。

残るのは [33, 34] です。34が届いたあとも、先に待っていた32が先に印刷されます。