Download presentation
Presentation is loading. Please wait.
1
アルゴリズムと データ構造 第4回 スタック・キュー
2
スタック スタックとは データを一時的に蓄える際利用するデータ構造 最後に入れたものが最初に取り出される：後入れ先出し（LIFO）
関数呼び出しや再帰アルゴリズムの非再帰実現などにも使用
3
スタック スタックの詳細 データ操作 スタックの上と下 データを入れる：プッシュ（push） データを取り出す：ポップ（pop）
プッシュ、ポップが行われる側：頂上（top） その反対側：底（bottom）
4
スタック スタックの動き push pop top 3 1 2 3 3 2 bottom 1
5
スタック スタックの実現 pop push ptr ptr ptr ptr ptr 15 28 29 5 7 5 7 15 29 28 28
6
キュー キューとは データを一時的に蓄える際利用するデータ構造 最初に入れたものが最初に取り出される：先入れ先出し（FIFO） 待ち行列
7
キュー キューの詳細 データ操作 キューの上と下 データを入れる：エンキュー（enqueue） データを取り出す：デキュー（dequeue）
データを取り出す側：先頭（front） その反対側：末尾（rear）
8
キュー キューの動き enqueue dequeue front 1 1 2 3 rear 2 1 3
9
キュー キューの実現（配列版） dequeue enqueue ptr ptr ptr ptr ptr 15 28 29 5 7 5 7
10
キュー キューの実現（リングバッファ版） dequeue enqueue rear rear rear front front rear
7 5 28 29 15 28 29 68 39 5 7 15 68
Similar presentations
