Stack - tanakakenji/Rinko GitHub Wiki

イントロダクション (Introduction)
スタック（Stack）は抽象データ型の一種で、次の2つの操作をサポートします:

  • push: 新しい要素をスタックの頂上（トップ）に挿入する
  • pop: スタックの頂上にある、最後に追加された要素を削除して返す

抽象データ型としてのスタックは、配列や単方向リスト（単方向リンクドリスト）を用いて実装できます。

このような挙動は一般的に LIFO (Last In, First Out) と呼ばれます。名前の由来は、物理的に積み重なった複数の物体を想像すると分かりやすいでしょう。

スタックは、再帰呼び出しの管理や、深さ優先探索（Depth-first search: DFS）の実装に頻繁に使われる重要なデータ構造です。深さ優先探索は、再帰を使う方法か、スタックを手動で用いる方法のいずれかで実現できます。

学習リソース (Learning resources)

読み物

動画

実装 (Implementations)

言語 API
C++ std::stack
Java java.util.Stack
Python リスト(List)でシミュレート
JavaScript 配列(Array)でシミュレート

時間計算量 (Time complexity)

操作 Big-O
Top / Peek O(1)
Push O(1)
Pop O(1)
isEmpty O(1)
Search O(n)

コーナーケース (Corner cases)

  1. 空のスタック: スタックが空の時に pop するとエラー
  2. 要素が1つだけのスタック
  3. 要素が2つだけのスタック

重要問題 (Essential questions)

スタックに関する問題を学習する際、まず取り組むべき代表的な問題は以下です。

  • Valid Parentheses
  • Implement Queue using Stacks

おすすめの練習問題 (Recommended practice questions)

上記の重要問題をマスターした後に、さらに挑戦したい場合には以下がおすすめです。

  • Implement Stack using Queues
  • Min Stack
  • Asteroid Collision
  • Evaluate Reverse Polish Notation
  • Basic Calculator
  • Basic Calculator II
  • Daily Temperatures
  • Trapping Rain Water
  • Largest Rectangle in Histogram

スタックは、CPUとOSの内部で重要な役割を果たすメモリ領域です。スタックは、関数やメソッドが使用するローカル変数や引数、戻りアドレスといった一時的なデータを格納するために使用されます[5][7][13].

CPUにおけるスタック

  • データの格納 CPUはスタックを操作するための特別なレジスタと命令を備えており、リターンアドレス、ベースポインタ、引数、ローカル変数などをスタックに格納します[7].
  • 関数呼び出しの管理 関数が呼び出されると、CPUは呼び出し元のリターンアドレスをスタックに保存します[2]. これにより、関数が終了した後にプログラムがどこに戻るべきかを把握できます.
  • スタックポインタ スタックポインタは、スタック領域内の現在位置を示すレジスタです[2][8]. CPUはスタックポインタを使用して、スタックへのデータの追加（push）やスタックからのデータの取り出し（pop）を行います[8][19].

OSにおけるスタック

  • スレッド管理 OSは、プログラムがスレッドを生成する際に、そのスレッド専用のスタック領域を割り当てます[5]. このスタックは、スレッド上で実行されるメソッドや関数が使用するローカル変数などを格納するために使用されます[5].
  • メモリ管理 OSは、スタック領域を自動的に管理し、メモリの確保と解放を行います[11].
  • 割り込み処理 プログラム実行中に割り込みが発生すると、OSは現在のプログラムの状態をスタックに退避させ、割り込み処理ルーチンを実行します[1]. 割り込み処理が完了すると、OSはスタックから元のプログラムの状態を復元し、処理を再開します.
  • タスク管理 RTOS（リアルタイムOS）では、各タスクに専用のスタック領域が割り当てられます[6]. タスクの切り替え時には、CPUのレジスタの内容がスタックに保存され、切り替え先のタスクのスタックからレジスタの内容が復元されます。

スタックオーバーフロー スタック領域には限りがあるため、過剰な関数呼び出しや大きなローカル変数の使用などにより、スタック領域が不足することがあります。これをスタックオーバーフローと呼び、プログラムのクラッシュや予期しない動作を引き起こす可能性があります[5][6][10].

ヒープとの比較 スタック領域とは別に、ヒープ領域と呼ばれるメモリ領域も存在します。スタックはコンパイラやOSによって管理されるのに対し、ヒープはアプリケーションが動的にメモリを確保・解放するために使用されます[4][11]. スタックはLIFO（後入れ先出し）方式で管理されますが、ヒープはより柔軟なメモリ管理が可能です[11][14].

Citations: [1] https://monoist.itmedia.co.jp/mn/articles/0612/19/news098_2.html [2] https://www.iar.com/ja/knowledge/learn/programming/rtos-stack-overflows-part-1 [3] http://www3.nit.ac.jp/~tamura/algorithm/lesson11.html [4] https://uquest.tktk.co.jp/embedded/learning/lecture16.html [5] https://software.fujitsu.com/jp/manual/manualfiles/M080099/J2UZ9570/03Z2A/tun07/tun00084.htm [6] http://miqn.net/rtos/61.html [7] https://qiita.com/tobira-code/items/75d3034aed8bb9828981 [8] https://edn.itmedia.co.jp/edn/articles/1609/27/news009.html [9] https://zenn.dev/rita0222/articles/1f37a5bf910282 [10] https://uquest.tktk.co.jp/embedded/learning/lecture07-2.html [11] https://zenn.dev/mifurohi/articles/c2e29c482bdbed [12] https://qiita.com/hinakko/items/f0d29c64e2f5759af1b4 [13] https://www.renesas.com/jp/ja/document/apn/stack-estimation-using-call-walker-cs [14] https://it-trend.jp/development_tools/article/32-0041 [15] https://www.youtube.com/watch?v=nChAnySdzQo [16] https://qiita.com/yusuke_blog1026/items/6df869bf373926398f7d [17] https://qiita.com/hellokenta/items/3649214d333ef0e7dbac [18] https://monoist.itmedia.co.jp/mn/articles/1107/25/news004_2.html [19] https://www.info.kochi-tech.ac.jp/y-takata/pl2/part1/stack.html [20] https://info.iar.com/ja/knowledge/learn/programming/mastering-stack-and-heap-for-system-reliability