第八の巻 キューを作れ

中段 / 目安 30分

カメ師範が、ハレノヒ珈琲の前にできた行列を顎で指しました。

「あそこで、後から来た者が先に珈琲を受け取ったら、どうなる。喧嘩じゃ。世の中の多くの器は、皿のようには積まん。先に並んだ者から先に出す。それが正直な器よ」

八本目の巻物には、こうあります。「ハレノヒ珈琲の行列を見よ。先に並んだ者が先に出る。あの正直な器を作れ。enqueue、dequeue」

この器はキューと呼ばれます。印刷の順番待ちも、メッセージの配達も、世界は行列でできています。

前の巻で作ったスタックと、形は驚くほど似ています。配列を用意し、入れて、出す。違うのはどちら側から出すか、ただ一点です。スタックは入れた側から出しました。キューは反対側から出します。

この一点の違いで、何が変わるのかを手で確かめるのがこの巻の狙いです。前の巻の答えを開いて、変えなければならない行がいくつあるかを数えてみてください。驚くほど少ないはずです。そして、その少ない行が世界を分けています。

完成条件

runQueue という関数を1つ定義してください。どの言語で解いても関数名は runQueue にしてください。Python でも snake_case ではなく、この綴りのまま使います。

引数は1つ、操作を並べたカンマ区切りの文字列です。たとえば次の形です。

操作は3種類です。

• enq 数 — その数を行列の最後尾に並ばせます
• deq — 行列の先頭を取り出して器から減らします。空なら何も減らさず empty を記録します
• front — 先頭を見るだけで器は減らしません。空なら empty を記録します

deq と front は、見た値を出た順に記録していきます。enq は何も記録しません。

全部の操作を終えたら、次の形の1つの文字列を返してください。

queue= の後ろは器に残った中身を先頭から最後尾の順にスラッシュでつないだもの、out= の後ろは記録した値をカンマでつないだものです。どちらも空のときは - の一文字にします。上の例は enq 3,enq 5,deq,front を処理した結果です。同じ操作の並びをスタックで処理すると out=5,3 になりました。同じ入力から違う答えが出る、そこがこの巻の見どころです。

引数の文字列の前後には余分な空白が入ることがあります。1つずつ切り出したあとに整えてください。

進め方

白紙から書いてください。手が止まったらヒントを開けます。ヒントは3段階で、①方針、②使う構文、③部分解の順に出ます。1つも開けずに通せたら、その問題は自分のものです。

開かずに10分粘って進まないなら、①だけ開けてください。粘る時間そのものには価値がありません。価値があるのは、自分で書いた行が動いた瞬間です。

先頭を取り出すたびに、残り全部を1つずつ前へ詰め直すやり方でも答えは合います。ただし行列が長くなると、その詰め直しが重くのしかかります。先頭がどこかを指す番号を1つ持っておけば、詰め直さずに済みます。答えが合ったあとで、自分がどちらを書いたか見直してみてください。師範が第九の巻で問うのは、まさにその差です。

1. 関数名は4言語すべてで runQueue にすること(Python も snake_case にしない)
2. 引数はカンマ区切りの操作文字列1つ
3. 既製のキュー型を使わず、配列だけで組み立てること
4. enq は数を行列の最後尾に並ばせ、何も記録しないこと
5. deq は行列の先頭を取り出して器から減らし、その値を記録すること
6. front は先頭を見るだけで器を減らさず、その値を記録すること
7. deq と front が空の器に来たら、器を変えず empty を記録すること
8. 戻り値は「queue=残った中身 out=記録」の形の文字列で、残りは先頭から最後尾へスラッシュ区切り、記録はカンマ区切り
9. 残りも記録も、空のときは半角ハイフン1文字にすること
10. 切り出した操作の前後の余分な空白を取り除くこと