スタックのLIFO原則を解説

LIFO原則

スタックは**後入れ先出し（LIFO: Last In, First Out）**原則に従う抽象データ型です。最後に追加された要素が最初に取り出されます。皿を積み重ねたスタックのように、常に一番上から取り出します。

コア操作

操作	説明	時間計算量
push(x)	要素xをトップに追加	O(1)
pop()	トップの要素を削除して返す	O(1)
peek()	トップの要素を削除せずに確認	O(1)
isEmpty()	スタックが空か確認	O(1)

LIFOの動作

要素1, 2, 3をスタックにpushする場合：

push(1): [1]         <- 1がトップ
push(2): [1, 2]      <- 2がトップ
push(3): [1, 2, 3]   <- 3がトップ
pop():   [1, 2]      <- 3が削除（後入れ先出し）
pop():   [1]         <- 2が削除

重要なポイントは、要素に順番外でアクセスすることはできないということです。2にアクセスするには先に3をpopし、1にアクセスするには先に2をpopする必要があります。この制約こそが、ネストされたコンテキストや再帰的なコンテキストの追跡にスタックを有用にしています。

配列 vs 連結リスト実装

スタックは配列または連結リストのどちらでも実装できます：

• 配列ベース：変数topでトップ要素のインデックスを追跡。pushはtopをインクリメントして代入、popは読み取ってデクリメント。配列のリサイズが稀なため償却O(1)。
• 連結リストベース：各ノードが下のノードを指す。pushは新しいヘッドを前に追加、popはヘッドを削除。リサイズ不要で常にO(1)だが、各ノードにポインタのオーバーヘッドあり。

オーバーフローとアンダーフロー

• スタックオーバーフロー：固定サイズのスタックがいっぱいの状態でpush。コールスタックのようなバウンドスタックの言語ではクラッシュの原因となる。
• スタックアンダーフロー：空のスタックからpop。実装はエラーをスローするかセンチネル値を返すべき。