定義
スタック(Stack)は後入れ先出し(LIFO、Last In First Out)方式のデータ構造です。お皿を積み重ねたように、最後に入れたデータを最初に取り出します。
主な特性
- ✓LIFO（後入れ先出し）- 最後に入れたものを最初に取り出す
- ✓pushとpop操作がO(1)時間計算量
- ✓topで最上位要素を確認
- ✓再帰呼び出し、元に戻す（Undo）などでよく活用
活用事例
こんな場面で使われます:
◀️
ブラウザの戻るボタン
ウェブブラウザで訪問したページをスタックに保存し、戻るボタンを押すと最新のページから取り出します。
↩️
元に戻す (Ctrl+Z)
ドキュメントエディタで作業履歴をスタックに保存し、取り消すたびに最新の作業から元に戻します。
()
括弧チェック
コードの括弧が正しく閉じられているかをチェックする際、開き括弧をスタックに入れ、閉じ括弧が出たら取り出して比較します。
🔄
再帰→反復変換
再帰関数を反復文に変換する際、関数呼び出し状態をスタックに保存して再帰と同じ動作を実装します。
主な操作
主な操作:
push
O(1)スタックの最上位に要素を追加します。
pop
O(1)スタックの最上位要素を削除して返します。
peek / top
O(1)スタックの最上位要素を削除せずに確認します。
isEmpty
O(1)スタックが空かどうかを確認します。
計算量
時間計算量
最良
O(1)
平均
O(1)
最悪
O(1)
空間計算量
O(n)
可視化でより深く理解する
ステップごとのアニメーションとコード実行を通じて、アルゴリズムの動作を直接確認してください。
可視化を開始