スタック（抽象データ型）

コンピュータ サイエンスにおいて、スタックとは、主に次の 2 つの操作を持つ要素の コレクションとして機能する抽象データ型です。

• Pushはコレクションに要素を追加し、
• Pop は、最後に追加された要素を削除します。

さらに、ピーク操作は、スタックを変更せずに、最後に追加された要素の値を返すことができます。スタックという名前は、皿の積み重ねなど、物理的に積み重ねられた一連のアイテムに 似ています。

スタックに要素を追加したりスタックから要素を削除したりする順序は、後入れ先出し( LIFO )と表現されます。^{[注 1]}物理的なオブジェクトのスタックと同様に、この構造により、スタックの一番上からアイテムを簡単に取り出すことができますが、スタックのより深いデータにアクセスするには、最初に他の複数のアイテムを削除する必要がある場合があります。^[1]

スタックは順次的なコレクションとして考えられ、プッシュおよびポップ操作が実行できる唯一の位置であるスタックの最上部の一方の端と、スタックの最下部のもう一方の端が固定されています。スタックは、たとえば、最上位要素へのポインタを持つ 単一リンク リストとして実装できます。

スタックは、制限された容量を持つように実装される場合があります。スタックがいっぱいで、別の要素を受け入れるのに十分なスペースがない場合、スタックはスタック オーバーフローの状態になります。

深さ優先探索を実装するにはスタックが必要です。

スタックがコンピュータサイエンスの文献に登場したのは1946年で、アラン・チューリングがサブルーチンの呼び出しと戻りの手段として「bury」と「unbury」という用語を使用したときである。^{[2] [3]} サブルーチンと2レベルスタックは、1945年にコンラート・ツーゼのZ4ですでに実装されていた。^{[4] [5]}

ミュンヘン工科大学のクラウス・ザメルソンとフリードリヒ・L・バウアーは、1955年にOperationskeller（「操作用セラー」）と呼ばれるスタックのアイデアを提案し、1957年に特許を申請しました。 ^{[ 6] [7] [8] [9] [10] [11]} 1988年3月、ザメルソンが亡くなる頃に、バウアーはスタック原理の発明によりIEEEコンピュータパイオニア賞を受賞しました。 ^{[12] [7]}同様の概念は、1954年前半にチャールズ・レナード・ハンブリンによって独立して開発され、 ^{[13] [7]}、1958年にヴィルヘルム・ケメラー [de]によってautomatisches Gedächtnis（「自動メモリ」）が開発されました。 ^{[14] [15] [7]}

スタックは、カフェテリアのバネ仕掛けの皿の積み重ねの例えで説明されることが多い。^{[16] [1] [17]}清潔な皿がスタックの上に置かれ、すでに積み重ねられている皿を押し下げる。スタックから一番上の皿が取り除かれると、その下の皿が持ち上げられて新しい一番上の皿になる。

多くの実装では、スタックには必須の「プッシュ」および「ポップ」操作以外にも多くの操作があります。必須でない操作の例としては、「スタックのトップ」または「ピーク」があり、これはスタックからトップ要素を削除せずに観察します。^[18]これは「ポップ」とそれに続く「プッシュ」に分解でき、同じデータをスタックに返すことができるため、必須の操作とは見なされません。スタックが空の場合、「スタックのトップ」または「ポップ」操作のいずれかを実行すると、アンダーフロー状態が発生します。さらに、多くの実装では、スタックが空かどうかのチェックと、そのサイズを返す操作が提供されています。

スタックは単にリストの特殊なケースに過ぎないので、配列またはリンクリストのいずれかを介して簡単に実装できます。 ^[19]どちらの場合でも、データ構造をスタックとして識別するのは実装ではなくインターフェイスです。ユーザーは、配列またはリンクリストにアイテムをポップまたはプッシュすることしかできず、他のヘルパー操作はほとんどありません。以下では、疑似コードを使用して両方の実装を示します。

