データ構造とアルゴリズム 第6回 キュー ～ データ構造（2）～.

Presentation on theme: "データ構造とアルゴリズム 第6回 キュー ～ データ構造（2）～."— Presentation transcript:

1 データ構造とアルゴリズム 第6回 キュー ～ データ構造（2）～

2 スタック ユニークな回答と多かった回答 ユニーク編 ・自分の家の冷蔵庫(新しいものばかり食べています)。
スタック　ユニークな回答と多かった回答 ユニーク編 ・自分の家の冷蔵庫(新しいものばかり食べています)。 ・ティッシュを間違って2枚取り出したとき使わなかった1枚は再び突っ込みます。次に使うときにはそれを使うのでスタックでしょうか。 ・小学校でよく使う上から入れてどんどんためていくファイル。 ・メジャー。 多数編 ・箪笥の服 ・レポートの提出 ・銃(ハンドガン)のマガジン ・食器 ・コピー機の紙

3 キュー ユニークな回答と多かった回答 ユニーク編 ・学校：基本的に先に入った人から出ていく(卒業していく) ・観覧車
キュー　ユニークな回答と多かった回答 ユニーク編 ・学校：基本的に先に入った人から出ていく(卒業していく) ・観覧車 ・髪の毛：先に生えたところから切られるから ・「便通」←食べたものは下から出る(笑) 多数編 ・自動販売機 ・スーパー(コンビニを含む)商品の品だし ・シャープペンシル ・エスカレーター ・行列

4 キュー(待ち行列、Queue)

5 本日の内容：キュー キュー 抽象データ型としてのキュー 単方向リストによるキューの実現 循環配列（リングバッファ）によるキューの実現
英国では行列することをqueueingという。 The verb queue means to form a line, and to wait for services. Queue is also the name of this line.

6 待ち行列 レジ A君の レポート B君の レポート C君の レポート

7 キュー　(Queue) 　 キュー：要素の挿入がいつも一方の端（　　　）からしかできず，要素の削除はその反対の端（　　　　）からしかできないリスト 先に入れた要素ほど，先に出る 別名 先入れ先出しリスト 　　　　　　 (first-in first-out) 先頭 ↓ 末尾 ↓ a1 a2 a3 a4

8 抽象データ型としてのキュー 抽象データ型：　データ構造＋操作 キュー 操作 要素の挿入 （　　　　　　　　　　　　） 要素を 並べたもの 要素の取出し （　　　　　　　　　　　　　）

9 キューの操作 　 CREATE(Q ) TOP(Q )

10 キューの操作 Enq (x, Q )：要素ｘをキューQの（ ）に入れる． Deq (Q )：キューの（ ）の要素を削除する
キューの操作　　　　　 Enq (x, Q )：要素ｘをキューQの（　　　　）に入れる． Deq (Q )：キューの（　　　　）の要素を削除する ＜同時にSの先頭の要素を返す場合もある＞

11 例　 末尾 ↓ 先頭 ↓ Q 初期状態 Enq(A, Q) Enq(B, Q) Enq(C, Q) Deq(Q) Enq(Deq(Q), Q)

12 例 Q 末尾 ↓ 先頭 ↓ 初期状態 Enq(A, Q) A Enq(B, Q) B A Enq(C, Q) C B A Deq(Q) C
例　 末尾 ↓ 先頭 ↓ Q 初期状態 Enq(A, Q) A Enq(B, Q) B A Enq(C, Q) C B A Deq(Q) C B A Enq(Deq(Q), Q) B C

13 単方向リストによるキューの実現 Queue型 front rear a0 a1 an-1 構造体 struct queue型
rear->element front->element キューの末尾要素 rear->nextはNULL キューの先頭要素

14 キューの型定義とEnqueueのプログラム例（p38）
/* セルを表わす構造体の定義 */ struct cell { int element; struct cell *next; }; … main() struct queue struct cell *front; struct cell *rear; } セルのデータ構造はリストのときと同じ。 ここではint型の要素としたが、どのような型でも良い。 先頭を指すfrontと末尾を指すrearの２つのポインタから成る構造体でキューを定義

15 Enqのプログラム例（p38） … Main() { struct queue Q; Q.front =Q.rear =NULL; }
void enqueue(init x, struct queue *S) struct cell *p; p=(struct cell *)malloc(sizeof(struct cell)); if(S ->rear != NULL) S ->rear->next = p; S ->rear = p; if(S ->front == NULL) S ->front = p; S ->rear->element = x; S ->rear->next = NULL; return;

16 Enqの実現(単方向リスト版) S 初期状態 Q front rear front, rearともにNULL
struct queue型の変数Q struct queue型を指すポインタ S 初期状態 front, rearともにNULL 関数enqueueにおいて、仮引数Sは、struct queue 型を指すポインタ Q front rear struct queue Q; Q.front =Q.rear =NULL; 教科書では、両方とも Qなので混乱する。 スライドでは、ポインタをSとしておく … void enqueue(init x, struct queue *S)

17 ① p = (struct cell *)malloc(sizeof(struct cell));
Enqの実現(単方向リスト版) Enq(x, Q) [void enqueue(int x, struct queue *S)] ①新しいセル用のメモリを確保し， S Q a0 a1 an-1 front rear p ① p = (struct cell *)malloc(sizeof(struct cell));

18 ②if(S ->rear != NULL) S ->rear->next = p;
Enqの実現(単方向リスト版) Enq(x, Q) [void enqueue(int x, struct queue *S)] ① 新しいセル用のメモリを確保し， pはそのセルを指すポインタとする ② Sが指しているキューQが S ②if(S ->rear != NULL) S ->rear->next = p; Q a0 a1 an-1 front rear p

