スタック

スタックとは

スタック（stack）は、コンピュータサイエンスにおける基本的なデータ構造の一つで、データを後入れ先出し（LIFO: Last In First Out）の順序で保持するものです。これは、最後に入力されたデータが最初に取り出されるという性質を持ちます。スタックは抽象データ型としても、具体的な実装としても用いられます。

抽象データ型としてのスタック

抽象データ型としてのスタックは、ノード（データと他のノードへの参照を持つ構造）のコンテナであり、主にプッシュ（push）とポップ（pop）という二つの操作を持ちます。プッシュは新しいノードをスタックの先頭（トップ）に追加し、ポップはスタックのトップにあるノードを取り出して返します。

スタックの動作は、食堂で皿を積み重ねる様子に例えられます。一番上の皿だけが利用可能で、新しい皿を積むとそれがトップになり、下の皿は隠れます。皿を取ると、次の皿がトップになります。この比喩から、LIFOの原則と、スタックの中身が隠蔽されているという点が理解できます。

その他の操作

多くのスタック実装では、プッシュとポップに加えて、スタックのサイズ取得、トップのノードを返す（ただし取り出さない）ピーク（peek）操作、特定の要素へのアクセス、要素の入れ替えなどの操作が提供されます。これらの操作の計算量は、実装によって異なり、配列ベースではO(1)で、連結リストではO(n)となる場合があります。

実装

スタックの実装には、配列や連結リストがよく使われます。n個の要素を持つスタックに必要なメモリ容量はO(n)であり、個々の操作は通常O(1)で完了します。具体的な実装の詳細は、別の議論が必要です。

ハードウェアにおけるスタック

ハードウェアレベルでは、スタックはシフトレジスタによる直接的な実装と、メモリ上の領域とスタックポインタによる間接的な実装があります。多くのコンピュータでは、スタックポインタを使ってメモリ上にコールスタックを保持しています。

典型的なスタック

典型的なスタックは、メモリ上の固定された基点と可変サイズの領域で構成されます。スタックポインタは、最後に参照された位置を指し示します。スタックが空の場合、スタックポインタは基点を指します。

プッシュ操作では、スタックポインタをデータのサイズ分だけ移動させて、新しいデータを格納します。ポップ操作では、スタックポインタが指すデータを取り出し、スタックポインタを逆方向に移動させます。

スタックの成長方向は実装によって異なり、アドレスが小さくなる方向にも大きくなる方向にも伸びることがあります。スタックポインタが基点を超えてしまうと、スタックアンダーフローが発生し、スタックの最大許容範囲を超えるとスタックオーバーフローが発生します。

追加の操作

スタックには、以下のような追加の操作が実装されることがあります。

Dup (Duplicate): トップのアイテムを複製してスタックにプッシュします。
Peek: トップのアイテムを返しますが、スタックからは削除しません。
Swap (Exchange): スタックのトップ2つのアイテムを入れ替えます。
Rotate: トップのn個のアイテムを回転させます。

スタックは、メモリセルで構成され、スタックポインタがトップのアドレスを格納します。プッシュ操作では、スタックポインタが移動し、新しいアイテムがスタックにコピーされます。ポップ操作では、トップのアイテムが取り出され、スタックポインタが更新されます。

コールスタック

スタックは、特にコールスタックとして利用されます。コールスタックは、関数呼び出し時の情報（引数、戻りアドレスなど）を格納するために使われ、関数呼び出しの入れ子や再帰呼び出しを実現します。スタックフレームと呼ばれる領域が関数呼び出しごとに作成され、スタックトレースによって呼び出し履歴を追跡できます。

具体例

多くのプロセッサは、スタックポインタとして使用できる専用のレジスタを持っています。x86プロセッサなどがその例です。一部のマイクロコントローラには、固定サイズのスタックが内蔵されている場合があります。また、ハードウェアで直接スタックを実装したコンピュータも存在します。

ソフトウェアにおけるスタック

高水準言語では、スタックは配列や線形リストを使って効率的に実装できます。LISPなどの言語では、リスト操作がスタック操作に対応するため、スタックを明示的に実装する必要はありません。

応用例

式評価と構文解析

逆ポーランド記法を使用する電卓では、スタックを使って値を保持します。式を前置、中置、後置記法の間で変換する際にもスタックが利用されます。多くのコンパイラは、構文解析にスタックを使用します。

例えば、((1 + 2) 4) + 3 という式は、後置記法で 1 2 + 4 3 + と表され、スタックを用いて評価できます。オペランドをスタックにプッシュし、演算子に遭遇したらスタックからオペランドをポップして演算を行い、結果をスタックにプッシュするという手順を繰り返します。

探索問題の解法

探索問題を解く際、スタックは探索ノードを覚えておくために用いられます。力まかせ探索、バックトラッキング、分枝限定法などでスタックが使用されます。再帰処理も内部的にはスタックを使用します。スタックを使った探索は、幅優先探索や深さ優先探索、パズルやゲームの自動解法などで広く利用されています。

プログラミング言語処理系の実装

コンパイルされたプログラムは、実行時にコールスタックを使用して、プロシージャ呼び出しに関する情報を格納します。関数呼び出し時のコンテキスト切り替えや呼び出し元への復帰に利用され、再帰呼び出しを可能にします。プロシージャ内のローカルデータをスタックに格納する言語もあります。

セキュリティ

プロシージャ内のローカルデータとプロシージャ呼び出し情報は、共通のスタックに格納されるため、バッファオーバーランなどの脆弱性が生じる可能性があります。リターンアドレスが壊されると、プログラムが異常動作を引き起こす可能性があります。悪意ある攻撃者は、このような脆弱性を利用して、許可されていない操作を実行させる可能性があります。

スタック指向プログラミング言語

スタック指向プログラミング言語では、基本操作はスタックから引数を取り、結果をスタックに返します。ForthやPostScriptなどが例として挙げられます。

スタックマシン

機械語命令がスタック指向プログラミング言語に類似しているマシンをスタックマシンといいます。バロース B5000などがその例です。多くの仮想機械もスタックマシンです。これに対し、オペランドがレジスタのマシンをレジスタマシンといいます。

歴史

スタックを使った式評価方法は、ドイツのコンピュータ科学者フリードリッヒ・L・バウアーによって最初に提案されました。