スタック
スタックは後入れ先出し（LIFO）です。push は頂上に要素を置き、pop は最後に置いた要素を取り出します。同じ端だけを操作し、中間の移動や走査はしません。この Python リスト実装では、両操作の償却時間は O(1) です。
重ねた皿の上に置き、上から取ると考えてください。この制約は、関数呼び出し、取り消し履歴、括弧の対応、深さ優先探索など、逆順に戻る処理に適しています。
スタックの仕組み
コードは Python リスト data と容量 max で有界スタックを作ります。push(val) は最初に len(self.data) >= self.max を検査します。満杯なら Stack Overflow を送出し、そうでなければ末尾に val を追加します。pop() は空なら Stack Underflow を送出し、空でなければ末尾を削除して返します。
頂上はリストの最後のインデックスです。append と list.pop() はこの端で動き、その下の要素を走査しません。
容量制限はこの実装の規則で、LIFO 自体の条件ではありません。組み込みでは有界スタックを使いますが、通常の Python リストは利用可能なメモリに応じて成長します。スライダーの 3–10 は画面の表示制限です。
操作をステップで追う
既定は空のスタック、容量 8 です。追加と取り出しのボタンで実行します。
push(3)：0 < 8で検査を通過し、[3]。頂上のインデックスは 0。push(7)：[3, 7]。古い頂上の上に新しい要素を置く。push(1)：[3, 7, 1]。pop()：最後に入れた1を返し、[3, 7]が残る。pop()：7を返し、[3]が残る。push(9)：[3, 9]。以前7が占めた位置を再利用する。pop()を二回：9、3の順に返し、空になる。さらに一回でアンダーフロー。
容量 8 に九個目を入れる例も試してください。追加前にオーバーフローとなり、失敗した操作は状態を変えません。
画面では上だけが開いた容器を使い、要素は上から入り、上へ出ます。ヘッダーの size と頂上の値が更新され、空なら頂上の値を隠します。古い値を表示し続けないためです。上の手順が状態の全記録です。
時間・空間計算量
| 操作 | 時間 | 空間 |
|---|---|---|
push | 償却 O(1) | 要素ごとに O(1) |
pop | 償却 O(1) | — |
peek | O(1) | — |
| 全体の保存領域 | — | O(n) |
頂上だけにアクセスするインターフェースと、リスト末尾の実装がこの費用を支えます。規則と保存方法を合わせて評価してください。
境界ケース
- 満杯への追加：オーバーフロー。状態は変わらない。
- 空からの取り出し：アンダーフロー。空を調べるか例外を処理する。
- 一要素：追加して取り出すと同じ値が戻り、サイズは 0 → 1 → 0。
- 重複値：使用できる。集合ではなく順序を保存する構造。
よくある間違い
popとpeekの混同。popは削除します。見るだけなら空を確認してdata[-1]を読みます。- 端を混ぜる。 後ろから入れ、前から出すとキューになります。
- 空の検査を省く。 Python の空リストの
pop()は例外、JavaScript 配列はundefinedを返します。API に応じて処理してください。 - 中間への添字アクセスを公開する。
data[k]を自由に読むなら LIFO に制限したインターフェースではありません。リストや deque を検討します。 - コールスタックを見落とす。 関数呼び出しでフレームを積み、復帰で取り出します。再帰のスタックオーバーフローは、実行時のコールスタックの枯渇です。