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

積み重ねた皿と同様に、追加や削除は上部でのみ実行可能です。
プッシュおよびポップ操作を含むスタック ランタイムの単純な表現。

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

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

さらに、peek操作はスタックを変更することなく、最後に追加された要素（スタックの一番上の要素）の値を返すことができます。スタックという名前は、皿の山のように、物理的なアイテムが積み重ねられている様子に 似ています。

スタックに要素を追加または削除する順序は、後入れ先出し（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 ]清潔な皿が積み重ねられた皿の上に置かれ、既に積み重ねられている皿が押し下げられる。積み重ねられた皿の一番上の皿が取り除かれると、その下の皿が持ち上げられ、新しい一番上の皿となる。

必須ではない業務

多くの実装において、スタックには必須の「プッシュ」操作と「ポップ」操作以外にも多くの操作があります。必須ではない操作の例としては、「スタックのトップ」、または「ピーク」操作があります。これは、スタックからトップ要素を削除せずに、その要素を参照する操作です。[ 18 ]これは、「ポップ」操作と「プッシュ」操作の2つに分解でき、同じデータをスタックに戻す操作であるため、必須操作とはみなされません。スタックが空の場合、「スタックトップ」操作または「ポップ」操作のいずれかを実行すると、アンダーフロー状態が発生します。さらに、多くの実装では、スタックが空かどうかの確認やスタックのサイズの取得など、一般的なタスクを処理するための便利な操作も含まれています。

ソフトウェアスタック

実装

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

配列

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

構造スタック: 最大サイズ: 整数 上: 整数 items : アイテムの配列 
手順initialize(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 
構造スタック: head : フレームまたはnil サイズ: 整数 
手順initialize(stk:stack): stk.head ← なし stk.size ← 0

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

手順push(stk:スタック、x:アイテム): ニューヘッド ← 新しいフレーム 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()および操作があります。さらに、テンプレートクラスは既存のコンテナを適応させ、push/pop操作のみを含む制限付きAPIを提供します。PHPにはクラスがあります。Javaライブラリにはを特殊化した クラスが含まれています。以下は、そのクラスを使用した Java言語のサンプルプログラムです。pop_back()std::stackSplStackStackVector

パッケージorg.wikipedia.examples ;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 以上に) 増加してはなりません。スタックのポップ操作によってスタック ポインターがスタックの起点を超えて移動すると、スタック アンダーフローが発生します。プッシュ操作によってスタック ポインターがスタックの最大範囲を超えて増加または減少すると、スタック オーバーフローが発生します。

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

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

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

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

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

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

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

スタックのポップは、単にプッシュの逆の操作です。スタックの最上位の要素が削除され、スタックポインタが更新されます。これはプッシュ操作とは逆の順序です。

メインメモリ内のスタック

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

レジスタまたは専用メモリ内のスタック

1988 年のプログラム可能なポケット計算機 HP -42S は、当時の同社のほぼすべての計算機と同様に 4 レベル スタックを備えており、2 行のディスプレイ (この場合は X と Y) により、スタック レジスタ X、Y、Z、T の 4 つの値のうち 2 つを同時に表示できました。HP -48などの後期モデルでは、レベル数はメモリ サイズによってのみ制限されるように増加されました。

一部のマシンでは、算術演算や論理演算にスタックを使用します。オペランドはスタックにプッシュされ、算術演算や論理演算はスタックの先頭にある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言語は通常、このように実装されています。データ呼び出しとプロシージャ呼び出しの両方に同じスタックを使用することは、セキュリティ上の重要な影響を及ぼします（下記参照）。プログラマは、プログラムに深刻なセキュリティバグが入り込むのを防ぐために、この影響を認識しておく必要があります。

効率的なアルゴリズム

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

安全

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

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

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

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

参照

注記

  1. ^対照的に、キューは先入れ先出し方式で動作し、頭字語でFIFOと呼ばれます。

