第326回 スタックとキュー(後編)

スタックを《使う》立場から、スタックを《作る》立場に移動した「僕」とテトラちゃん。アルゴリズムを理解する柔軟な発想が試される!

新シリーズ「数学ガールの物理ノート」始動!

『数学ガールの物理ノート/ニュートン力学』

『数学ガールの物理ノート/ニュートン力学』をアマゾンで見る

登場人物紹介

:数学が好きな高校生。

テトラちゃんの後輩。 好奇心旺盛で根気強い《元気少女》。言葉が大好き。

$ \newcommand{\ABS}[1]{\left|\mathstrut #1\right|} \newcommand{\TT}[1]{\textrm{#1}} \newcommand{\ANGLE}[1]{\angle\textrm{#1}} \newcommand{\TRI}[1]{\triangle\textrm{#1}} \newcommand{\HIRANO}{\unicode[sans-serif,STIXGeneral]{x306E}} \newcommand{\SQRT}[1]{\sqrt{\mathstrut #1}} \newcommand{\TRUE}{\textbf{true}} \newcommand{\FALSE}{\textbf{false}} \newcommand{\FOCUS}[1]{\fbox{$#1$}} \newcommand{\GEQ}{\geqq} \newcommand{\LEQ}{\leqq} \newcommand{\NEQ}{\neq} \newcommand{\REMTEXT}[1]{\textbf{#1}} \newcommand{\PS}[1]{\left(#1\right)} \newcommand{\LL}{\left\langle\,} \newcommand{\RR}{\,\right\rangle} \newcommand{\LLRR}[1]{\LL#1\RR} \newcommand{\Enil}{\textbf{nil}} \newcommand{\Fnext}{\textrm{next}} \newcommand{\Fprev}{\textrm{prev}} \newcommand{\Fvalue}{\textrm{value}} \newcommand{\LNOT}{\lnot} $

スタックを実装しよう

双倉図書館の一般講座《リンクとストラクチャー》でアルゴリズムを学んできたテトラちゃんは、 自分の理解のため、学んだことをに向けて《講義》している。

最大の値を求めるMAX-VALUEを題材にしたり(第321回参照)、 線形リストのノードを先頭に移動するMOVE-TO-FIRSTを題材にしたり(第322回参照)、 リストヘッド付き線形リストを議論したり(第323回参照)、 双方向リストを考えたり(第324回参照)、 文字列のカッコの対応を調べるMATCHEDステップワイズ・リファインメントで作ったり(第325回参照)してきた。

いまは、スタックを双方向リストで実装しようとしていて……

スタックを作ろう

「あっ、これは、もしかして……テトラちゃんが好きな《知らないふりゲーム》になってる?」

テトラ「そうなんですよ! スタックを使う側では、スタックがどう実装されているか知らなくていい。スタックを作る側では、スタックをどう使うかを知らなくていい。 両者が知るべきなのは、NEW-STACKPUSHPOPIS-EMPTY-STACKの入力と出力だけです。これらのインタフェースを守っていれば……守っているものを……スタックと呼ぶんですっ!」

「おもしろい! これはすごくおもしろい話だねえ!」

テトラ「おもしろいですよねえ!」

スタック

「ということは、具体的にはPUSHPOPという手続きを作る……プログラミングしていくことになるのかな、テトラ先生!」

テトラ「先輩、『テトラ先生』はやめてください……ちょっと恥ずかしくなってきました」

「わかったけど、でもテトラちゃんの《講義》はとてもわかりやすいよ。教え方がうまいんだ」

テトラ「あ、ありがとうございます。教えるといっても、あたしは習ったことをお伝えしているだけなんです……あ、でも、あたし、先輩に教えていて思ったんですが、 いろいろ話してもらった方が教えやすいんですね」

「話すというのは、教えてもらう側が?」

テトラ「そうです。あたしが先輩に少し何かを伝えますと、先輩はいろいろ質問を返してきます。その質問があると、あたしはとても話しやすくなります。 それから、先輩はご自身が考えたことを語ってくださいます。あたしの話はそこに導かれることもよくあります」

「なるほど。その感覚は僕もよくわかるよ。ほら、以前ノナちゃんの話をしたことがあるよね(『数学ガールの秘密ノート/学ぶための対話』)。 あのときは、数学を教えるのがすごく難しかった。 話しても反応があまり帰ってこないから、わかったのかどうかがわからないし、 どこまでわかったかもわからない。ノナちゃんが悪いわけじゃないんだけどね」

テトラ「はいはい。たとえばあたしが先輩に《スタック》や《ステップワイズ・リファインメント》のことをお話ししたときに、もしも先輩が無表情で無言だったら……あたしはたぶん何も話せなくなると思います。 もっと詳しくお話しした方がいいのか、どんどん次に進んでいいのかがわからないからです」

「無表情、試してみる?」

テトラ「や、やめてくださいよう……ああ、でも、あたし、授業中に先生に対して同じことをやってるかもしれません。 先生が『わかりましたか』と尋ねたときに、きちんと反応を返していなかったかも。 それって先生にとっては教えるのが難しい生徒ってことですよね……」

「いやあ、テトラちゃん。テトラちゃんが授業中に反応を返してないなんてことは絶対にないと思うよ……」

テトラ「そうでしょうか……だといいのですが」

「うん。自信を持って言えるよ!」

新たなスタックを作る

テトラ「では、双方向リストでスタックを実装するというお話に入ります。最初はNEW-STACKです。この手続きを呼び出すと、要素が一個も含まれていない双方向リストを作って返します。 それだけです」

List 29

List 29ではNEW-NODEを呼び出している。prevフィールドもnextフィールドも自分自身を指しているリストヘッドだけが作られて、 そのアドレスを返したということだよね(第324回参照)」

テトラ「はい、その通りです。要素が一つもない双方向リストを作ったことになります」

NEW-STACKはリストヘッドだけを作り、そのアドレス(この例では3820)を返す

「実際には、$$ S \leftarrow \textrm{NEW-STACK}() $$ のようにして、スタックSを使うことになるんだよね?」

テトラ「そうです」

「でもね、NEW-STACKって、単にNEW-NODEを呼び出しているだけだから、わざわざNEW-STACKを作らなくてもいいんじゃないの?」

テトラ「ええ、そうですね。ただ、このようにすると実装が隠蔽されて都合がいいんです」

「いんぺい? 隠蔽されて都合がいい?」

テトラ「あ、い、いえ。隠蔽というと不穏な雰囲気が漂いますけれど、よからぬお話ではありません。先ほどの《知らないふりゲーム》のお話と同じです。どんなふうにスタックを実装するかを見せないようにするというだけのことです」

「そうか……スタックを《使う》側に対して隠すということ? 『双方向リストによって実装している』ことを隠蔽しているのかな?」

テトラ「はい、そういうことになります」

「スタックを《作る》側には隠蔽しているわけじゃないよね。まあ、それは当然か」

テトラ「はい。いまのあたしたちはスタックを《作る》側にいて、もちろん、双方向リストでスタックを実装することを知っています。先輩のおっしゃる通りです。隠蔽してはいません」

「うん、ここまでは理解したと思うよ」

は、自分が「理解した」ではなく「理解したと思う」と言ってることに気付いた。

次々に新しい概念がやってくるとき、「理解した」と言い切ることは難しい。 言ってる意味はわかったとしても「どうしてそんなふうに考えるのか」という方法論がしっくり来ないからだ。

うん、テトラちゃんがよく「わかった……と思います」と表現するけれど、 きっとこんな気持ちなんだなあ。 《ある程度は理解したけれど、もう一度ゆっくり考える必要がありそうだ》という旗を立てておきたい気持ちだ。

スタックにPUSHする

テトラNEW-STACKの次に実装する手続きはPUSHです。スタックSと、スタックに積む値vが入力になって、これまで練習してきたようなリンクの付け替えを行います。 やっていることは……」

List 30

「……うん、List 30は読めるよ。2行目では、スタックに積むvの値をvalueフィールドに入れたノードを一つ確保している。そして3行目から6行目までで、そのノードを双方向リストの先頭に入れている。たとえばPUSH(S, 123)を呼び出したら、こんなふうになるよね」

$$ \begin{align*} & S \leftarrow \textrm{NEW-STACK}() \\ & \textrm{PUSH}(S, 123) \\ \end{align*} $$

テトラ「はい、その通りです! ここでも、PUSHという手続きの中では、双方向リストであることを利用しているわけですが、PUSHを呼び出す側では、スタックが双方向リストで実装されていることは知りません。 入力として与えているのがスタックSと値のvだけだからです」

「確かに、この二行だけを見た場合、Sが双方向リストで実装されているかどうかはわからないね。《使う》側には知らされていない。隠蔽されている。知らされているのは、Sに対してPUSHPOPができるということだけ……?」

$$ \begin{align*} & S \leftarrow \textrm{NEW-STACK}() \\ & \textrm{PUSH}(S, 123) \\ \end{align*} $$

テトラ「そうです! 講師の先生は《インタフェースを設計する》とおっしゃっていました。どのような手続きのセットを用意するか、それぞれの手続きは何を入力とし、何を出力とするか……それがインタフェースの設計です。 もちろん、インタフェースがどうなっていても、つじつまがあえばプログラムは動きます。 でも、実装をどこのレベルまで見せるか、そしてどこのレベルまで隠蔽するかによって、プログラムが修正しやすくなったり、しにくくなったりするそうです」

「……そうか。プログラムを考えるときには、そういう工学的な観点が出てくるってことなのかな。プログラムを修正しやすいとか、どこまでを隠蔽するかとか……」

テトラ「工学的な観点……」

「数学の場合には修正しやすいかどうかなんて考えないし、どこまで隠蔽するかなんて考えない……いやいや、待てよ。《知らないふりゲーム》だと考えてみると、そうでもないかな」

テトラ「先輩は何を考えていらっしゃるんですか?」

「うん、あのね。インタフェースの設計って、《群》や《環》と似ているよね」

テトラ「えっ?」

「群では、積という演算が定義されていて、単位元があって、結合法則などの法則を満たしていた。そして、そのようなものを《群》と呼んだ。 それが実際には足し算だろうがビット演算だろうが、あみだくじだろうが《群》だった。《群》と見なせた。 環では、積と和という演算が定義されていて、分配法則などを満たすべき法則が決まっていた。 そして、そのようなものを《環》と呼んだ。 それが整数環だろうが、多項式環だろうが、《環》だった……似てない?」

テトラ「ああ、そうですね! 《スタック》も似ています。PUSHPOPというものがあれば、それが何で実装されていようともスタックと呼べます。そういう意味ですね?」

「うんうん。インタフェースの設計をまちがえるというのは、一般的な群に関する証明でビット演算であることを仮定したり、 一般的な環に関する証明で整数環であることを仮定しちゃうのに似ているかも……って思ったんだよ」

テトラ「似てると思います!」

スタックが空かどうかを調べる

「じゃあ、次はPOPを双方向リストで実装する?」

テトラ「その前に、スタックが空かどうかを調べるIS-EMPTY-STACKを実装します。List 31になります。これは双方向リストのときと同じです(第324回参照)」

List 31

「ああ、そうだね。List 31では、要素数が0であることを使うんじゃなくて、もっと直接的にリストヘッドが自分自身を指しているかどうかで空かどうかを判断している」

スタックからPOPする

テトラ「次にPOPですが……」

「これはPUSHの逆だね。リストヘッドから先頭の値を得ればいい」

テトラ「だいたいはそうなんですが、注意が必要になります。エラー処理が必要になるからです」

この続きは有料会員登録をすると
読むことができます。
cakes会員の方はここからログイン

1週間無料のお試し購読する

cakesは定額読み放題のコンテンツ配信サイトです。簡単なお手続きで、サイト内のすべての記事を読むことができます。cakesには他にも以下のような記事があります。

人気の連載

おすすめ記事

アルゴリズムと確率を学ぼう!

ケイクス

この連載について

初回を読む
数学ガールの秘密ノート

結城浩

数学青春物語「数学ガール」の中高生たちが数学トークをする楽しい読み物です。中学生や高校生の数学を題材に、 数学のおもしろさと学ぶよろこびを味わいましょう。本シリーズはすでに14巻以上も書籍化されている大人気連載です。 (毎週金曜日更新)

この連載の人気記事

関連記事

関連キーワード

コメント

fall_twtr List39のT21に NEXT-ELEMENT ってあるけど、これは NEXT-CHARACTER のつもりかな 12日前 replyretweetfavorite

fall_twtr 練習問題、単純にぱっと思いついたのは、今キューに入っているのが数字かアルファベットかあるいは空… https://t.co/q2cpAjLJC3 12日前 replyretweetfavorite

fall_twtr なるほど、キューはスタックと逆のイメージってことでサクッと。構造やら隠蔽やらにも少し触れて、「みんなも想像力を働かせてみてね」という形。 12日前 replyretweetfavorite

Lsdu2DalePerry 先週は【スタック】が出てきた。RPNの考え方に似ていたので分かりやすかったけど、今週の【キュー】という概念も面白いですね。 12日前 replyretweetfavorite