スタック/キュー操作コモン公開

「スタック操作コモン」と「キュー操作コモン」公開したので
ブログの方でもまとめておきます。

それぞれのコモンについては以下のコモンイベント集の
登録先にて確認してください。
スタック操作コモン
キュー操作コモン


一応ここで
スタックとキューを使用すれば何が実現できるのかを大まかに
説明しようと思います。
とはいえ使い方は数えきれないほどありますし、説明として
的確なものを考えるのもの大変ですので
代表的なものを説明していきたいと思います。

まずはスタックから説明していきたいと思います。


■ スタック

代表的なものの１つとして構文解析があります。
例えば以下のような文字列があるとします。

if( A > (B + 1) ){
　B += 1;
}

このとき
『if』の次出てくる『()』で囲まれた文字列を取得したい場合
この場合『 A > (B + 1) 』が取得したい文字列に該当しますよね。

ですが該当する文字列の中にも『()』があります。
もし『if』の次の『(』から『)』までの文字列を取得した場合
『 A > (B + 1』
が取得されてしまいます。

この問題を容易に解決する手法の１つとしてスタックを
利用する方法があります。

まず『if(』の『(』をスタックに入れます。
そして右へ右へ文字列を調べていきます。
もし『(』が出てきた場合、さらにスタックに入れます。
今回の場合『(B』の部分の『(』がそれに該当します。
そして『)』が出てきた場合、スタックから『(』を取り出します。
もしこのとき、まだスタックに『(』が入っている場合続行します。
そしてスタックの中身が空になるまで続けます。
中身が空になった場合、その箇所の『)』が先頭にあった『(』と組に
なることがわかります。

これで『 A > (B + 1) 』を取り出すことが可能になりました。

今回の例の場合、できる限り分かりやすくするために
単純なパターンに限定しましたが、
いろいろな種類の括弧が出てくる場合などにとても役に立つと思います。
その場合は取り出した括弧が同じ種類の括弧かどうか調べるなど
すれば対応できるでしょう。

この原理を使えば数式の計算などにも用いれます。
1 + ( 5 × ( 4 + 1 ) )
上記の様な場合でも『4 + 1』のところから取り出して～～～
って言う感じで計算を行っていくことができます。
こういった数式計算についての詳しいことは『逆ポーランド記法』等で
調べるとよいでしょう。

迷路のスタートからゴールを求める探索処理などにも
スタックが用いられます。

他にも編集ソフト等で
アンドゥ、リドゥで操作を元に戻したりする処理も
スタックによって実現されています。


次にキューの説明……と言いたいところだけど
すごく長くなりそうなのでまた次回にでも書こうと思います。
（※たぶん）