参考文献

  1. ^ a bコーメン, トーマス・H. ;レイソン, チャールズ・E. ;リベスト, ロナルド・L. ;スタイン, クリフォード(2009) [1990].アルゴリズム入門（第3版）. MITプレスおよびマグロウヒル. pp.  232– 233. ISBN 0-262-03384-4。
  2. ^チューリング、アラン・マティソン(1946-03-19) [1945].自動計算エンジン (ACE) の数学部門の開発提案.(注: 1946 年 3 月 19 日に英国国立物理学研究所の執行委員会に提出されました。)
  3. ^カーペンター、ブライアン・エドワード、ドラン、ロバート・ウィリアム(1977年1月1日) [1975年10月]. 「もう一つのチューリングマシン」 .コンピュータジャーナル. 20 (3): 269– 279. doi : 10.1093/comjnl/20.3.269 .（11ページ）
  4. ^ Blaauw, Gerrit Anne ; Brooks, Jr., Frederick Phillips (1997). 『コンピュータアーキテクチャ：概念と進化』 ボストン、マサチューセッツ州、米国: Addison-Wesley Longman Publishing Co., Inc.
  5. ^ LaForest, Charles Eric (2007年4月). 「2.1 ルカシェヴィチと第一世代：2.1.2 ドイツ：コンラート・ツーゼ（1910–1995）；2.2 第一世代のスタックコンピュータ：2.2.1 ツーゼZ4」.第二世代スタックコンピュータアーキテクチャ(PDF) (論文). ウォータールー大学（カナダ）. pp. 8, 11. 2022年1月20日時点のオリジナルよりアーカイブ(PDF) . 2022年7月2日閲覧。（178ページ）
  6. ^クラウス・サメルソン(1957) [1955].ドイツ、ドレスデンの国際コロキウム・ユーバー・プロブレム・デア・レヒェンテクニクで執筆。問題 der Programmierungstechnik (ドイツ語)。ベルリン、ドイツ: VEB Deutscher Verlag der Wissenschaften。61～ 68ページ 。(注: この論文は 1955 年に初めて発表されました。数値スタック ( Zahlenkeller ) について説明していますが、線形補助メモリ ( linearer Hilfsspeicher ) という名前が付けられています。)
  7. ^ a b c dフォーテ、マイケル;トーマス・ウィルク編。 (2015) [2014-11-14]。ドイツのイエナで書かれました。Keller、Stack und automatisches Gedächtnis – eine Struktur mit Potenzial [セラー、スタック、および自動メモリ - 可能性のある構造] (PDF) (Tagungsband zum Kolloquium 14. 2014 年 11 月、イエナ)。 GI シリーズ: 情報学講義ノート (LNI) – テーマ (ドイツ語)。 Vol. T-7。ボン、ドイツ: Gesellschaft für Informatik (GI) / Köllen Druck + Verlag GmbH。ISBN 978-3-88579-426-4. ISSN  1614-3213 . 2020年4月12日時点のオリジナルよりアーカイブ（PDF） . 2020年4月12日閲覧.[1]（77ページ）
  8. ^バウアー、フリードリヒ・ルートヴィヒ;クラウス・サメルソン(1957-03-30)。「Verfahren zur automatischen Verarbeitung von kodierten Daten und Rechenmaschine zur Ausübung des Verfahrens」（ドイツ語）。ミュンヘン、ドイツ: ドイツ特許。 DE-PS 1094019 。2010 年 10 月 1 日に取得。
  9. ^バウアー、フリードリヒ・ルートヴィヒ;グース、ゲルハルト[ドイツ語] (1982)。Informatik – Eine einführende Übersicht (ドイツ語)。 Vol.パート 1 (3 版)。ベルリン: Springer-Verlag。 p. 222.ISBN​ 3-540-11722-9。Die Bezeichnung 'Keller' hierfür wurde von Bauer und Samelson in einer deutschen Patentanmeldung vom 30. März 1957 eingefüult.
  10. ^クラウス・サメルソン;バウアー、フリードリヒ・ルートヴィヒ(1959)。 「Sequentielle Formelübersetzung」[逐次式翻訳]。Elektronische Rechenanlagen (ドイツ語)。1 (4): 176 – 182.
  11. ^サメルソン, クラウス;バウアー, フリードリヒ・ルートヴィヒ(1960). 「逐次式変換」 . Communications of the ACM . 3 (2): 76– 83. doi : 10.1145/366959.366968 . S2CID 16646147 . 
  12. ^ "IEEE-Computer-Pioneer-Preis – Bauer, Friedrich L.."ミュンヘン工科大学、コンピュータサイエンス学部。1989年1月1日。 2017年11月7日時点のオリジナルよりアーカイブ。
  13. ^ Hamblin, Charles Leonard (1957年5月). An Addressless Coding Scheme based on Mathematical Notation (PDF) (typescript). NSW University of Technology . pp.  121-1 – 121-12 . 2020年4月12日時点のオリジナルよりアーカイブ(PDF) . 2020年4月12日閲覧。（12ページ）
  14. ^ヴィルヘルム、ケンメラー[ドイツ語] (1958-12-11). Ziffern-Rechenautomat mit Programmierung nach mathematischem Formelbild (ハビリテーション論文) (ドイツ語)。イエナ、ドイツ: Mathematisch-naturwissenschaftliche Fakultät、Friedrich-Schiller-Universität。urn:nbn:de:gbv:27-20130731-133019-7。 PPN:756275237。2023年10月14日のオリジナルからアーカイブ。2023 年 10 月 14 日に取得。[2] (2+69ページ)
  15. ^ヴィルヘルム、ケンメラー[ドイツ語] (1960).ツィフェルンレーヘンオートマテン。 Elektronisches Rechnen und Regeln (ドイツ語)。 Vol. 1. ドイツ、ベルリン: Akademie-Verlag。
  16. ^ Ball, John A. (1978). RPN計算機のためのアルゴリズム（第1版）. ケンブリッジ, マサチューセッツ州, 米国: Wiley-Interscience , John Wiley & Sons, Inc. ISBN 978-0-471-03070-6。LCCN  77-14977。
  17. ^ Godse, Atul P.; Godse, Deepali A. (2010-01-01).コンピュータアーキテクチャ. 技術出版物. pp.  1– 56. ISBN 978-8-18431534-9. 2015年1月30日閲覧。
  18. ^ Horowitz, Ellis (1984). Pascalにおけるデータ構造の基礎.コンピュータサイエンスプレス. p. 67.
  19. ^ Pandey, Shreesham (2020). 「データ構造の要点」 . Dev Genius . 2020. SSRN 4145204 . 
  20. ^ Graham, Ronald "Ron" Lewis (1972).有限平面集合の凸包を決定するための効率的なアルゴリズム(PDF) . Information Processing Letters 1. Vol. 1. pp.  132– 133. 2022年10月22日時点のオリジナルよりアーカイブ(PDF) 。
  21. ^ Aggarwal, Alok; Klawe, Maria M. ; Moran, Shlomo ; Shor, Peter ; Wilber, Robert (1987) . 「行列探索アルゴリズムの幾何学的応用」. Algorithmica . 2 ( 1–4 ): 195– 208. doi : 10.1007/BF01840359 . MR 0895444. S2CID 7932878 .  。
  22. ^ Berkman, Omer; Schieber, Baruch ; Vishkin, Uzi (1993). 「最も近い小さな値をすべて見つけることに基づく最適な二重対数並列アルゴリズム」. Journal of Algorithms . 14 (3): 344– 370. CiteSeerX 10.1.1.55.5669 . doi : 10.1006/jagm.1993.1018 . 。
  23. ^ Murtagh, Fionn (1983). 「階層的クラスタリングアルゴリズムの最近の進歩に関する概説」(PDF) . The Computer Journal . 26 (4): 354– 359. doi : 10.1093/comjnl/26.4.354 .。

さらに読む

ウィキメディア コモンズには、スタック データ構造に関連するメディアがあります。
Wikibooksには、 「データ構造/スタックとキュー」に関する書籍があります。
「 https://en.wikipedia.org/w/index.php?title=Stack_(abstract_data_type)&oldid=1322896999#push」から取得