スタック（stack）とキュー（queue）

• ここでは配列を使って物理的な実装を行なっているが、 連結リスト等で実装することもできる

スタック（stack）

• スタック（stack）とは、何かが積み重なった山のことである
• 後入れ先出し（Last In First Out : LIFO）型の記憶装置である
• 以下の操作が許されている
  • ：スタックトップにデータを置く
    • プッシュ（push）
  • ：スタックトップのデータを取り出す
    • ポップ（pop）

New 新しい空のスタックを作る Push 新たなデータをスタックトップに置く Pop スタックトップのデータを取り出す Peek スタックトップのデータ値を見る この実現では、配列を使っている

キュー（queue）

• キュー（queue）とは、待ち行列（line）のことである
• 先入れ先出し（First In First Out : FIFO）型の記憶装置である
• 以下の操作が許されている
  • キューの末尾、後端、後ろ、終端（tail, rear, back, end）に挿入する
    • 挿入する（insert）、置く（put）、加える（add）、加列する（enqueue）
  • キューの先頭、前端（head, front）から削除する
    • 削除する（remove）、消す（delete）、除列する（dequeue）

New 新しい空のキューを作る Insert 新たなデータをキューの末尾に挿入する Remove キューの先頭のデータを取り出す Peek キューの先頭のデータ値を見る この実現では、配列を使ってリングバッファ（ring buffer）を構成している

プライオリティキュー（priority queue）

• プライオリティキューは、優先度の順に並んだキューである
• 削除は先頭からなされるが、挿入時にはキーの順に並べられる

New 新しい空のプライオリティキューを作る Insert 新たなデータをキューに挿入する Remove キューの先頭のデータを取り出す Peek キューの先頭のデータ値を見る この実現では配列を使っているが、ヒープ（heap）が使われることが多い