【第三回】C#におけるCollectionsの基本のキを理解する【スタックとキュー】

はい第三回です。
第二回目はこちらです。
今回はCollectionsの中で利用頻度がそこそこ高いスタックとキューについて説明したいと思います。
ただし例のごとく、僕のプログラミング歴は約3ヶ月と短いので、間違っている可能性山のごとしです。
その点だけご留意ください。

まず確認

みなさんはスタックとキューと言われて、「ああ、あれね。知ってるよ」と答えられますか?
もし答えられるなら、この記事は読むに値しません。飛ばしちゃいましょう。
もしスタックとキューについて「なにそれ初めて聞いた。C#特有の機能?」などと疑問が湧いた方は、ぜひこの記事を読んでください。
スタックとキューについての概要くらいは把握できるようになると思います。

スタックとキューはC#独特の機能ではない

C#でスタックとキューを利用する場合、一般的には System.Collections.Generic名前空間に属するStack<T>クラスやQueue<T>クラスを利用します
そしてこのスタックとキューという機能、実はC#が独特に実装している機能ではないのです。
もちろんStack<T>クラスやQueue<T>クラスはC#独自の機能なのですが、スタックやキューそのものは別の言語でも利用できます。
もっと言えば、OS自体がスタックやキューの考え方を利用しています。

スタックやキューは考え方

先ほど「OS自体がスタックやキューの考え方を利用しています」と書きました。
そうなのです。
スタックやキューは単なるものの考え方なので、言語に依存しません
実際、スタックやキューを標準で実装していない言語でも、自分でスタックやキューの機能を作ればスタックやキューを利用できます
もちろんC#でもスタックやキューの機能をもつクラスを自作することもできますが、特別な理由がない限りはSystem.Collections.Generic名前空間に属するStack<T>クラスやQueue<T>クラスを利用した方が賢明でしょう。

スタックもキューも配列の亜種

じゃあスタックとキューって具体的になんやねんという話ですが、スタックもキューも配列の亜種と考えておけば当たらずといえども遠からず
配列をどのように使っていくかの考え方と言い換えることもできます
つまり、スタックもキューもデータを保存するための配列であり、そのデータを管理する方法を指し示す言葉なのですね。

スタックとは何か

スタックはイメージで覚えたほうが楽です。
まず、お皿があるとしますね。そのお皿の上に、違うお皿を置きます。そのまたお皿の上に、違うお皿を置きます。
これを幾度か繰り返したとき、一番下のお皿を取りたい場合、どうしますか?
一番下のお皿をじかに取ろうとしたら、他のお皿がついてきてしまうので、とても危ないですね。
安全に取るには、最後に置いたお皿を取って、その最後の前に置いたお皿を取って……と繰り返して最初のお皿まで行くとよいです。
まさにこれがスタックです。
つまり、最後に置かれたものから順番に取っていく方法がスタックなのです。

よりプログラム寄りの例も挙げてみましょう。
例えばカレンダーを想像してみてください。
ごく一般的な家庭にある、毎月めくっていくタイプのカレンダーです。
このカレンダーを、スタックを使った考えを用いて制作してみましょう。

スタックで作るカレンダー

ここで作るカレンダーは、必ず1月から順番に表示していくものとします。
1月を表示しているのに、その次の月が急に6月になったりはしません。1月の次は必ず2月です。
また、過去の月を表示することもできません。
ここではそういうカレンダーを作ります。

とりあえずスタックAを用意します。
このスタックAには、12月のデータを追加(Push)します。
ここで「おい待てよ。順番に表示するのなら、最初は1月からじゃないのか」と思うかもしれませんが、お皿の例で説明したように、スタックは最後に追加したものから順番に取り出していくという性質があります
なので最初に追加するデータは12月でなければなりません。
なんだか直感的ではないですが、スタックとはそういうものなので仕方ありません。