配列は、次のように (境界付き) スタックを実装するために使用できます。通常、ゼロ オフセットにある最初の要素は一番下にあり、array[0]スタックにプッシュされる最初の要素とポップされる最後の要素になります。プログラムは、スタックのサイズ (長さ) を追跡する必要があります。そのためには、これまでにプッシュされた項目の数を記録する変数top を使用する必要があります。これにより、配列内で次の要素が挿入される場所が示されます (ゼロベースのインデックス規則を想定)。したがって、スタック自体は、3 つの要素の構造として効果的に実装できます。

構造スタック:
    最大サイズ: 整数
    上: 整数
    items : アイテムの配列

手順初期化(stk: スタック、サイズ: 整数):stk.items ←サイズ項目
    の新しい配列。最初は空です。
    stk.maxsize ← サイズ
    stk.top ← 0

プッシュ操作は、オーバーフローをチェックした後、要素を追加し、先頭のインデックスを増分します。

手順push(stk:stack,x:item):
     stk.top = stk.maxsizeの場合:
        オーバーフローエラーを報告する
    それ以外：
        stk.items[stk.top] ← x
        stk.top ← stk.top + 1

同様に、pop はアンダーフローをチェックした後、先頭のインデックスを減算し、以前は先頭だった項目を返します。

手順pop(stk : stack):
     stk.top = 0の場合:
        アンダーフローエラーを報告する
    それ以外：
        stk.top ← stk.top − 1
        r ← stk.items[stk.top]
        rを
返す

動的配列を使用すると、必要に応じて拡大または縮小できるスタックを実装できます。スタックのサイズは動的配列のサイズと同じで、動的配列の末尾に項目を追加したり、動的配列の末尾から項目を削除したりするには償却 O(1) 時間しかかからないため、これはスタックの非常に効率的な実装です。

スタックを実装する別のオプションは、単方向リンク リストを使用することです。スタックはリストの「先頭」へのポインターであり、リストのサイズを追跡するためのカウンターが付いている場合があります。

構造フレーム:
    データ: 項目
    next : フレームまたはnil

構造スタック:
    ヘッド: フレームまたはnil
    サイズ: 整数

手順initialize(stk:stack):
    stk.head ← なし
    stk.サイズ ← 0

アイテムのプッシュとポップはリストの先頭で行われます。この実装ではオーバーフローは発生しません (メモリが使い果たされない限り)。

手順push(stk:スタック、x:項目):
    newhead ← 新しいフレーム
    newhead.data ← x
    newhead.next ← stk.head
    stk.head ← ニューヘッド
    stk.size ← stk.size + 1

手順pop(stk : stack):
     stk.head = nilの場合:
        アンダーフローエラーを報告する
    r ← stk.head.data
    stk.head ← stk.head.next
    stk.size ← stk.size - 1
    rを
返す

Perl、LISP、JavaScript、Pythonなどの一部の言語では、スタック操作 push と pop を標準のリスト/配列型で使用できます。一部の言語、特にForthファミリ ( PostScriptを含む) は、プログラマが直接表示して操作できる言語定義のスタックを中心に設計されています。

以下は、 Common Lispでスタックを操作する例です(「>」は Lisp インタープリターのプロンプトです。「>」で始まっていない行は、式に対するインタープリターの応答です)。

