スタックのユースケース：元に戻す/やり直し、コールスタック、式の評価

スタックの実世界アプリケーション

スタックは教科書の概念だけではなく、日常のソフトウェアの重要な機能を支えています。ここでは最も重要な実世界のアプリケーションを紹介します。

1. 関数コールスタック

すべてのプログラミング言語はスタックを使用して関数呼び出しを管理します：

main()がfoo()を呼び出す
  foo()がbar()を呼び出す
    bar()が戻る -> foo()に戻る
  foo()が戻る -> main()に戻る

各関数呼び出しはローカル変数、戻りアドレス、パラメータを含むスタックフレームをpushします。関数が戻ると、そのフレームがpopされます。無限再帰がスタックオーバーフローを引き起こすのはこのためです — コールスタックのスペースが不足します。

2. 元に戻す/やり直しシステム

テキストエディタ、描画アプリ、フォームビルダーは2つのスタックを使用します：

• Undoスタック：各アクションがpushされる。Undoを押すと最後のアクションをpopしてRedoスタックにpush。
• Redoスタック：Redoを押すとここからpopしてUndoスタックに戻す。

3. ブラウザナビゲーション

Webブラウザの戻る/進むボタンはスタックのようなモデルを使用します。新しいページにアクセスすると現在のURLが戻るスタックにpushされます。戻るをクリックすると戻るスタックからpopして進むスタックにpushします。

4. 式の評価

コンパイラや電卓はスタックを使用して数式を評価します：

• 中置から後置への変換：演算子スタックを使用して優先順位に従ってトークンを並べ替え。
• 後置式の評価：オペランドをpushし、演算子が現れたら2つのオペランドをpopして演算を適用し、結果をpush。

5. 括弧の整合性チェック

最もクラシックなスタック問題の一つ：

入力: "({[]})"
- '('をpush  -> stack: ['(']
- '{'をpush  -> stack: ['(', '{']
- '['をpush  -> stack: ['(', '{', '[']
- ']'に対してpop、'['とマッチ -> stack: ['(', '{']
- '}'に対してpop、'{'とマッチ -> stack: ['(']
- ')'に対してpop、'('とマッチ -> stack: []
結果: 整合性あり！

6. 深さ優先探索（DFS）

グラフやツリーのDFSは明示的なスタック（または再帰によるコールスタック）を使用して次に訪問するノードを追跡します。LIFO特性により、アルゴリズムはバックトラックする前にできるだけ深く探索します。