キュー (enqueue / dequeue) を実装する
割り込みされたら、その列は成立しない
窓口に整理券を持った人が 5 人並んでいます。ここでいちばんあとに来た人を先に呼んだら、苦情が出ます。列というのは 先に来た人から順に処理する という約束があるから成り立っています。
プリンタの印刷待ち、注文の処理待ち、メッセージの配送待ち。順番を守ることが仕様そのものになっている場面はいくらでもあります。この「先に入れたものが先に出る」並べ方を キュー と呼びます。
入るのは末尾、出るのは先頭
キューでは、追加と取り出しで触る場所が違います。新しく来た人は最後尾に付き、呼ばれるのは先頭にいる人です。
Python
waiting = []
waiting.append("整理券 12 番")
waiting.append("整理券 13 番")
print(waiting[0]) # 整理券 12 番 次に呼ばれるのはこの人
waiting.pop(0)
print(waiting) # ['整理券 13 番']append で末尾に追加し、pop(0) で先頭を取り出します。JavaScript なら push と shift です。配列の左端が古い人、右端が新しい人。この向きを最後まで崩さないことが、混乱しないコツです。
先頭を 1 人抜くと、全員が 1 つずつ詰める
配列で列を作ると、取り出しに手間がかかります。先頭の 1 つを抜いたあと、残り全員の位置が 1 つずつ前へずれるからです。
Python
waiting = list(range(100000))
waiting.pop(0) # 残り 99999 個を 1 つずつ前へ詰め直す追加は末尾なので一定時間で終わりますが、取り出しは並んでいる人数に比例します。数千件までなら気になりません。それ以上を高速に流したい場面では、両端を同じ速さで触れる専用の構造に置き換えます。
誰も並んでいない列から、呼び出す
行列がはけたあとに次の人を呼ぼうとすると、当然ながら誰もいません。
Python
waiting = []
waiting.pop(0)
# IndexError: pop from empty list空のときにどう振る舞うかは、仕様として決めておく必要があります。何もせず素通りするのか、エラーにするのか。決めないまま書くと、言語ごとの既定の振る舞い任せになり、あとから追いにくい不具合になります。
そしてもう 1 つ、取り出す側を間違えないことです。末尾から取ってしまうと、あとから来た人が先に呼ばれることになり、それはもう列ではありません。
要件
- operations の各要素は ['enq', N] (N は整数) か ['deq'] のいずれか
- 空キューに対する deq は何もせず無視する
- 戻り値は最終的なキュー状態を表す整数配列 (先頭が古い、末尾が新しい)
入出力例
queueOps([1], [["enq",5],["enq",3],["deq"]]) → [5,3]
queueOps([1,2], [["enq",3],["deq"],["deq"]]) → [3]
queueOps([1,2], [["deq"],["deq"],["deq"],["deq"]]) → []
queueOps([7,8,9], []) → [7,8,9]
queueOps([0], [["enq",1],["enq",2],["enq",3],["deq"]]) → [1,2,3]
queueOps([10,20], [["deq"],["deq"],["deq"],["enq",42]]) → [42]ヒント
編集 ゆめさく編集部