Loading article…
コンピュータサイエンスにおいて、スタックは抽象データ型であり、主に2つの操作を持つ要素の集合として機能する。
さらに、ピーク操作はスタックを変更することなく、最後に追加された要素（スタックの最上位にある要素）の値を返すことができます。スタックという名前は、皿の山のように、物理的なアイテムが積み重ねられた状態を比喩的に表しています。
スタックに要素を追加または削除する順序は、後入れ先出し（LIFO）と呼ばれます。[注1 ]物理的なオブジェクトのスタックと同様に、この構造ではスタックの一番上のアイテムを取り出すのは簡単ですが、スタックの奥にあるデータにアクセスするには、まず他の複数のアイテムを取り出す必要がある場合があります。[ 1 ]
スタックは、要素を順次連結する構造であり、プッシュ操作とポップ操作が可能な唯一の位置であるスタックの最上部と、要素が固定された最下部を持ちます。スタックは、例えば、最上部の要素へのポインタを持つ単方向連結リストとして実装できます。
スタックは容量に制限を設けて実装されることがあります。スタックが満杯で、新たな要素を受け入れるための十分なスペースがない場合、スタックはスタックオーバーフロー状態になります。
スタックは1946年にコンピュータ科学の文献に登場し、アラン・チューリングがサブルーチンの呼び出しと戻りの手段として「bury」と「unbury」という用語を使用した。[ 2 ] [ 3 ]サブルーチンと2レベルのスタックは、 1945年にコンラート・ツーゼのZ4ですでに実装されていた。[ 4 ] [ 5 ]
ミュンヘン工科大学のクラウス・ザメルソンとフリードリヒ・L・バウアーは、 1955年にOperationskeller（「操作の地下室」）と呼ばれるスタックのアイデアを提案し[ 6 ] [ 7 ]、1957年に特許を出願した[ 8 ] [ 9 ] [ 10 ] [ 11 ]。 1988年3月、ザメルソンが亡くなる前に、バウアーはスタック原理の発明によりIEEEコンピュータパイオニア賞を受賞した[ 12 ] [ 7 ] 。同様の概念は、1954年前半にチャールズ・レナード・ハンブリン[ 13 ] [ 7 ]によって、また1958年にヴィルヘルム・ケメラーがautomatisches Gedächtnis（「自動メモリ」）で独自に開発した[ 14 ] [ 15 ] [ 7 ]。
スタックは、カフェテリアのバネ仕掛けの皿の山に例えられることが多い。[ 16 ] [ 1 ] [ 17 ]きれいな皿がスタックの上に置かれ、既にある皿を押し下げる。スタックから一番上の皿が取り除かれると、その下の皿が持ち上げられて新しい一番上の皿になる。
多くの実装では、スタックには必須の「push」と「pop」操作以外にも多くの操作があります。必須ではない操作の例としては、「スタックの先頭」または「peek」があり、これはスタックから要素を削除せずに最上位の要素を観察します。[ 18 ]これは「pop」の後に「push」を実行して同じデータをスタックに戻す操作に分解できるため、必須の操作とはみなされません。スタックが空の場合、「peek」または「pop」操作を実行するとアンダーフロー状態が発生します。さらに、多くの実装には、スタックが空かどうかを確認したり、スタックのサイズを返したりするなど、一般的なタスクを処理する便利な操作が含まれています。
スタックは、単にリストの特殊なケースであるため、配列またはリンクリストのどちらでも簡単に実装できます。 [ 19 ]いずれの場合も、データ構造をスタックとして識別するのは実装ではなくインターフェースです。ユーザーは、配列またはリンクリストに項目をポップまたはプッシュすることしかできず、他のヘルパー操作はほとんどありません。以下では、擬似コードを使用して両方の実装を示します。
配列は、以下のように（境界付き）スタックを実装するために使用できます。最初の要素（通常はオフセット0）は最下層であり、array[0]スタックに最初にプッシュされる要素、および最後にポップされる要素となります。プログラムは、これまでにプッシュされた項目の数を記録する変数topを使用してスタックのサイズ（長さ）を追跡する必要があります。これにより、次の要素が挿入される配列内の位置が示されます（0ベースのインデックス規則を想定）。したがって、スタック自体は、3つの要素からなる構造として効果的に実装できます。
構造スタック: 最大サイズ：整数 上：整数 アイテム: アイテムの配列
プロシージャinitialize(stk : スタック、size : 整数): stk.items ←サイズアイテムの新しい配列（最初は空） stk.maxsize ← サイズ stk.top ← 0
プッシュ操作は、オーバーフローをチェックした後、要素を追加し、最上位インデックスをインクリメントします。
procedure push(stk : stack, x : item): if stk.top = stk.maxsize: オーバーフローエラーを報告する それ以外： stk.items[stk.top] ← x stk.top ← stk.top + 1
同様に、pop 関数はアンダーフローをチェックした後、最上位インデックスをデクリメントし、以前の最上位項目を返します。
procedure pop(stk : stack): if stk.top = 0: アンダーフローエラーを報告します それ以外： stk.top ← stk.top − 1 r ← stk.items[stk.top] rを返す
動的配列を使用することで、必要に応じてサイズを拡大縮小できるスタックを実装できます。スタックのサイズは動的配列のサイズと全く同じであり、動的配列の末尾への項目の追加や末尾からの項目の削除にかかる償却時間がO(1)であるため、非常に効率的なスタックの実装と言えます。
スタックを実装するもう一つの方法は、単方向連結リストを使用することです。この場合、スタックはリストの「先頭」へのポインタであり、リストのサイズを追跡するためのカウンタが付属している場合もあります。
構造フレーム： データ:アイテム 次へ：フレームまたはnil
構造スタック: ヘッド:フレームまたはnil サイズ：整数
手続きinitialize(stk : stack): stk.head ← nil stk.size ← 0
項目のプッシュとポップはリストの先頭で行われます。この実装ではオーバーフローは発生しません（メモリが枯渇しない限り）。
手続きpush(stk : スタック、x : アイテム): 新しいヘッド ← 新しいフレーム newhead.data ← x newhead.next ← stk.head stk.head ← newhead stk.size ← stk.size + 1
procedure pop(stk : stack): if stk.head = nil: アンダーフローエラーを報告します それ以外： r ← stk.head.data stk.head ← stk.head.next stk.size ← stk.size - 1 rを返す
Perl、LISP、JavaScript、Pythonなどの一部の言語では、標準のリスト/配列型に対してスタック操作のプッシュとポップが利用可能です。一方、Forth系言語（PostScriptを含む）など一部の言語は、プログラマが直接参照および操作できる言語定義のスタックを中心に設計されています。
以下は、 Common Lispでスタックを操作する例です（" > " は Lisp インタプリタのプロンプトです。" > " で始まらない行は、式に対するインタプリタの応答です）。
> ( setf stack ( list 'a 'b 'c )) ;; 変数 "stack" を設定します( A B C ) > ( pop stack ) ;; スタックAを変更する必要がある最上位 (左端) 要素を取得します> stack ;; stack の値を確認します( B C ) > ( push 'new stack ) ;; 新しい最上位要素をスタックにプッシュします( NEW B C )C++ 標準ライブラリのコンテナ型のいくつかは、LIFO セマンティクスを持つ操作push_back()と操作を備えています。さらに、テンプレートクラスは既存のコンテナを適応させ、プッシュ/ポップ操作のみを持つ制限されたAPIを提供します。PHP にはクラスがあります。Java ライブラリには、の特殊化であるクラスが含まれています。以下は、そのクラスを使用したJava言語のサンプル プログラムです。pop_back()std::stackSplStackStackVector
パッケージorg.wikipedia.examples ;import java.util.Stack ;public class Example { public static void main ( String [] args ) { Stack < Character > stack = new Stack <> (); stack . push ( 'a' ); // スタックに 'a' を挿入 stack . push ( ' b' ); // スタックに 'b' を挿入stack . push ( 'c' ); // スタックに 'c' を挿入 stack . push ( ' d' ); // スタックに 'd' を挿入System . out . println ( stack . peek ()); // スタックの最上位 ('d') を表示stack . pop (); // 最上位 ('d') を削除stack . pop (); // 次の最上位 ('c') を削除} }PDP-11、VAX、Motorola 68000シリーズなどの一部のプロセッサには、スタック操作に便利なアドレッシングモードが備わっています。以下の簡単なPDP-11アセンブリソースコードは、2つの数値をスタックにプッシュして加算し、結果をスタックに残します。
; R0 はスタック領域を指していると想定されます; -(R0) はスタックポインタを前置デクリメントしてスタックに項目を割り当てます; (R0)+ はスタックポインタを後置インクリメントしてスタックから項目を削除します; MOV #12,-(R0) ; 12 をスタックにプッシュしますMOV #34,-(R0) ; 34 をスタックにプッシュしますADD ( R0 ) + ,( R0 ) ; スタックから 34 をポップして 12 に加算します; 結果をスタックに残しますアーキテクチャレベルにおけるスタックの一般的な用途は、メモリの割り当てとアクセス手段として用いられることである。
典型的なスタックとは、固定された開始位置を持ち、サイズが可変なコンピュータメモリ領域です。スタックの初期サイズはゼロです。スタックポインタ（通常はプロセッサレジスタの形式）は、スタック上で最後に参照された位置を指します。スタックのサイズがゼロの場合、スタックポインタはスタックの開始位置を指します。
すべてのスタックに適用できる2つの操作は次のとおりです。
スタック操作の基本原理には多くのバリエーションが存在する。どのスタックも、メモリ上の固定された開始位置を持つ。スタックにデータ項目が追加されると、スタックポインタが移動してスタックの現在の範囲を示し、スタックは開始位置から離れて拡張していく。
スタックポインタは、スタックの起点、または起点より上または下の限られた範囲のアドレスを指すことができます（スタックが成長する方向によって異なります）。ただし、スタックポインタはスタックの起点を超えることはできません。つまり、スタックの起点がアドレス1000にあり、スタックが下方向（アドレス999、998など）に成長する場合、スタックポインタは1000を超えて（1001以降に）インクリメントされてはなりません。スタックに対するポップ操作によってスタックポインタがスタックの起点を超えて移動すると、スタックアンダーフローが発生します。プッシュ操作によってスタックポインタがスタックの最大範囲を超えてインクリメントまたはデクリメントされると、スタックオーバーフローが発生します。
スタックに大きく依存する環境によっては、次のような追加操作が提供される場合があります。
スタックは、現実世界のスタックのように、下から上に成長していく様子として視覚化されることが多い。また、左から右に成長していく様子（一番右が上）や、上から下に成長していく様子として視覚化されることもある。重要なのは、スタックの一番下が固定された位置にあることである。このセクションの図は、上から下に成長していく様子を視覚化した例である。スタックの「上」（9）はアイテムが押し出されたり取り出されたりする場所であるため、上（28）がスタックの「下」となる。
右回転を行うと、最初の要素は3番目の位置に、2番目の要素は最初の位置に、3番目の要素は2番目の位置に移動します。このプロセスを視覚的に表した2つの例を以下に示します。
リンゴバナナ バナナ ===右回転==> キュウリ キュウリ リンゴ
キュウリ リンゴ バナナ ===左回転==> キュウリ リンゴバナナ
スタックは通常、コンピュータではメモリセルのブロックとして表現され、「ボトム」は固定位置にあり、スタックポインタはスタック内の現在の「トップ」セルのアドレスを保持します。「トップ」と「ボトム」という表記は、スタックが実際に高いメモリアドレスに向かって拡張されるかどうかに関係なく使用されます。
スタックに項目をプッシュすると、スタックポインタは項目のサイズ分だけ調整され（メモリ内でスタックが成長する方向に応じて、減少または増加します）、次のセルを指すようになり、新しい最上位項目がスタック領域にコピーされます。実装方法によって異なりますが、プッシュ操作の終了時には、スタックポインタはスタック内の次の未使用位置を指す場合もあれば、スタックの最上位項目を指す場合もあります。スタックが現在の最上位項目を指している場合は、新しい項目がスタックにプッシュされる前にスタックポインタが更新されます。スタック内の次の使用可能な位置を指している場合は、新しい項目がスタックにプッシュされた後に更新されます。
スタックから要素をポップする操作は、プッシュする操作の逆の操作です。スタックの最上位の要素が削除され、スタックポインタが更新されます。更新順序はプッシュ操作とは逆になります。
x86、Z80、6502など、多くのCISC型CPU設計では、コールスタックのスタックポインタとして使用できる専用レジスタが用意されており、専用のcall、return、push、pop命令によってこの専用レジスタが暗黙的に更新されるため、コード密度が向上します。PDP -11や68000などの一部のCISCプロセッサでは、スタックを実装するための特別なアドレッシングモードも用意されており、通常は半専用のスタックポインタ（68000のA7など）も備えています。これに対し、ほとんどのRISC型CPU設計では専用のスタック命令がないため、必要に応じてほとんど、あるいはすべてのレジスタをスタックポインタとして使用できます。
一部の機械は、算術演算と論理演算にスタックを使用します。オペランドはスタックにプッシュされ、算術演算と論理演算はスタックの最上位の1つまたは複数の項目に対して実行され、それらの項目がスタックからポップされ、結果がスタックにプッシュされます。このように動作する機械はスタックマシンと呼ばれます。
メインフレームやミニコンピュータの多くはスタックマシンであり、最も有名なのはバローズ・ラージ・システムズである。その他の例としては、CISC方式のHP 3000マシンや、タンデム・コンピュータ社のCISCマシンなどが挙げられる。
x87浮動小数点アーキテクチャは、スタックとして構成されたレジスタ群の一例であり、個々のレジスタへの直接アクセス（現在の最上位レジスタからの相対的なアクセス）も可能である。
スタックの最上位を暗黙の引数として持つことで、バス帯域幅とコードキャッシュを効率的に利用しながら、マシンコードのフットプリントを小さくすることができます。しかし、すべての（2つまたは3つの）オペランドに対してレジスタファイルへのランダムアクセスを許可するプロセッサで可能な一部の最適化は妨げられます。また、スタック構造は、レジスタリネーミング（投機的実行のため）を備えたスーパースカラ実装をやや複雑にしますが、最新のx87実装に見られるように、依然として実現可能です。
Sun SPARC、AMD Am29000、Intel i960はすべて、レジスタスタック内にレジスタウィンドウを使用することで、関数引数や戻り値に低速なメインメモリを使用することを回避する戦略を採用しているアーキテクチャの例である。
ハードウェアでスタックを直接実装する小型マイクロプロセッサも多数存在し、一部のマイクロコントローラは直接アクセスできない固定深度のスタックを備えています。例としては、PICマイクロコントローラ、Computer Cowboys MuP21、Harris RTXシリーズ、Novix NC4016などがあります。少なくとも1つのマイクロコントローラファミリであるCOP400は、デバイスに応じて、ハードウェアで直接スタックを実装するか、スタックポインタを介してRAMにスタックを実装します。多くのスタックベースのマイクロプロセッサは、マイクロコードレベルでプログラミング言語Forthを実装するために使用されました。
逆ポーランド記法を用いる電卓は、値を保持するためにスタック構造を使用します。式は前置記法、後置記法、中置記法で表現でき、スタックを使用してある形式から別の形式への変換を行うことができます。多くのコンパイラは、低レベルコードへの変換前に構文解析を行うためにスタックを使用します。ほとんどのプログラミング言語は文脈自由言語であるため、スタックベースのマシンで解析できます。
スタックのもう一つの重要な応用例は、バックトラッキングです。その一例として、一連の点、開始点、複数の経路、そして目的地を含む迷路で正しい経路を見つけるという単純な例が挙げられます。ランダムな経路を選択する必要がある場合、間違った経路をたどった後に、その経路の先頭に戻る方法が必要です。これはスタックを使用することで実現できます。最後に正しい点をスタックにプッシュし、間違った経路をたどった場合はスタックからポップすればよいのです。
バックトラッキングアルゴリズムの典型的な例は深さ優先探索であり、これは指定された開始頂点から到達可能なグラフのすべての頂点を見つけます。バックトラッキングの他の応用例としては、最適化問題の潜在的な解を表す空間を探索することが挙げられます。分岐限定法は、そのような空間内のすべての潜在的な解を網羅的に探索することなく、バックトラッキング探索を実行する手法です。
多くのプログラミング言語はスタック指向であり、基本的な操作（2つの数値の加算、文字の印刷など）は、引数をスタックから取得し、戻り値をスタックに戻すという形で定義されています。例えば、PostScriptには戻り値スタックとオペランドスタックがあり、さらにグラフィックス状態スタックと辞書スタックも備えています。pコードマシンやJava仮想マシンなど、多くの仮想マシンもスタック指向です。
ほぼすべての呼び出し規約（サブルーチンがパラメータを受け取り、結果を返す方法）は、特別なスタック（ 「コールスタック」）を使用して、プロシージャ/関数呼び出しとネストに関する情報を保持し、呼び出された関数のコンテキストに切り替え、呼び出しが終了したら呼び出し元の関数に戻ります。関数は、呼び出し元と呼び出し先の間で実行時プロトコルに従って、引数と戻り値をスタックに保存します。スタックは、ネストされた関数呼び出しや再帰関数呼び出しをサポートする重要な方法です。このタイプのスタックは、コンパイラによって暗黙的に使用され、CALL および RETURN ステートメント（またはそれに相当するもの）をサポートし、プログラマによって直接操作されることはありません。
一部のプログラミング言語では、プロシージャ内でローカルなデータを格納するためにスタックを使用します。ローカルデータ項目用の領域は、プロシージャの開始時にスタックから割り当てられ、プロシージャの終了時に解放されます。C言語は一般的にこの方法で実装されています。データとプロシージャ呼び出しの両方に同じスタックを使用することは、重要なセキュリティ上の影響（下記参照）があり、プログラマはプログラムに深刻なセキュリティバグを混入させないように、これらの影響を認識しておく必要があります。
いくつかのアルゴリズムは、（ほとんどのプログラミング言語の通常の関数呼び出しスタックとは別の）スタックを主要なデータ構造として使用し、情報を整理します。これには以下が含まれます。
一部のコンピューティング環境では、スタックをセキュリティ侵害や攻撃に対して脆弱な方法で使用する場合があります。そのような環境で作業するプログラマーは、これらの実装における落とし穴を避けるために特に注意を払う必要があります。
例えば、一部のプログラミング言語では、呼び出されたプロシージャのローカルデータと、プロシージャが呼び出し元に戻るために必要なリンク情報の両方を格納するために、共通のスタックを使用します。つまり、プログラムはプロシージャ呼び出しの重要な戻りアドレスを含む同じスタックにデータを出し入れします。データがスタック上の誤った場所に移動されたり、大きすぎるデータ項目がそれを格納するのに十分な大きさではないスタック位置に移動されたりすると、プロシージャ呼び出しの戻り情報が破損し、プログラムが失敗する可能性があります。
悪意のある第三者は、入力の長さをチェックしないプログラムに過大なデータ入力を与えることで、この種の実装を悪用したスタック破壊攻撃を試みる可能性があります。このようなプログラムは、データ全体をスタック上の場所にコピーし、その際に、自身を呼び出したプロシージャの戻りアドレスを変更する可能性があります。攻撃者は、このようなプログラムに提供できる特定の種類のデータを探し出す実験を行い、現在のプロシージャの戻りアドレスがスタック自体（攻撃者が提供したデータ内）の領域を指すようにリセットされ、その領域に不正な操作を実行する命令が含まれるようにすることができます。
この種の攻撃はバッファオーバーフロー攻撃の一種であり、ソフトウェアにおけるセキュリティ侵害の非常に頻繁な原因となっています。これは主に、最も普及しているコンパイラの一部がデータとプロシージャ呼び出しの両方に共有スタックを使用し、データ項目の長さを検証しないためです。プログラマーもデータ項目のサイズを検証するコードを記述しないことが多く、サイズが大きすぎる、または小さすぎるデータ項目がスタックにコピーされると、セキュリティ侵害が発生する可能性があります。
Die Bezeichnung 'Keller' hierfür wurde von Bauer und Samelson in einer deutschen Patentanmeldung vom 30. März 1957 eingefüult.
この記事は、ポール・E・ブラック著「境界付きスタック」、『アルゴリズムとデータ構造の辞典』、NIST のパブリックドメイン資料を組み込んでいます。
