スタック
「底」とか「トップ」という用語はスタックがアドレスの大きくなる方向に成長するか、小さくなる方向に成長するかに関係なく使われる。
スタックへのアイテムの push により、そのアイテムのサイズのぶんだけスタックポインタがずらされ(増減はメモリ空間内のスタックの成長方向に依存する)、次のセルを指すようにして、新たなトップとなるアイテムをスタック領域にコピーする。詳細な実装に依存するが、push 操作を完了したときのスタックポインタの値はスタック上の次の未使用領域を指しているかもしれないし、現在のトップのアイテムを指しているかもしれない。スタックポインタが現在のトップのアイテムを指している場合、次回の push のときには最初にスタックポインタをずらさなければならない。逆にスタックポインタが次の未使用領域を指しているなら、次回の push のときには最後にスタックポインタをずらすことになる。
スタックの pop 操作は push の逆となる。Push とは逆の順番でスタックのトップのアイテムが取り出され、スタックポインタが更新される。
以上のようなスタックは、特にコールスタックに使われる。
多くのプロセッサはスタックポインタとして使用可能なレジスタを持っている。x86のようなプロセッサは専用のスタックポインタレジスタを持っている。他のPDP-11や68000ファミリなどは、アドレッシングモードによって任意のレジスタをソフトウェア的にスタックポインタとして使用できるようになっているが、普通は割込みやJSR命令が操作するR6レジスタやA7レジスタを使う。RISCの多くはそのように特別扱いされるようなレジスタを持たず、どのレジスタをスタックポインタとして使うかは通常ABIで決めており、ソフトウェアでスタック処理をおこなう。Intel 8087シリーズの数値演算コプロセッサはスタックアーキテクチャである。一部のマイクロコントローラ(例えばいくつかのPIC)は固定サイズのスタックを内蔵しており、その任意の位置に直接アクセスすることはできない。
以上のようなスタックポインタによるスタックではなく、直接ハードウェアで実現したスタックを持つコンピュータもある。
Computer Cowboys MuP21
Harris RTX line
Novix NC4016
なお、以上のようなスタックがあるコンピュータをスタックマシンとするのは間違いである。詳細は後述のスタックマシンについての記述を参照すること。
典型的なスタックはコンピュータのメモリ上に固定の基点と可変のサイズを持つ領域である。初期状態ではスタックのサイズはゼロである。「スタックポインタ」(一般にハードウェアのレジスタが使われる)はスタック内で最も後で参照された位置を指している。スタック長がゼロのとき、スタックポインタはスタックの基点を指す。
あらゆるスタックで実施可能な2つの操作は以下の通りである。