> ( setf stack ( list 'a 'b 'c )) ;; 変数 "stack" を設定します( A B C ) > ( pop stack ) ;; 一番上の (左端の) 要素を取得し、スタックを変更しますA > stack ;; スタックの値を確認します( B C ) > ( push 'new stack ) ;; 新しいトップをスタックにプッシュします( NEW B C )        
  
    

         
 
     
  

C++ 標準ライブラリのコンテナ タイプのいくつかには、LIFO セマンティクスによるpush_backおよびpop_back操作があります。さらに、 stackテンプレート クラスは既存のコンテナを適応させて、push/pop 操作のみの制限されたAPI を提供します。PHP には SplStack クラスがあります。Java のライブラリには、を特殊化したクラスが含まれています。以下は、そのクラスを使用したJava言語のサンプル プログラムです。 StackVector

java.util.Stackをインポートします。 

クラス StackDemo { public static void main ( String [] args ) { Stack < String > stack = new Stack < String > (); 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") を削除} } 
        
            
            
            
            
            
            
            
            
    

アーキテクチャ レベルでのスタックの一般的な用途は、メモリの割り当てとアクセスの手段として使用することです。

典型的なスタックは、固定の起点と可変のサイズを持つコンピュータ メモリの領域です。スタックのサイズは最初 0 です。スタック ポインター(通常はプロセッサ レジスタの形式) は、スタック上で最後に参照された場所を指します。スタックのサイズが 0 の場合、スタック ポインターはスタックの起点を指します。

すべてのスタックに適用可能な 2 つの操作は次のとおりです。

• プッシュ操作: スタック ポインター内のアドレスがデータ項目のサイズによって調整され、スタック ポインターが指す場所にデータ項目が書き込まれます。
• ポップまたはプル操作: スタック ポインターが指している現在の位置にあるデータ項目が読み取られ、スタック ポインターがそのデータ項目のサイズに対応する距離だけ移動されます。

スタック操作の基本原理にはさまざまなバリエーションがあります。すべてのスタックには、メモリ内で開始する固定位置があります。データ項目がスタックに追加されると、スタック ポインターは移動してスタックの現在の範囲を示し、スタックは原点から拡大します。

スタック ポインターは、スタックの起点を指すことも、起点の上または下の限られた範囲のアドレスを指すこともできます (スタックが成長する方向によって異なります)。ただし、スタック ポインターはスタックの起点を越えることはできません。つまり、スタックの起点がアドレス 1000 にあり、スタックが下方向に成長する場合 (アドレス 999、998 など)、スタック ポインターは 1000 を超えて (1001 以上に) 増加してはなりません。スタックのポップ操作によってスタック ポインターがスタックの起点を超えて移動すると、スタック アンダーフローが発生します。プッシュ操作によってスタック ポインターがスタックの最大範囲を超えて増加または減少すると、スタック オーバーフローが発生します。

スタックに大きく依存する環境では、次のような追加の操作が提供される場合があります。

• 複製: 一番上の項目がポップされ、その後 2 回プッシュされます。これにより、以前の一番上の項目の 2 つのコピーが最上部に配置されます。
• Peek : 最上位の項目が検査 (または返される) されますが、スタック ポインターとスタック サイズは変更されません (つまり、項目はスタック上に残ります)。これは、トップ操作とも呼ばれます。
• スワップまたは交換: スタック交換の場所の一番上の 2 つの項目。
• 回転 (またはロール) :スタック上の最上位のn 個の項目が回転しながら移動します。たとえば、n = 3の場合、スタック上の項目 1、2、3 は、それぞれスタック上の位置 2、3、1 に移動されます。この操作には多くのバリエーションがありますが、最も一般的なものは左回転と右回転と呼ばれます。

スタックは、多くの場合、下から上に成長するものとして視覚化されます (実際のスタックと同様)。また、左から右に成長するものとして視覚化されることもあります (この場合、スタックの最上部は右端になります)。さらに、上から下に成長するものとして視覚化されることもあります。重要な点は、スタックの最下部が固定位置にあることです。このセクションの図は、上から下への成長の視覚化の例です。スタックの最上部 (28) はスタックの「下部」です。スタックの最上部 (9) は、アイテムがプッシュまたはポップされる場所です。

右に回転すると、最初の要素が 3 番目の位置に移動し、2 番目の要素が最初の位置に移動し、3 番目の要素が 2 番目の位置に移動します。このプロセスを視覚化した 2 つの例を以下に示します。

リンゴ バナナ
バナナ ===右回転==> キュウリ
キュウリ リンゴ

キュウリ リンゴ
バナナ ===左回転==> キュウリ
リンゴ バナナ

スタックは通常、コンピュータ内ではメモリ セルのブロックで表され、「最下部」は固定位置にあり、スタック ポインタはスタック内の現在の「最上部」セルのアドレスを保持します。「最上部」と「最下部」という命名は、スタックが実際に上位のメモリ アドレスに向かって拡大するかどうかに関係なく使用されます。

スタックにアイテムをプッシュすると、スタック ポインターがアイテムのサイズだけ調整され (メモリ内でスタックが増加する方向に応じて、減少または増加)、次のセルを指し、新しい最上位アイテムがスタック領域にコピーされます。また、正確な実装に応じて、プッシュ操作の終了時に、スタック ポインターはスタック内の次の未使用の場所を指す場合もあれば、スタック内の最上位のアイテムを指す場合もあります。スタックが現在の最上位のアイテムを指している場合、スタック ポインターは新しいアイテムがスタックにプッシュされる前に更新されます。スタック ポインターがスタック内の次の使用可能な場所を指している場合は、新しいアイテムがスタックにプッシュされた 後に更新されます。

スタックのポップは、単にプッシュの逆の操作です。スタックの最上位の項目が削除され、スタック ポインターがプッシュ操作で使用された順序と逆の順序で更新されます。

x86、Z80、6502 を含む多くのCISCタイプのCPU設計には、呼び出しスタックスタック ポインターとして使用するための専用レジスタがあり、専用の呼び出し、戻り、プッシュ、ポップ命令によって暗黙的に専用レジスタが更新されるため、コード密度が向上します。 PDP-11や68000などの一部の CISC プロセッサには、スタックの実装用に特別なアドレッシング モードもあり、通常は半専用スタック ポインターも使用されます (68000 の A7 など)。対照的に、ほとんどのRISC CPU 設計には専用のスタック命令がないため、すべてではないにしてもほとんどのレジスタを必要に応じてスタック ポインターとして使用できます。

一部のマシンでは、算術演算や論理演算にスタックを使用します。オペランドはスタックにプッシュされ、算術演算や論理演算はスタックの一番上の 1 つ以上の項目に対して実行され、それらの項目がスタックからポップされ、結果がスタックにプッシュされます。このように機能するマシンは、スタック マシンと呼ばれます。

多くのメインフレームとミニコンピュータはスタック マシンであり、最も有名なのはBurroughs の大規模システムです。他の例としては、CISC HP 3000マシンやTandem Computersの CISC マシンなどがあります。

x87 浮動小数点アーキテクチャは、 スタックとして編成されたレジスタ セットの例であり、個々のレジスタへの直接アクセス (現在の最上位を基準として) も可能です。

スタックの最上位を暗黙の引数として持つことで、バス帯域幅とコード キャッシュを有効に活用しながらマシン コードのフットプリントを小さくすることができますが、すべての (2 つまたは 3 つの) オペランドに対してレジスタ ファイルへのランダム アクセスを許可するプロセッサで可能な、ある種の最適化も妨げられます。また、スタック構造により、レジスタ名の変更(投機的実行用) を伴うスーパースカラー実装の実装がやや複雑になりますが、最新のx87実装 に例示されているように、それでも実現可能です。

Sun SPARC、AMD Am29000、およびIntel i960はすべて、関数の引数と戻り値に低速のメイン メモリを使用しないようにするための別の戦略として、レジスタ スタック内でレジスタ ウィンドウを使用するアーキテクチャの例です。

ハードウェアで直接スタックを実装する小型マイクロプロセッサも多数存在し、マイクロコントローラの中には直接アクセスできない固定深度のスタックを持つものもあります。例としては、PIC マイクロコントローラ、Computer Cowboys MuP21、Harris RTXシリーズ、Novix NC4016 などがあります。少なくとも 1 つのマイクロコントローラ ファミリ ( COP400 ) は、デバイスに応じて、スタックをハードウェアで直接実装するか、スタック ポインターを介して RAM に実装します。多くのスタックベースのマイクロプロセッサは、マイクロコードレベルでプログラミング言語Forth を実装するために使用されました。

逆ポーランド記法を採用する計算機は、スタック構造を使用して値を保持します。式は、接頭辞、接尾辞、または中置記法で表すことができ、ある形式から別の形式への変換はスタックを使用して実行できます。多くのコンパイラは、低レベルのコードに変換する前に、スタックを使用して構文を解析します。ほとんどのプログラミング言語はコンテキストフリー言語であるため、スタックベースのマシンで解析できます。

スタックのもう 1 つの重要な用途は、バックトラッキングです。これの例として、一連のポイント、開始点、複数のパス、および目的地を含む迷路で正しいパスを見つけるという簡単な例があります。ランダムなパスを選択する必要がある場合、間違ったパスをたどった後、そのパスの先頭に戻る方法が必要です。これは、スタックを使用することで実現できます。最後の正しいポイントをスタックにプッシュし、間違ったパスの場合はスタックからポップすることができます。

バックトラッキング アルゴリズムの典型的な例は深さ優先探索です。これは、指定された開始頂点から到達できるグラフのすべての頂点を見つけます。バックトラッキングの他の用途には、最適化問題に対する潜在的な解決策を表す空間の検索が含まれます。分岐限定法は、そのような空間内のすべての潜在的な解決策を網羅的に検索することなく、このようなバックトラッキング検索を実行するための手法です。

多くのプログラミング言語はスタック指向です。つまり、ほとんどの基本的な操作 (2 つの数値の加算、文字の印刷) は、スタックから引数を取得し、戻り値をスタックに戻すものとして定義されます。たとえば、PostScript には、リターン スタックとオペランド スタックがあり、グラフィックス状態スタックと辞書スタックもあります。pコード マシンやJava 仮想マシンなど、多くの仮想マシンもスタック指向です。

ほとんどすべての呼び出し規約（サブルーチンがパラメータを受け取って結果を返す方法）では、呼び出された関数のコンテキストに切り替えて、呼び出しが終了したときに呼び出し元の関数に復元するために、プロシージャ/関数の呼び出しとネストに関する情報を保持する特別なスタック（「呼び出しスタック」）を使用します。関数は、呼び出し元と呼び出し先の間の実行時プロトコルに従って、引数と戻り値をスタックに保存します。スタックは、ネストされた関数呼び出しや再帰関数呼び出しをサポートする重要な方法です。このタイプのスタックは、CALL ステートメントと RETURN ステートメント（またはそれらに相当するもの）をサポートするためにコンパイラによって暗黙的に使用され、プログラマによって直接操作されることはありません。

一部のプログラミング言語では、スタックを使用してプロシージャのローカル データを保存します。ローカル データ項目のスペースは、プロシージャに入るときにスタックから割り当てられ、プロシージャを終了するときに割り当て解除されます。Cプログラミング言語は通常、このように実装されています。データとプロシージャの呼び出しの両方に同じスタックを使用すると、セキュリティ上の重要な影響があります (以下を参照)。プログラムに重大なセキュリティ バグが入り込むのを避けるために、プログラマーはこれを認識する必要があります。

いくつかのアルゴリズムでは、情報を整理するための 主要なデータ構造としてスタック (ほとんどのプログラミング言語の通常の関数呼び出しスタックとは別) を使用します。これには次のものが含まれます。

• グラハムスキャンは、2次元点群の凸包を求めるアルゴリズムです。入力のサブセットの凸包はスタックに保持され、新しい点が凸包に追加されたときに境界の凹みを見つけて削除するために使用されます。^[20]
• 単調行列の行の最小値を見つけるためのSMAWKアルゴリズムの一部は、グラハムスキャンと同様の方法でスタックを使用します。 ^[21]
• 最も近い小さい値すべて、配列内の各数値に対して、それより小さい最も近い先行する数値を見つける問題。この問題の1つのアルゴリズムは、最も近い小さい値の候補のコレクションを維持するためにスタックを使用します。配列内の各位置について、より小さい値がその先頭に見つかるまでスタックがポップされ、新しい位置の値がスタックにプッシュされます。^[22]
• 最近傍連鎖アルゴリズムは、スタック上の前のクラスターに最も近いクラスターのスタックを維持することに基づく、凝集型階層的クラスタリング手法である。この手法では、互いに最も近いクラスターのペアが見つかると、それらをポップしてマージする。^[23]

一部のコンピューティング環境では、スタックの使用方法によってセキュリティ侵害や攻撃に対して脆弱になる可能性があります。このような環境で作業するプログラマーは、これらの実装でこのような落とし穴を回避するために特別な注意を払う必要があります。

たとえば、一部のプログラミング言語では、呼び出されたプロシージャのローカル データと、プロシージャが呼び出し元に戻ることを可能にするリンク情報の両方を共通のスタックに格納します。つまり、プログラムは、プロシージャ呼び出しの重要な戻りアドレスを含む同じスタックにデータを出し入れします。データがスタック上の間違った場所に移動されたり、大きすぎるデータ項目が、それを収容するのに十分でないスタックの場所に移動されたりすると、プロシージャ呼び出しの戻り情報が破損し、プログラムが失敗する可能性があります。

悪意のある者は、入力の長さをチェックしないプログラムに特大のデータ入力を提供することで、このタイプの実装を利用してスタック破壊攻撃を試みる可能性があります。このようなプログラムは、データ全体をスタック上の場所にコピーし、その際に、呼び出したプロシージャの戻りアドレスを変更する可能性があります。攻撃者は、このようなプログラムに提供できる特定のタイプのデータを見つけるために実験し、現在のプロシージャの戻りアドレスがスタック自体 (および攻撃者によって提供されたデータ内) 内の領域を指すようにリセットされ、その領域には不正な操作を実行する命令が含まれるようにすることができます。

このタイプの攻撃は、バッファ オーバーフロー攻撃のバリエーションであり、ソフトウェアのセキュリティ侵害の非常に頻繁な原因となっています。主な原因は、最も一般的なコンパイラの一部がデータとプロシージャの呼び出しの両方に共有スタックを使用し、データ項目の長さを検証しないことです。プログラマは、データ項目のサイズを検証するコードも作成しないことが多く、大きすぎるデータ項目または小さすぎるデータ項目がスタックにコピーされると、セキュリティ侵害が発生する可能性があります。

•  この記事には、 Paul E. Blackのパブリック ドメイン資料が組み込まれています。「境界スタック」。アルゴリズムとデータ構造の辞書。NIST 。

• Donald Knuth . The Art of Computer Programming、第 1 巻:基本アルゴリズム、第 3 版。Addison - Wesley、1997 年。ISBN 0-201-89683-4 . セクション 2.2.1: スタック、キュー、およびデック、pp. 238–243。 
• ラングマック、ハンス[ドイツ語] (2015) [2014-11-14]。ドイツのキールで書かれました。 Friedrich L. Bauers und Klaus Samelsons Arbeiten in den 1950er-Jahren zur Einführung der Begriffe Kellerprinzip und Kellerautomat [セラー原理とセラーオートマトンという用語の導入に関する 1950 年代のフリードリヒ L. バウアーとクラウス サメルソンの著作] (PDF) (ドイツ語) ）。ドイツ、イエナ: Institut für Informatik、Christian-Albrechts-Universität zu Kiel。 19～29ページ。2022-11-14 にオリジナルからアーカイブ(PDF)されました。2022 年 11 月 14 日に取得。(11 ページ) (注: Fothe & Wilke に掲載)
• グース、ゲルハルト[ドイツ語] (2017-08-07)。 Geschichte der deutschsprachigen Informatik - Programmierspra​​chen und Übersetzerbau [ドイツ語圏における情報学の歴史 - プログラミング言語とコンパイラー設計] (PDF) (ドイツ語)。カールスルーエ、ドイツ: Fakultät für Informatik、カールスルーエ工科大学(KIT)。2022-05-19 にオリジナルからアーカイブ(PDF)されました。2022 年 11 月 14 日に取得。（11ページ）

ウィキメディア・コモンズには、スタックデータ構造に関連するメディアがあります。

Wikibooks には、 「データ構造/スタックとキュー」に関する本があります。

• スタックマシン - 新しい波
• 境界スタックの深さ
• 割り込み駆動型プログラムのスタックサイズ分析