さて、続いて11月、10月……と追加していきましょう。最終的には1月まで追加します。
これでスタックAは完成です。
このスタックAから情報を取り出す(Pop)と、最後に追加した1月が表示されます
1月が表示されたあとにさらに情報を取り出すと、今度は2月です。
取り出した情報(Popした情報)は、もう元に戻すことはできません。破棄されてしまいます(ただし実際にC#でスタックを使う場合、情報は取り出すけれども破棄しない方法がちゃんと用意されています)。

そうして12月まで情報を順番に取り出したなら、そのスタックの中身は空になります
どうでしょうか?
ちょっとはスタックのイメージがつかめてきたでしょうか?

注*実際のプログラミングでは、データを全て取り出し終わらないうちに、別のデータを追加することもザラです。カレンダーの例のように、スタックに何もデータが追加されないまま中身が空になることばかりではないとだけ覚えておいてください。

スタックとよく対比されるのがキューですから、キューも見てみましょう。

キューとは何か

キューもイメージで覚えたほうが楽です。
たとえばあなたがゲームを買ったとします。
窃盗するのでもない限り、普通はレジに並びますよね。
このとき、横入りするオロカモノ! でもない限りは、列の最後列に並びます
つまり、最初に並んでいた人が最初にレジで精算を済ませます。最後に並んだ人は、今までに並んでいた人が全て精算し終えるまで待たなければなりません。また、あとから誰かが自分の後ろに並んだとしても、自分の順番は変わりません(横入りでもされない限りw)。
これがまさにキューです。

つまり、最初に追加されたデータから順番に処理されるのがキューというわけですね。
なんだかスタックと対照的ですね。

カレンダーを作るならキューの方が適している

実はカレンダーを作るならスタックよりもキューのほうが適しているかもしれません。
なぜなら、スタックは最後に追加されたデータが最初に処理されるという性質上、12月からデータを追加しなければならないからです。
このことがなぜ問題となるのでしょう?

例えば、ありえないことではありますが、もし「一年は14ヶ月である」と改訂されたときのことを想像してみてください。
スタックを使ったプログラムの場合、あとから「13月」と「14月」のデータを追加することができないのです!

注*正確には作りにくいだけで、できないことはないです。

なぜなら、「13月」や「14月」のデータを追加しようとしても、最後に追加したデータから処理されるため、「13月」や「14月」のデータを12月よりも後ろに持っていくことができないからです。
これは困りましたね。

ではキューを使った場合、どうなるでしょう。
最初に追加されたデータから処理されるという性質上、一年が14ヶ月どころか20ヶ月になろうとも、あとから必要な分だけのデータを追加してやればよいだけです。
これはカレンダーに適していますね!

注*もちろん、キューよりスタックが適しているデータもあります。どこでもキューの方が優れているというわけではないので、その点だけ抑えておいてください。

キューでカレンダーを作ってみる

キューでカレンダーを作ってみましょう。基本はスタックと同じです。
変わったことは、最初に「1月」を追加し、それからどんどん月を進め、最終的に12月を追加するということだけです。
データは最初に追加されたもの、すなわち「1月」から順番に取り出されます
したがって、「13月」をあとから追加したくなったとしても、全く問題ありません(「13月」君が最後尾にお行儀よく並んでくれればね)。
ちなみにですが、ここでのカレンダーも、1月を表示しているのに、その次の月が急に6月になったりはしません。1月の次は必ず2月です。
また、過去の月(つまり破棄したデータ)を再度表示することもできません。

スタックとキューを実際の開発ではどう使っているか

「つまんねー例じゃなくて、実際のプログラムではどんな風に使ってんだよ」と思われる方がいるかもしれませんね。
まずスタックから行きましょう。
例えば僕の制作中のゲームでは、ゲーム画面をシーンごとに管理しています。
シーンというのは、例えば「ブート画面」「タイトル画面」「キャラ選択画面」「パズル画面」などですね。
このシーンでプログラムを管理するというやり方は、ツクールMVでも使われています。Unityでもシーンという用語があるので、たぶん同じかなあ? と思っています。

で、このシーンを管理するときなのですが、「前のシーンに戻りたい」というときがあります
そして、「前のシーンは複数の可能性がある」場合があり、直接「タイトル画面へ飛べ!」と指定できないことがあるのです。
このとき役に立つのがスタックです。
シーンをスタックに溜め込むことにより、「前のシーンが何か」というのが一発でわかるのです。
シーンを溜め込んでいるスタックから情報を取り出せば(Popすれば)、それすなわち「前のシーン」ですからね。

より一般的な例で言えば、テキストエディタの「元に戻す」機能はスタックを使っているでしょう(実際に開発したわけではありませんので、別のもっと適切な方法があったらすみません)。

キューの使用例も挙げておきます。
僕の制作中のゲームでは会話シーンがあるのですが、その会話の順番は完全に決まっています。
つまり、いったん会話する順にキューへ登録しておけば、そのキューからデータを取り出していけば、会話が成立することになります
ちなみにですが、ツクールMVのメッセージ表示もキューの機能を使っているようですよ。

スタックとキューの説明おわり

C#を使ったプログラムのところまで書けませんでしたが、いかがでしたでしょうか?
スタックとキューについての理解の手助けとなれば幸いです(個人的にはカレンダーの例が秀逸だと自画自賛しています)。
次回こそは実際にC#でスタックとキューを使ったプログラム例を紹介いたしますので、どうぞお付き合いください。

フォローする