第325回　スタックとキュー（前編）

$ \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} $

間違い探し

テトラ「List 23にNEW-LIST-FROM-ARRAYの《まちがった実装例》があります」

僕「《まちがった実装例》って？」

テトラ「つまり、いわゆるバグのあるプログラムです。問題7の間違い探しをしてくださいっ！」

僕「ええと……」

テトラ「……」

僕「……」

​

テトラ「……い、いかがでしょう」

僕「うん、List 23の間違いはわかったと思う。まず、基本的には、このNEW-LIST-FROM-ARRAYは動くよね。 といってもそれは『少なくとも配列から双方向リストを作ってはいる』という意味だけど、双方向リストじゃない変なものができるわけじゃない」

テトラ「はいはいっ！」

僕「List 23の行番号でいうと、A2でリストヘッドを作る。これは、要素が0個の双方向リストといえる。その後、A3からA11までのwhileの繰り返しで、 $$ A[1], A[2], A[3], \ldots, A[n] $$ という値を双方向リストに順番に挿入している……繰り返しのたびに$k$が増えていく。1からnまで順番に」

テトラ「はい……」

僕「それで、A6からA9のリンクの付け替えは、これまでに練習したものと同じだから間違いはないんだけど、重大な間違いがある。このList 23のままだと『配列の要素が逆順になった双方向リスト』になってしまう。 そこが間違いだね！」

テトラ「はいっ、そうです。そこが間違いになります。先輩、大正解ですっ！」

僕「……」

テトラ「正解です……よ？」

僕「あ、うん。いや、ありがとう、テトラちゃん」

テトラ「は、はあ」

具体的に確かめる

僕「List 23の間違い探しがちょっと難しいのは、与えられた配列の要素が一個の場合、つまり$n = 1$の場合には間違いに気付かない点だね」

テトラ「そうですね。要素が一個なら、逆順になってもわかりませんから」

僕「僕は、$$ A[1] = 10,\, A[2] = 20,\, n = 2 $$ を使って、10と20を順番に入れようとしたところで気付いたよ。A6からA9は、 pが指している新たなノードを双方向リストDの《先頭》……つまりリストヘッドの次に入れる処理だから、 毎回《先頭》に入れていったら逆順になっちゃうんだね」

テトラ「先輩ならどう修正なさいますか？」

僕「うん。確保したノードを双方リストの《末尾》に入れればいいね。それには、A6からA9のnextとprevをすべて逆にすればいい！」

テトラ「はい、List 24のようにしてもいいですし、List 25のように配列の要素を逆順に入れるという手もあります」

僕「なるほど。nextとprevはList 23のままにしておいて、$k$をnから1まで減らしていくんだね。確かに同じことだ」

次の問題は？

テトラ「NEW-LIST-FROM-ARRAY以外にも、まだまだ問題はあります。次はどんな問題がお好みでしょうか？」

僕「そうだなあ……リンクの付け替えでいろんなことができるのはわかってきたんだけど、これっていったんどんなふうに役立つんだろうね」

テトラ「So what?（だから、何？）ですねっ！」

僕「ああ、確かに。テトラちゃんが出してくる《根源的な質問》に近いかも。根源的というよりも応用的かもしれないけど……」

テトラ「それでは、こんな問題はいかがでしょう！」

僕「カッコの対応を調べるアルゴリズム……なるほどね。たとえば、$$ (1 + 2) $$ のようになっていたら正しい対応になっていて、 $$ (1 + 2 $$ だったら正しくない対応という意味かな？　そんなに難しくなさそう」

テトラ「それだけじゃなくてですね……」

僕「ああ、そうか。複数個あるのか！　たとえば、$$ ((1 + 2) + 3) $$ のようになる場合があるんだね。だとすると……」

テトラ「ええ、そうなんですが……」

僕「うん、簡単だね。開きカッコの個数を数えるだけで済む」

テトラ「……といいますと？」

僕「開きカッコの個数と、閉じカッコの個数が等しくなればいいよね。まだ閉じていない開きカッコの個数を、最初は0にしておいて、 読んだ文字が開きカッコだったら1増やして、閉じカッコが来たら1減らす。 文字を読み終えたとき、閉じていない開きカッコの個数が0になっていたら正しいカッコの対応だ」

テトラ「先輩、先輩！　問題は最後まで聞いてくださいっ！」

僕「……はい。すみません」

テトラ「先輩のおっしゃる《開きカッコの個数を数える》方法ではまずいことが起きます。たとえば、 $$ ))1 + 2(( $$ という文字列が与えられた場合でも、 文字を読み終えたときには閉じていない開きカッコの個数は0ですよね。 でもこれは、正しいカッコの対応とはいえません」

僕「確かに。文字を読んでいる途中で負になってはいけないという条件が必要だね」

テトラ「それに、カッコは一種類とは限りません。たとえば、$$ [ \{1 + 2\} + (3 - 4) ] $$ のようになっていても、正しいカッコの対応であると見なすことにします。 でも、 $$ [ ( 1 + \{ 2 + 3 ) - 4 \} ] $$ は正しいカッコの対応とは見なさないことにします。正しい入れ子になっていないからです」

僕「なるほど……だとすると、カッコの種類ごとに数を数える必要があるか。いや、待てよ……」

テトラ「問題8を改めて示しますね」