いぬおさんのおもしろ数学実験室

おいしい紅茶でも飲みながら数学、物理、工学、プログラミング、そして読書を楽しみましょう

スタック(データ構造の一種)とは何か

 下のようにカッコが並んでいます。数式についたカッコと思えばよいでしょう。点検してみるとカッコの対応は正しいことが分かります。例えばこれが

((()(())だと正しい対応でないということになります。いったん開いたカッコは閉じなければなりません。また開いていないカッコを閉じることはできません。

f:id:Inuosann:20200722080902p:plain

正しい対応かどうかは見れば分かります。しかしちょっと複雑になると間違いは起こりますし、パソコンにやらせるときに困ります。つまりパソコンに「(()(()()))」というデータを渡し、これが正しい対応になっているか判断させたいのです。しかも、どのカッコが対応しているのかも明らかにしたいとしましょう。例えば、2と3は対応していますし、また4と9は対応しています。こんな感じに対応が分かればよいのです。

 パソコンで扱うデータ構造にスタックというものがあります。いわゆる「先入れ・後出し」(さきいれ・あとだし)というやつです。スタックについてはこの記事でも紹介しています。 

www.omoshiro-suugaku.com

スタックは stack。積み重ね、干し草の山という意味です。改めて解説します。スタックとはデータの格納の仕方、取り出し方に決まりのある記憶装置です。例をあげて説明します。下の図を見てください。空のスタックに5を格納しました(図1)。次に2を格納しました(図2)。そして3を格納しました(図3)。次に3を取り出します(図4)。

f:id:Inuosann:20200722084229p:plain

このように、スタックでは格納してあるデータの上に新しいデータが格納されてゆき、取り出すときにはそのとき一番上に見えているデータが取り出されます。格納の操作は「プッシュ」、取り出すのは「ポップ」と言います。これでスタックについては分かりました。もとの問題を考えます。

 説明のため、最初の問題より易しいものを用意します。どのカッコがどのカッコに対応しているのか調べます。

f:id:Inuosann:20200722082917p:plain

図を見ながらカッコについている番号をスタックに出し入れしますが、カッコを開くときは番号をプッシュ、閉じるときにはポップすることにします。「(」はカッコを開く、「)」はカッコを閉じる、と表現します。まず1のところでカッコを開くので1をプッシュ(図1)。2でカッコを開くので2をプッシュ(図2)。3でカッコを閉じるのでポップ。このとき、一番最近プッシュした2が取り出されます(図3)。

f:id:Inuosann:20200722090346p:plain

4でカッコを開くので4をプッシュ(図4)。5でカッコを閉じるので一番最近プッシュしたデータ、4をポップ(図5)。最後、6でカッコを閉じているので一番上にあるデータ、1をポップします(図6)。これでスタックは空になりました。

f:id:Inuosann:20200722090743p:plain

図の番号とポップされる番号が、対応するカッコの番号になっていることが分かるでしょう。もちろん、最後にスタックがちょうど空になったら「正しく対応していた」ということになります。

 これ、何に使うんでしょうか? もちろん本当に「カッコが正しく対応しているかどうか」の確認にも使えますが、プログラミング言語の作成にも役立ちます。例えば……(何の言語も見たことがない、という人は分かりづらいかも。ゴメンナサイ……)。

f:id:Inuosann:20200723081554p:plain

while文、for文、if文が混ざっています。架空の言語ですが。while、for、 ifと対応するendは同じ色にしてあります。「この end はどの命令に対応しているのか」ということが分からないと困ります。これを明らかにするために上述のスタックを使えることは明らかでしょう。while 、 for 、 if を「(」と思い、end を「)」だと思えばよいのです。実際に今、自分で作っている言語でこの方法を用いています。

 

 何だか全然暑くありませんね。山の部活をやっていたときには7月20日くらいには梅雨が明けてそれまでの曇りとは違う、凄い青空。たいていすぐ合宿でどこかの山に行きます。生徒も頑張っているし気温も上がって「よし、行くぞ!」とテンションが最高に上がったものです……。