スタック

積み上げて、上から取る

前回まででは関数と再帰の読み方を確かめました。ここからは、アルゴリズムが値を置いておく「入れ物」そのものを見ていきます。最初はスタックです。

スタックは、値を上へ積み上げていき、いちばん上から取り出す入れ物です。後から入れたものが先に出るので、後入れ先出し (LIFO、Last In First Out) と呼びます。机の上に本を積んでいく様子そのままで、途中の本は抜けず、いちばん上の1冊しか取れません。

操作は2つだけです。push は上に1つ積む操作、pop はいちばん上の1つを取り出して返す操作です。pop は取り出す操作なので、実行すると中身が1つ減ります。「いちばん上を見るだけ」ではない点に注意してください。試験の問題文で pop が出てきたら、値を受け取ると同時にスタックが短くなる、と読みます。

中身の書き方を先に決める

スタックの問題を間違える原因のほとんどは、どちらの端が「上」なのかを決めないまま追い始めることです。そこでこのコースでは、中身を {3, 1, 4} のように並べて書き、右端をいちばん上 (先頭) とします。この約束を決めておけば、迷いがなくなります。

  • {3, 1, 4} の状態で push(5) を実行すると {3, 1, 4, 5} になります
  • 続けて pop() を実行すると 5 が返り、中身は {3, 1, 4} に戻ります
  • 空のスタックは {} と書きます

擬似言語では、スタックの変数 st に対して st.push(x) と st.pop() の形で書きます。pop() は値を返すので、x ← st.pop() のように代入の右側に置かれます。

スタック: st st.push(3) st.push(1) x ← st.pop() /* x に 1 が入り、st は {3} になる */

どこで使われているか

再帰は、その仕組みそのものがスタックです。前回のトレースで、呼び出しが深くなるほど戻り先が積み上がり、戻るときは最後に積んだものから消えていきました。あれが呼び出しスタックです。

ほかにも、式の中の括弧の対応が取れているかを調べる処理、逆ポーランド記法の計算、ブラウザの「戻る」など、直前の状態へ戻したい場面はすべてスタックが向いています。

試験での問われ方

科目Bでは、push と pop が並んだ操作列を与えて、最後に取り出される値や、途中のある時点での中身を答えさせる形が定番です。値そのものより順番が答えを決めるので、1操作ごとに中身を書き出すのがいちばん速い解き方です。頭の中だけで積み下ろしを追うと、必ずどこかで1つずれます。

次のトレースで、push と pop が混ざった操作を1行ずつ追ってみましょう。取り出した値をもう一度積み直す行があるので、そこで中身がどう変わるかに注目してください。

課題

  1. 各行を実行したあとの値を入れる
  2. 値が変わらない変数はそのままの値を入れる
  3. スタックの中身は {3, 1} の形で書き、右端をいちばん上とする

ヒント

1 / 8 行目のトレース

1○整数型: tameshi()
2 スタック: st
3 整数型: x, y
4 st.push(3)
5 st.push(1)
6 st.push(4)
7 x ← st.pop()
8 st.push(x + 1)
9 y ← st.pop()
10 return y
実行した行stxy
実行前———
2 行目

2 行目を実行したあとの値を入れてください。変わらない変数は、 そのままの値を入れます。まだ値が入っていない変数は「—」と入れます。