19 Enqの実現(単方向リスト版) Enq(x, Q) [void enqueue(int x, struct queue *S)] S Q p
② Sが指しているキューQが空でなければ、 S->rear->nextが新しいセルを指す（pを代入） ③ S Q a0 a1 an-1 front rear ③ S ->rear = p; p

20 ④ if(S ->front == NULL) S ->front = p;
Enqの実現(単方向リスト版) Enq(x, Q) [void enqueue(int x, struct queue *Q)] ① 新しいセル用のメモリを確保し， pはそのセルを指すポインタとする ② Sが指しているキューQが空でなければ、 S->rear->nextが新しいセルを指す（pを代入） ③ S->rearが新しいセルを指す（pを代入） ④ Sが指しているキューQが空ならば、 S ④ if(S ->front == NULL) S ->front = p; S p Q Q front front rear rear

21 Enqの実現(単方向リスト版) Enq(x, Q) [void enqueue(int x, struct queue *Q)] S Q p
… ④ Sが指しているキューQが空ならば、 S->frontが新しいセルを指す（pを代入） ⑤新しいセルに ⑥新しいセルは S Q a0 a1 an-1 front rear ⑤ S ->rear->element = x; ⑥ S ->rear->next = NULL; p

22 Deqのプログラム例（p38） void dequeue(struct queue *S) { struct cell *q;
if(S->front == NULL) printf(“Error: Queue is empty. ¥n);exit(1); } else q = S->front; S->front = S->front->next; free(q); if(S->front == NULL) S->rear = NULL; return;

23 Deqの実現(単方向リスト版) Deq(Q)[void dequeue(struct queue *S)] S Q
Sが指すQのfront がNULLならキューが空 　① エラーメッセージを表示して関数を終了 S ① if(S->front == NULL) { printf(“Error: Queue is empty. ¥n); exit(1); } Q front rear

24 Deqの実現(単方向リスト版) Deq(Q)[void dequeue(struct queue *S)] S q Q …
　② qにS->frontを代入する（＝ ） S q ② q = S->front; a0 a1 an-1 front Q rear

25 Deqの実現(単方向リスト版) Deq(Q)[void dequeue(struct queue *S)] S q Q …
　② qにS->frontを代入する（＝前の先頭要素へのポインタをqに保持しておく） 　③ S->frontを S q a0 a1 an-1 front Q ③ S->front = S->front->next; rear

26 Deqの実現(単方向リスト版) Deq(Q)[void dequeue(struct queue *S)] S q Q …
　② qにS->frontを代入する（＝前の先頭要素へのポインタをqに保持しておく） 　③ S->frontを前の先頭要素の次（＝前の２番目）へのポインタとする ④ 削除するセルの領域を解放 S q ④ free(q); a0 a1 an-1 front rear Q

27 Deqの実現(単方向リスト版) Deq(Q)[void dequeue(struct queue *S)] q S S Q Q
（= S->front がNULLの場合は）　 ⑤ キューQは空とする（ ） ⑤ if(S->front == NULL) S->rear = NULL; q S S a0 front Q front Q rear rear

28 Deqの実現(単方向リスト版) Deq(Q)[void dequeue(struct queue *S)] S S Q Q
・いずれの場合も先頭要素が削除される ・教科書p38のプログラムはvoid関数なので、戻り値はなし 元のキューQが要素１個だった場合 元のキューQが要素２個以上だった場合 S S a1 an-1 front front Q rear rear Q

29 配列によるキューの実現 element [0] [1] データがある部分 front p [p] a0 a1 rear k [k] an-1

30 先頭と末尾の要素の位置を格納するためのメンバー
キューの型の定義 (配列版) #define N 7 struct QUEUE/* 構造体queueの定義 */ { int element[N]; int front; int rear; }; 先頭と末尾の要素の位置を格納するためのメンバー

31 配列によるキューの実現 element [0] Deq （キューの先頭の要素を返す場合もある） Enq [1] front p [p] a0
rear k [k] an-1 [k+1] [N-1]

32 Enq，Deqを繰り返すとどうなるか？ N=7の場合 element
⇒これを防ぐ手法の一つが， [0] [1] [2] 3 front [3] A [4] B [5] C 6 rear [6] D

33 循環配列(Ring Buffer)　 element[N-1] element[0] front rear a0 a1 an-1 …

34 循環配列(Ring Buffer) element element element [0] [0] [0] G 1 front 1 rear
[1] A [1] [1] H [2] B [2] [2] 3 front [3] C [3] C [3] 4 rear [4] D [4] D [4] 5 front [5] [5] E [5] E 6 rear [6] [6] F [6] F

35 循環配列の問題点 このままでは，「 」と「 」の区別がつかない [0] rear an-1 front a0 a1 [N-1]
このままでは，「　　　　　　　　　　　　　」と「　　　　　　　　　　　　」の区別がつかない キューがFULLの状態 　　⇒ 一見問題無いように思えるが… [0] rear an-1 front a0 a1 [N-1]

36 循環配列の問題点（続き） [0] an-1 [0] [1] [1] front rear rear front
ここからDeqを行うとキューは空になる frontとrearの関係が， キューがFULLの時と同じ! [0] an-1 [0] [1] [1] front rear rear Deq front [N-1] [N-1]

37 解決方法 「キューがFULLの状態」と「キューが空の状態」をどう区別するか？
方法2： 待ち行列が配列いっぱいにならないようにする etc.

38 方法2： 待ち行列が配列いっぱいにならないようにする例
解決方法 方法2： 待ち行列が配列いっぱいにならないようにする例 （　　　　　　　　　　） （　　　　　　　　　　） [0] [0] rear rear an-1 front front a0 a1 [N-1] [N-1]