第七の巻 スタックを作れ

中段 / 目安 30分

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

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

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

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

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

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

完成条件

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

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

push 3,push 5,pop,peek

操作は3種類です。

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

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

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

stack=3 out=5,3

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

引数には余分な空白や空の操作が入ることがあります。切り出しと空白の除去、空の操作の読み飛ばしはひな形に用意しています。

進め方

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

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

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

今回は取り出しと参照に絞る

操作の切り分け・空白除去・数への変換、push、空の器の判定、記録と最終整形の枠組みは完成済みです。課題は2か所です。空でないときの pop で末尾を減らして値を記録し、peek では末尾を見るだけで記録します。仮の「未実装」の記録を置き換えてください。

別の題材として、手札にカードを足し、末尾を読み、最後のカードを外す書き方を見ます。Python の append と JavaScript の push は末尾への追加、pop は末尾を取り除いてその値を返す配列の操作です。

Python

cards = [8]
cards.append(2)
last = cards[len(cards) - 1]
removed = cards.pop()

JavaScript

const cards = [8];
cards.push(2);
const last = cards[cards.length - 1];
const removed = cards.pop();

TypeScript

const cards: number[] = [8];
cards.push(2);
const last: number = cards[cards.length - 1];
const removed = cards.pop();

Java

int[] cards = new int[4];
int used = 1;
cards[0] = 8;
cards[used] = 2;
used++;
int last = cards[used - 1];
used--;
int removed = cards[used];

Java の配列は長さが固定です。top は有効な枚数で、末尾の位置は top - 1 です。枚数を減らしても配列の数値自体は残りますが、その位置は器の外と扱います。配列の容量は入力文字列の長さから確保済みです。

記録は Python の log.append(str(value))、JavaScript と TypeScript の log.push(String(value))、Java の log.append(value) で行います。str と String は数を文字列にする道具です。区切りの処理は既存コードが担当します。入力は記載した3種類の操作だけで、数は整数です。空白と空の操作は既存コードが除きます。

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