スタック
探索問題を解くとき、総当り的か最適化されているかに関わらず、スタックを多大に必要とすることが多い。総当り探索の例としては、力まかせ探索やバックトラッキングがある。最適探索の例としては、分枝限定法 (branch and bound) やヒューリスティックによる解法がある。いずれのアルゴリズムでも、発見してはいるが探索していない探索ノードを覚えておくのにスタックが必要となる。スタックを使う以外の手法としては再帰を使う方法があるが、これはコンパイラが生成するコードが内部的に使用するスタックで代替しているだけである。スタックを使った探索は幅広く使われており、木構造の単純な幅優先探索や深さ優先探索から、クロスワードパズルを自動的に解くプログラムやコンピュータチェスゲームでも使われている。ある種の問題はキューなどの別のデータ構造を使って解くこともでき、探索順を変えたいときに有効である。
機械語命令の体系がスタック指向プログラミング言語に類似している、すなわち、命令のオペランドがスタックであるマシンをスタックマシンと言う。最も有名なものとしてバロース B5000がある(B5000は、高水準言語(ALGOL)のサポートを目的として、前述のコールスタックもアーキテクチャでサポートしているが、コールスタックをアーキテクチャでサポートしている、という意味では「スタックマシン」の語は使わない)。
またx86等でも、スタックポインタ間接参照によってスタックマシンのように使うことはできるが、普通あまりスタックマシンとはしない。
多くの仮想機械もスタックマシンであり、例えばp-コードマシンやJava仮想マシンなどがある。x87の命令もスタックマシン的である。
これに対し、オペランドがレジスタのマシンをレジスタマシンと言う。多くの実機がレジスタマシンであるため実機に対してこの語が使われることは少ない。仮想機械ではLua 5の仮想機械がレジスタマシンである。