【アルゴリズム】Javaプログラマのためのアルゴリズムとデータ構造(第4章)

4.2 スタック

スタックとは挿入と削除がリストの先頭のみで行われるもの。挿入をPush、削除をpopという。本を地面に並べるイメージ

挿入(enqueue)が一方の端のみで行われ、削除(dequeue)が反対の端でのみ行われるリストのこと。 ATMで順番待ちをしているイメージ

リストは要素を線形に並べたものなので配列で表現できそう。

リストに関する操作の計算量 n個の要素が含まれていると考えて、k番目の要素の前に新たな要素を追加するには、k番目以降の要素を1つずらしてからk番目に要素をいれる。平均n/2個の要素を移動しなければならないため、O(n)となる。削除も同じO(n)

k番目の要素の内容の読み書きは、配列の要素x[k-1]を参照すればよいので計算量はO(1)

結論として、任意の位置に要素を挿入したり、任意の要素を削除するのにO(n)も計算量を使うので配列は一般的なリストを表現するのに適したデータ型ではない。しかし、リストのうちスタックと待ち行列という特別ケースに限れば配列によって効率よく表現できる。

配列を使ってスタックを実現するには一般的なリストとは逆向きに要素をいれるようにする。配列xを使うとすると、x[0]が底で、x[n-1]が頂上。このとき変数nはスタックポインタと呼ばれ、次に要素が積まれる位置を指す。

スタックにデータを挿入するには

x[n++] = data;

スタックからデータを削除するには

data = x[n--];

とする。このようにスタックの場合データの挿入・削除の計算量はO(1)ですむ。