スタック (Stack)

**スタック (Stack)**は、最後に追加した要素を最初に取り出すLIFOデータ構造である。

仕組み

pushは頂上へ追加し、popは頂上を削除して返す。途中の要素を直接取り出さないことが不変条件になる。

計算量・性質

配列・連結リストの適切な実装ではpush、pop、peekはO(1)。動的配列のpushは償却O(1)。

具体例

1,2,3を順にpushするとpopの順は3,2,1になる。

限界と注意点

空スタックからのpopによるアンダーフローと、固定容量でのオーバーフローを処理する。