第七の巻 スタックを作れ

中段 / 目安 30分

カメ師範が、洗い場に積まれた皿を指さしました。

「見よ。洗った皿を上へ上へと積んでおる。次に使うのはどれじゃ。一番下ではあるまい。一番上、つまり最後に置いた皿じゃ」

七本目の巻物には、こう書かれています。「皿を積むように、後から入れた物が先に出る器を、配列で作れ。push、pop、そして覗き見(peek)」

この器はスタックと呼ばれます。ブラウザの「戻る」も、関数を呼んだあとに元の場所へ帰れるのも、中身はこの皿の積み方です。今回は既製の器を使わず、配列だけで自分で作ります。

覚える操作は3つです。push は皿を一枚上に積む。pop は一番上の皿を取り出して器から減らす。peek は一番上を見るだけで、器は減らさない。この「減らす」と「減らさない」の違いが、この巻の要です。

もう一つ決めておくことがあります。空の器に pop や peek が来たらどうするかです。落ちて止まる器は使い物になりません。今回は empty という札を返す約束にします。

完成条件

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

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

操作は3種類です。

• push 数 — その数を器の一番上に積みます
• pop — 一番上を取り出して器から減らします。空なら何も減らさず empty を記録します
• peek — 一番上を見るだけで器は減らしません。空なら empty を記録します

pop と peek は、見た値を出た順に記録していきます。push は何も記録しません。

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

stack= の後ろは器に残った中身を下から上の順にスラッシュでつないだもの、out= の後ろは記録した値をカンマでつないだものです。どちらも空のときは - の一文字にします。上の例は push 3,push 5,pop,peek を処理した結果で、器には3だけが残り、pop で5、peek で3を見たという意味です。

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

進め方

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

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

配列のどちら側を「皿の一番上」と決めるかで、書きやすさが大きく変わります。末尾を上と決めると、積むのも取り出すのも末尾だけを触れば済みます。先頭を上と決めると、積むたびに全部をずらすことになります。同じスタックでも、置き方一つで手間が変わることを確かめてください。

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