スタック

• 概要

  • データ記憶構造の一種
  • 後入れ先出し(Last In First Out : LIFO)
  • このようなデータ記憶構造になっているメモリ領域をスタック領域、あるいは単にスタックと呼ぶ

• 計算量

  • 1 回の処理は通常 O(1)

• メリット

  • 必要な分しか場所を使用しないのと、場所がフラグメント化しない

• デメリット

  • 最初に入ったデータが最後まで放置される

• データの読み書き

  • PUSH
    • スタックへのデータ書き込み
  • POP
    • スタックからデータを取り出す

• スタック領域

  • サブルーチンの呼び出しなどによって自動的に確保され、プログラムが一時的に使用するデータを格納するために用いられる
  • 不要になると自動的に解放

• 用途

  • プログラム内でサブルーチンを呼び出す際に、その戻り位置(リターンアドレス)を格納
  • サブルーチン内で定義された変数(内部変数、ローカル変数) の格納など、一時的に使用されるデータを格納する用途に使われる

• 通常のプログラムや初期データなどをメモリに格納する場合には低位のアドレスから使われていくが、スタックでは逆に高位のアドレスから使われる

  • スタックに PUSH するデータの数が増えることによって、メモリに格納されたプログラムやデータを破壊してしまうのを防ぐため