プログラミング 3 スタックとキュー.

Presentation on theme: "プログラミング 3 スタックとキュー."— Presentation transcript:

1 プログラミング 3 スタックとキュー

2 データ構造 データ構造：コンピュータがデータを扱うときに，扱 いやすくなるように加工したもの
今回扱うスタック（stack）とキュー（queue）は， データを一時的に蓄えるバッファと呼ばれるもののひ とつ

3 スタック(1) 「入れる」「出す」の操作を持つバッファ トレイの山を想像するとよい
入れる：プッシュ（push） 出す：ポップ（pop） トレイの山を想像するとよい 入れられた（プッシュされた）データは山のてっぺんに積ま れる 取り出し（ポップ）は山のてっぺんに対して行う 最後に入れたものが最初に出てくる：Last-In First-Out（LIFO）

4 スタック(2) ３ ４ ↓ ↓ ↓ ↑ ↓ ↑ ３ ４ ２ ２ ２ ２ ２ １ １ １ １ １ １ 1をプッシュ 2をプッシュ 3をプッシュ
ポップ 4をプッシュ ポップ ３ ４ ２ ２ ２ ２ ２ １ １ １ １ １ １

5 スタックの実装(1) 簡易なものは配列で実装できる 必要な変数宣言 int stack[STACKSIZE]; int sp = 0;
スタック本体となる配列 スタックに何個データが入っているかを保持する変数（ス タックポインタ） 必要な変数宣言 int stack[STACKSIZE]; int sp = 0; STACKSIZE はスタックの容量（大きさ）を定義した記号定 数

6 スタックの実装(2) ↓ ２ ２ Ｘ Ｘ Ｘ プッシュ スタックポインタの位置に 値を入れる スタックポインタを 1 増 やす sp→

7 スタックの実装(3) ２ ↑ ２ ２ Ｘ Ｘ Ｘ ポップ スタックポインタを 1 減 らす スタックポインタの位置の 値を返す sp→

8 キュー(1) 「入れる」「出す」の操作を持つバッファ レジや ATM の待ち行列を想像するとよい
入れる：エンキュー（enqueue） 出す：デキュー（dequeue） レジや ATM の待ち行列を想像するとよい 入れられた（エンキューされた）データは列の末尾に入れら れる 取り出し（デキュー）は列の先頭に対して行う 最初に入れたものが最初に出てくる：First-In First-Out（FIFO）

9 キュー(2) １ ← 1 をエンキュー １ ２ ← 2 をエンキュー １← ２ デキュー ２ ３ ← 3 をエンキュー ２← ３ デキュー

10 キューの実装(1) 簡易なものは配列で実装できる
キュー本体となる配列 キューの先頭・末尾を覚える変数（またはキューの先頭と データの個数を覚える変数） 必要な変数宣言 int queue[QUEUESIZE]; int head = 0, tail = 0; QUEUESIZE はキューの容量（大きさ）を定義した記号定数

11 キューの実装(2) ２ ３ ２ ３ ４ ← ２ ３ ４ エンキュー キューの末尾位置に値を代入する キューの末尾の要素 番号を 1 増やす
キューの末尾の要素 番号を 1 増やす ↓head ↓tail ２ ３ ↓head ↓tail ２ ３ ４ ← ↓head ↓tail ２ ３ ４

12 キューの実装(3) ２ ３ ４ ２← ３ ４ ← ３ ４ デキュー キューの先頭位置の値を取り出す キューの先頭の要素 番号を 1 増やす
キューの先頭の要素 番号を 1 増やす ↓head ↓tail ２ ３ ４ ↓head ↓tail ２← ３ ４ ← ↓head ↓tail ３ ４

13 スタックとキュー 使用頻度が高く，実装が容易なのはスタックのほう 格納できるデータ量に事実上制限がない実装もある （難しい）
キューについては，リングバッファという実装方法もある