第八の巻 キューを作れ

中段 / 目安 30分

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

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

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

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

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

この一点の違いで、何が変わるのかを手で確かめるのがこの巻の狙いです。今回の完成済みの枠組みと前の巻を比べ、取り出す側の違いを確認してください。驚くほど少ないはずです。そして、その少ない行が世界を分けています。

完成条件

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

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

enq 3,enq 5,deq,front

操作は3種類です。

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

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

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

queue=5 out=3,5

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

引数には余分な空白や空の操作が入ることがあります。解析はひな形に用意しています。

進め方

ひな形の「課題」と書かれた部分から始めてください。初期化や補助処理は完成済みです。手が止まったらヒントを開けます。ヒントは3段階で、①方針、②使う構文、③部分解の順に出ます。ヒントは必要に応じて使い、書いた処理を自分で追えることを目標にします。

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

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

head が指す有効な範囲

操作の解析、enqueue、空判定、記録と残りの整形の枠組みは完成済みです。書くのは、空でないときの deq（dequeue）と front の2か所です。前の回の解析処理を書き直す必要はありません。

配列が [11, 22, 33]、head が 1 なら、有効な行列は [22, 33] です。取り出したら head は 2 となり、有効な行列は [33] です。配列には 11 と22が残っていますが、先頭より前は読みません。head が追加済みの個数に達したら空です。

別の題材として、読み終えたページの位置を進めます。保存済みの配列を詰め直さず、次に読む位置だけを変えます。

Python

pages = [101, 102, 103]
cursor = 1
current = pages[cursor]
cursor += 1

JavaScript

const pages = [101, 102, 103];
let cursor = 1;
const current = pages[cursor];
cursor++;

TypeScript

const pages: number[] = [101, 102, 103];
let cursor: number = 1;
const current: number = pages[cursor];
cursor++;

Java

int[] pages = {101, 102, 103};
int cursor = 1;
int current = pages[cursor];
cursor++;

dequeue は今の先頭の値を記録してから位置を進めます。front は記録だけで位置を進めません。記録の書き方は前回と同じです。ひな形の仮の「未実装」の記録を置き換えてください。入力は記載した3種類の操作だけで、数は整数です。空白と空の操作は既存コードが除きます。

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. 切り出した操作の前後の余分な空白を取り除くこと
11. ひな形の補助処理と出力整形を使い、空でないときの deq と front だけを書くこと
12. 入力は記載した3種類の操作だけで、数は整数です。空白と空の操作は既存コードが除きます