構造体リスト、配列、リンクバッファの比較

[困ったさん]

今、スタックやキューについて学んでいますが、それらを構造体リスト、配列、リンクバッファなどで実現することについて、それぞれどのような利点や欠点があるのでしょうか？

[管理人]

私が応用するのはゲームプログラムなんで、そっちの話ばかりになってしまうんですが、
スタックについてあまり利用した事がありませんが、キューについては利用した事があります。

例えば文字表示バーの待機などです。

「キャラAは敵Bに23のダメージを与えた」
「キャラBはドリンクを使用した」
「キャラCは息絶えた」

などの文字列を１箇所に時間差で表示したかったとします。
上記３項目は同時に表示する必要が出てきました。
しかし表示部は１行分しかないので、１行目を表示してしばらく待機して、２行目を表示する必要があります。

ですから、これらの文字列は３つ同時にデータとして与えるんですが、表示は各３秒ずつ表示しなければならない。
このとき、最初の文字列のポインタをキューに与えます。
次に次の文字列のポインタをキューに与えます。
次にその次の文字列のポインタをキューに与えます。

このキューにたまっている文字列を時間差で表示します。
するとすんなり表示できます。


後は、シューティングの玉の表示とかですかね？

ハンドル１　：　画像１
ハンドル２　：　画像２
ハンドル３　：　画像３
ハンドル４　：　画像４
ハンドル５　：　画像５
・・

と無数に玉の画像があります。
表示すべきかどううかのフラグが１万位あったとします。
全てのフラグについていちいち表示フラグがたっているか調べて表示するのはちょっと無駄な感じがします。
そこで、表示すべきハンドルのみキューに貯めて、キューにはいっているものだけ表示するようにプログラムしてもいいかもしれません。

[box]

リング（リンクではありません）バッファは
配列の終わりの要素から先頭の要素へつながるようにしたデータ構造なので、
ここでは配列と同じとみなします。

配列のメリット：
いちばん単純なデータ構造であり、多くの人が直感的に理解できる（と思う）。
添字さえ管理すれば、スタックやキューをどれだけ使っているかがわかる。
リスト構造に比べれば、格段にわかりやすい。

配列のデメリット：
定義時に要素数が決まってしまう。実行中の柔軟な要素増減が（ほぼ）不可能。

リスト構造のメリット：
ポインタを付け替えるだけで、（ほぼ）制限がない大きさのスタックやキューを管理できる。

リスト構造のデメリット：
配列に比べると、（特に入門者にとって）理解するのがむずかしい。
ポインタの付け替えロジックを誤ってしまいやすい。


お互いにメリット・デメリットが（ここに挙げた以外にも）あります。
配列やリングバッファで十分な場合もあるでしょうし、そうでない場合もあるでしょう。

[困ったさん]

なんかデータ構造にも用途によって様々な使い道があるんですね。
ありがとうございました！