典型的なスタック
出典: フリー百科事典『ウィキペディア(Wikipedia)』 (2022/03/09 23:01 UTC 版)
典型的なスタックはコンピュータのメモリ上に固定の基点と可変のサイズを持つ領域である。初期状態ではスタックのサイズはゼロである。「スタックポインタ」(一般にハードウェアのレジスタが使われる)はスタック内で最も後で参照された位置を指している。スタック長がゼロのとき、スタックポインタはスタックの基点を指す。 あらゆるスタックで実施可能な2つの操作は以下の通りである。 Push操作 スタックポインタが指す場所にデータを格納し、そのデータのサイズのぶんだけスタックポインタをずらす。 Pop操作 スタックポインタが指している現在位置にあるデータを取り出し、スタックポインタをそのデータのぶんだけ(Pushとは逆方向に)ずらす。 スタック操作の基本原則には様々なバリエーションがある。スタックは初期状態ではメモリ上の固定の位置に配置される。データがスタックに追加されると、スタックポインタはデータ追加に伴うスタックの領域拡張に従って変更される。そのときのスタックの延びていく方向は特に規則は無く、実装によってアドレスの小さくなる方向だったり、大きくなる方向だったりする。 昔のコンピュータで、ヒープ領域をアドレスの小さいほうから大きいほうへ伸ばし、スタックを大きいほうから小さいほうへ伸ばす(そのようにすると、メモリが足りない場合はどちらを伸ばす余裕もなく、完全にメモリを使い切って計算続行不可能となる)という設計にした名残りから、アドレスの大きいほうから小さいほうへ伸びるものが多いが、PA-RISCは逆である。 例えば、あるスタックが1000番地から開始して、アドレスの小さい方向に延びていくとする。その場合、データは1000番地よりも小さい番地に格納され、スタックポインタはそれに伴って小さな番地を格納するようになる。そのスタックからデータをPopすると、スタックポインタに格納されているアドレスは大きくなる。 (初期状態の)スタックポインタはスタックの基点そのものではなく、その少し上か下(スタック成長方向に依存)の限界アドレスを指している場合もある。しかし、スタックポインタは基点を超えていくことはできない。換言すれば、スタックの基点が1000番地でスタックがアドレスの小さい方向(999番地、998番地など)に成長する場合、スタックポインタは決して1000番地を超えてはならない(1001番地や1002番地は不可)。Pop操作によってスタックポインタが基点を超えると「スタック・アンダーフロー」が発生する。逆にPush操作がスタックの最大許容範囲を超えてスタックポインタを操作することになるなら「スタック・オーバーフロー」が発生する。 スタックに強く依存している環境では、追加の操作を備えている場合がある。以下に例をあげる。 Dup(licate) トップのアイテムを pop して2回 push する。これによって元のスタックトップのアイテムが2個スタックトップに存在することになる。 Peek トップのアイテムを pop するが、スタックポインタを変更せず、スタックのサイズも変化しない(つまり、アイテムはスタック上に残存する)。Top 操作と呼ぶことも多い。 Swap または Exchange スタックトップの2つのアイテム(つまり一番目と二番目)を入れ替える。 Rotate トップの n 個のアイテムを回転するように入れ替える。例えば、n = 3 で、スタックに 1、2、3 が順に置かれているとき、この順番を 2、3、1 のように変化させる。この操作はバリエーションが多く、一般には left rotate(左回転)とright rotate(右回転)と呼ばれる操作を備えることが多い。 スタックは上に成長するようにイメージされることもあるし、左から右に成長するようにイメージされることもあり、トップという言い方ではなく右端と言ったりもする。このようなイメージはメモリ上のスタックの実際の構造とはあまり関係ない。right rotateと言ったとき、一番目の要素を三番目の位置に置き、二番目を一番目、三番目を二番目の位置に置く。これを二種類のイメージで表すと次のようになる。 apple bananabanana ===right rotate==> cucumbercucumber apple cucumber applebanana ===left rotate==> cucumberapple banana スタックはコンピュータ内では通常、メモリセルのブロックで構成される。そのブロックの「底」は固定の位置にあり、スタックポインタが「トップ」のセルのアドレスを格納している。「底」とか「トップ」という用語はスタックがアドレスの大きくなる方向に成長するか、小さくなる方向に成長するかに関係なく使われる。 スタックへのアイテムの push により、そのアイテムのサイズのぶんだけスタックポインタがずらされ(増減はメモリ空間内のスタックの成長方向に依存する)、次のセルを指すようにして、新たなトップとなるアイテムをスタック領域にコピーする。詳細な実装に依存するが、push 操作を完了したときのスタックポインタの値はスタック上の次の未使用領域を指しているかもしれないし、現在のトップのアイテムを指しているかもしれない。スタックポインタが現在のトップのアイテムを指している場合、次回の push のときには最初にスタックポインタをずらさなければならない。逆にスタックポインタが次の未使用領域を指しているなら、次回の push のときには最後にスタックポインタをずらすことになる。 スタックの pop 操作は push の逆となる。Push とは逆の順番でスタックのトップのアイテムが取り出され、スタックポインタが更新される。
※この「典型的なスタック」の解説は、「スタック」の解説の一部です。
「典型的なスタック」を含む「スタック」の記事については、「スタック」の概要を参照ください。
- 典型的なスタックのページへのリンク