スタック
たいていの場合、プロシージャ内のローカルなデータとプロシージャ呼び出しに関する情報は共通のスタックに格納されている。つまりプログラムは、プロシージャ呼び出しのリターンアドレスという極めて重要な情報を保持しているスタックに対して、データを出したり入れたりしているのである。データをスタック上の間違った領域に書き込んだり、大きすぎるデータをスタックに書き込んだりして、リターンアドレスが壊されると、プログラムが異常動作することになる(バッファオーバーラン攻撃)。
悪意ある者がこの種の実装を逆手にとって、入力データのサイズをチェックしていないプログラムに大きすぎるデータを入力したりする。そのようなプログラムはデータをスタック上に格納しようとしてリターンアドレスを壊してしまう。攻撃者は実験を繰り返し、リターンアドレスがスタック領域内(特に攻撃者の入力データが書き込まれた領域内)を指すようになる入力データのパターンを見つけ出し、許可されていない操作をするような命令列を入力データに含ませることでセキュリティを破る。こうした攻撃に対してプログラマはスタックの扱いに注意する必要がある。
スタックポインタが指している現在位置にあるデータを取り出し、スタックポインタをそのデータのサイズのぶんだけ(Pushとは逆方向に)ずらす。
スタック操作の基本原則には様々なバリエーションがある。スタックは初期状態ではメモリ上の固定の位置に配置される。データがスタックに追加されると、スタックポインタはデータ追加に伴うスタックの領域拡張に従って変更される。そのときのスタックの延びていく方向は特に規則は無く、実装によってアドレスの小さくなる方向だったり、大きくなる方向だったりする。
昔のコンピュータで、ヒープ領域をアドレスの小さいほうから大きいほうへ伸ばし、スタックを大きいほうから小さいほうへ伸ばす(そのようにすると、メモリが足りない場合はどちらを伸ばす余裕もなく、完全にメモリを使い切って計算続行不可能となる)という設計にした名残りから、アドレスの大きいほうから小さいほうへ伸びるものが多いが、PA-RISCは逆である。
例えば、あるスタックが1000番地から開始して、アドレスの小さい方向に延びていくとする。
n 個の要素のスタックが必要とするメモリ容量はO (n )、つまりスタック長に比例する。個々の操作が一定時間O (1) で完了する実装は配列や連結リストを使っても簡単に実現できる。
実装の詳細については別に議論する。
この節では、抽象データ型としてのスタックのソフトウェアによる実装について述べる。
高水準言語では、スタックは配列や線形リストを使って効率的に実装可能である。LISPでは任意のリストに対して push や pop に相当する関数(consがpush、cdrがpopである)を使用可能なので、スタックを実装する必要は無い。
その場合、データは1000番地よりも小さい番地に格納され、スタックポインタはそれに伴って小さな番地を格納するようになる。そのスタックからデータをPopすると、スタックポインタに格納されているアドレスは大きくなる。
(初期状態の)スタックポインタはスタックの基点そのものではなく、その少し上か下(スタック成長方向に依存)の限界アドレスを指している場合もある。しかし、スタックポインタは基点を超えていくことはできない。換言すれば、スタックの基点が1000番地でスタックがアドレスの小さい方向(999番地、998番地など)に成長する場合、スタックポインタは決して1000番地を超えてはならない(1001番地や1002番地は不可)。Pop操作によってスタックポインタが基点を超えると「スタック・アンダーフロー」が発生する。逆にPush操作がスタックの最大許容範囲を超えてスタックポインタを操作することになるなら「スタック・オーバーフロー」が発生する。
スタックに強く依存している環境では、追加の操作を備えている場合がある。以下に例をあげる。