この記事は検証可能な参考文献や出典が全く示されていないか、不十分です。出典を追加して記事の信頼性向上にご協力ください。（このテンプレートの使い方）
出典検索?: "スタック" ? ニュース ・ 書籍 ・ スカラー ・ CiNii ・ J-STAGE ・ NDL ・ dlib.jp ・ ジャパンサーチ ・ TWL（2015年10月）
.mw-parser-output .hatnote{margin:0.5em 0;padding:3px 2em;background-color:transparent;border-bottom:1px solid #a2a9b1;font-size:90%}

「スタック」のその他の用法については「スタック (曖昧さ回避)」をご覧ください。
push（プッシュ） およびpop（ポップ） のスタックの単純な表現スタックの単純な表現

スタック（英: stack）は、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し（LIFO: Last In First Out; FILO: First In Last Out）の構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。

特にその具象としては、割込みやサブルーチンを支援するために極めて有用であることから、1970年代以降に新しく設計された、ある規模以上のコンピュータは、スタックポインタによるコールスタックをメモリ上に持っていることが多い。
抽象データ型[ソースを編集]

抽象データ型としてのスタックは、ノード（何らかのデータを持ち、別のノードを指し示すことができる構造）のコンテナ（データを集めて格納する抽象データ型の総称）であり、2つの基本操作プッシュ (push) とポップ (pop) を持つ。Pushは指定されたノードをスタックの先頭（トップ）に追加し、既存のノードはその下にそのまま置いておく。Popはスタックの現在のトップのノードを外してそれを返す。

よく使われる比喩として、食堂にあるバネが仕込まれた台に皿や盆を積み重ねておく様子がある。そのようなスタックでは利用者は一番上（トップ）の皿だけにアクセスすることができ、それ以外の皿は隠されている。新たに皿が追加される（Pushされる）と、その新しい皿がスタックのトップとなり、下にある皿を隠してしまう。皿をスタックから取る（Popする）と、それを使うことができ、二番目の皿がスタックのトップとなる。二つの重要な原則がこの比喩で示されている。第一は後入れ先出し (LIFO: Last In First Out) の原則である。第二はスタックの中身が隠されているという点である。トップの皿だけが見えているため、三番目の皿がどういうものかを見るには一番目と二番目の皿を取り除かなければならない。
他の操作[ソースを編集]

多くのスタック実装では「Push」と「Pop」以外の操作をサポートしている。スタックの大きさ（長さ）、「現在のスタックのトップのノードを返すが、それをスタックから取り除かない」Peek操作、トップではなくn番目の参照・操作、入れ替え等も実装されることもある。連結リストではO(n)だが配列による実装ではO(1)、その逆、等色々な場合がある。
実装[ソースを編集]

n 個の要素のスタックが必要とするメモリ容量はO (n )、つまりスタック長に比例する。個々の操作が一定時間O (1) で完了する実装は配列や連結リストを使っても簡単に実現できる。

実装の詳細については別に議論する。
関連するデータ構造[ソースを編集]

FIFO (First In First Out、先入れ先出し) の原則を持つデータ構造または抽象データ型はキューである。スタックとキューの操作を組み合わせて提供するものは両端キュー (deque) と呼ぶ。例えば、探索アルゴリズムでスタックを使うかキューを使うかによって、深さ優先探索（スタック使用）か幅優先探索（キュー使用）になる。