スタックについて

質問

スタックを配列と連結リストで表現したとき、
例えば1 10 100 1000の順でpushしたとき、
配列だと、1 10 100 1000の順、連結リストだと
1000 100 10 1の順に表示されます。
なぜ、配列だと、底から頂上に出力されて、
連結リストだと頂上から底の順に出力されるんでしょうか？

よろしくお願いします。

（参考）
配列を用いたスタックのプログラム
http://www.infor.kanazawa-it.ac.jp/~watlab/al/2-1.txt
連結リストを用いたスタックのプログラム
http://www.infor.kanazawa-it.ac.jp/~watlab/al/2-2.txt

回答No.3

麻野 なぎ（@AsanoNagi） · ベストアンサー

まず、一般的にいって、「スタックを配列で表現するか、連結リストで表現するか」ということと、「出力」の順番は関係ありません。

例題のプログラムが、（出力ではなくて）データの保持順序をそのまま表示しているために、このプログラムでは、たまたま、反対になるだけです。

ただ、これは、別の意味でおもしろい例題ではありますが。

そもそも、「スタック」とは、データの挿入と取り出しができて、データを入れたのと反対の順序でデータが取り出される構造です。
この性質させ満たせば、具体的なデータの持ち方はどうでもいいわけです。
そのために、「内部的なデータの持ち方」は反対なのに、「スタック」の機能としてみた場合は、同じになっています。
ですから、これは、「スタック」という、「インターフェイス」と、具体的にどうデータを持つかという「実装」が別物だというひとつの例になっています。

最後に、なぜ、配列版と連結リスト版では、データの持ち方が逆になっているのか。
これは、

配列：すでにあるデータの位置は固定されている。これにデータを追加しようとすれば、まだデータのないところ、すなわち、配列の最後に追加していかなければならない。
つまり、多くの場合、スタックは先頭→最後尾に伸びる。

連結リスト：リスト構造なので、本来データの挿入・削除の自由度は高い。しかし、単方向連結リストなので、先頭の要素以外の要素にアクセスするのは大変。
（その要素まで、先頭から順次ポインタをたどる必要があるから）
すなわち、データの挿入は、もっとも参照コストの低い、「先頭」の要素に対して行われる。
つまり、スタックは、最後尾→先頭 の方向に伸びる。

これが、このプログラムで（そして、多くの場合は、同じですが）配列版と連結リスト版で、データののび方が逆になる理由です。

回答No.2

dra2jp

それぞれのプログラムのxを追加する部分を見てください。
実際追加の作業が行われている部分はここですね。

配列のスタック
stack[p++] = x;
リストのinsert
start->num = x;

渡されたxは配列の場合、
stack[0]
stack[1]
stack[2]
stack[3]
stack[4]...
の順番に格納されています。

リストの場合、
リストの先頭へ先頭へ追加されていっています。
x
x□
x□□
x□□□...

つまり番号で説明したら

0
1 0
2 1 0
3 2 1 0
4 3 2 1 0

と成っています。
printlist文はどちらも順番に表示するようになっているので、
配列は0,1,2,3,4と
リストは4,3,2,1,0と表示されるわけですね。

回答No.1

BLUEPIXY

参考のプログラムが
配列を用いた場合、最後のデータに追加するようになっていて、
表示するときは、先頭から表示するようになっていて。
リストをもちいた方は、先頭のデータに追加するようになっていて
表示するときは、先頭から表示するようになっているから。