スタック(Stack)データ構造の説明

Tags:

スタック(Stack)の概念

  • スタック(stack)は積み上げた山を意味する。
  • 一方の端からだけデータを入れたり取り出したりできる、後入れ先出し(LIFO: Last In First Out)形式のデータ構造である。
    • 最も最近入ったデータが最初に出る。

スタックの構造

  • スタック上端: top
  • スタック下端: 不要
  • 要素、項目
  • 挿入/削除演算

Stack

スタック(Stack)の演算

スタック(Stack)はLIFO(Last In First Out)に従う。つまり、最も最近スタックに追加した項目が、最初に削除される項目である。

  • push(x): 与えられた要素xをスタックの一番上に追加する。
  • pop(): スタックが空でなければ、一番上の要素を削除して返す。
  • isEmpty(): スタックが空なら真(true)、そうでなければ偽(false)を返す。
  • peek(): スタックが空でなければ、一番上の要素を削除せずに返す。
  • isFull(): スタックが満杯なら真(true)、そうでなければ偽(false)を返す。
  • size(): スタック内のすべての要素数を返す。
  • display(): スタック内のすべての要素を出力する。

スタック(Stack)の用途

  • 関数呼び出し
  • 再帰アルゴリズムを使う場合、スタックが有用である。
    • 再帰アルゴリズム
      • 再帰的に関数を呼び出す必要がある場合、一時データをスタックに入れる。
      • 再帰関数から戻ってバックトラック(backtrack)するときは、スタックに入れておいた一時データを取り出す必要がある。
      • スタックは、この一連の動作を直感的に可能にする。
      • また、スタックは再帰アルゴリズムを反復形式(iterative)で実装できるようにする。
  • Webブラウザの履歴(戻る)
  • 元に戻す(undo)
  • 逆順文字列の作成
  • 式の括弧検査(演算子優先順位表現のための括弧検査)
    • 例: 正しい括弧文字列(VPS, Valid Parenthesis String)の判定
  • 計算機(後置記法計算)

スタック(Stack)の使用例

参考