スタックやキューを作成する際に用いる方式の利点、欠点について

最近、スタックやキューを学んでいます。
これらを作成するには、構造体リストや配列、リングバッファなどを用いると思うのですが、この3つの方式に利点や欠点はありますか？
どのような場面でどの方式が活躍するのか、逆に何が向いていないのかなど気になっています。よろしくお願い致します。

行動規範の内容に同意します

回答2件

ベストアンサー

んー、それぞれの利点・欠点が理解できていればわかるはずですが……

まず、配列(構造)とリスト構造で考えてみましょうか。

配列はイメージとしては『中身の見えない箱』(びっくり箱とかみたいな)が『横一列に並んでいる』感じです。
縦一列の場合もありますが、ここでは横一列をイメージします。

収納ボックスの横一列に連なっている感じでしょうか。

なので、『5番目の箱を開けろ』とかみたいなことが出来ます。

配列だと arr[5] とかです。

でも、配列は『要素数が決まっている』のです。

たとえばC言語で配列を宣言するなら、

C
1int arr[10]; // 要素数10の配列

と言う風に。そうすると『要素数を超えることが出来ない』のです。

上記であれば arr[11] とかを追加しようとしてもできません。

なので、やるなら『別の配列を用意して、値をコピーし、挿げ替える』しかないです。

C
1int tmp[10]; // データすでに入っているとして
2
3int arr[11]; // N+1 した要素数分確保
4
5int i; // for文用
6
7// tmpにあるデータをすべてarrにコピー
8for( i = 0; i < 10; i++ ){
9    arr[i] = tmp[i];
10}
11
12arr[10] = 8; // 追加したい値をセット
13
14// 以降は arrの方を使う

のような感じで。

なので計算量でいえば **O(n)**ですね。

リスト構造の場合、某イメージ( 例 ) のような感じです。

そうですねぇ……子ども向けのおもちゃで、車系のおもちゃで、レールをつなげて自分で作るタイプ、ありますよね?
あのイメージです。

なので削除しようと思えば、その部分の前後を取り外し、削除したいものを削除して前後を直接つなげる。

後ろへの追加ならそのまま後ろの方につけるだけ。

なので (その場所にポインタなりが来ているという前提で) O(1) です。

したがって、スタック構造とかで使うなら、

[配列構造を利用]

 利点:
     実装が楽( 単に配列を用意するだけ )
 欠点:
     要素数が固定の為、サイズがその都度変動する場合は再実装をするか、修正し直さないといけない 

[リスト構造を利用]

 利点:
     付け替えたりするだけのため、要素数の変動が可能
 欠点:
     実装が面倒すぎる……(C++ でも OKならすでに実装済みだが、C言語だと実装しないといけない)

ですね。

[追記1]

もうちょっと調べてください。

『リスト構造 C言語』とかで調べてください。

リスト構造への理解が甘いので、区別がつかないのだと思います。

[追記2]

『スタック構造リングバッファ』でggると、

例2がヒットしました。

ざっと調べただけでも普通にヒットしますから、ご自分で調べた方が早いですよ。

それとプロでも調べながらやっています。

検索力は必須です。

それでもわからない場合は『質問方法を工夫』しましょう。