スタックは、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し（LIFO: Last In First Out; FILO: First In Last Out）の構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。
wikipediaより引用
スタックはその名の通り積み重ねる様なデータ構造のことを言います。スタックではデータの操作を下図の様に行います。新たにデータが来た場合、一番上に重ね置きし、新たにデータを取り出す場合、一番上から取り出す、という動作です。それぞれプッシュ、ポップと呼ばれます。
スタックはデータを格納した一番上のデータの参照のみで多数のデータを少ない値で扱いきれます。一番上のデータから、そのデータサイズ分参照をずらすことによって、データがいくらプッシュポップされようとも常に一番上のデータを参照し続けられます。
スタックは最新の情報のみしか参照できない代わりに、簡単に小さなデータ領域で無数のデータを処理できるデータ構造です。この利点欠点は関数の呼び出し、抜け出しと相性が良いです。プログラミング言語は自然言語と異なり、関数が表られます。関数が現れたとき、その関数のある場所に飛び、関数の処理が終わった場合、関数が現れた場所に戻る必要があります。スタックはこれを簡単に行います。関数の呼び出し抜け出しにおいてスタックは、関数が現れた場合現れた場所をプッシュし関数へ移動、関数から抜け出す場合ポップして呼び出された場所を取り出しそこへ移動、という動作で処理を行います。 この関数の積み上げを自己のみで行う処理、自己参照を繰り返す処理が再帰処理と呼ばれます。
とにかく入れ子構造と相性が良いです。
文字列:(()(()))を読むとした時、(を読んだらプッシュ、)を読んだらポップとする。
1文字目:(
動作:プッシュ
動作後のスタック:(
2文字目:(
動作:プッシュ
動作後のスタック:((
3文字目:)
動作:ポップ
動作後のスタック:(
4文字目:(
動作:プッシュ
動作後のスタック:((
5文字目:(
動作:プッシュ
動作後のスタック:(((
6文字目:)
動作:ポップ
動作後のスタック:((
7文字目:)
動作:ポップ
動作後のスタック:(
8文字目:)
動作:ポップ
動作後のスタック:
上記の様に入れ子の始めを積み上げ、入れ子の終わりで始めを一つ消すといった具合です。スタックが空の時にポップが走れば不正な入れ子の終わりがある、スタックが空で終了しないならば入れ子の始めが多すぎる、といったことが分かります。
