データ構造とアルゴリズム 第6回 キュー ~ データ構造(2)~
スタック ユニークな回答と多かった回答 ユニーク編 ・自分の家の冷蔵庫(新しいものばかり食べています)。 スタック ユニークな回答と多かった回答 ユニーク編 ・自分の家の冷蔵庫(新しいものばかり食べています)。 ・ティッシュを間違って2枚取り出したとき使わなかった1枚は再び突っ込みます。次に使うときにはそれを使うのでスタックでしょうか。 ・小学校でよく使う上から入れてどんどんためていくファイル。 ・メジャー。 多数編 ・箪笥の服 ・レポートの提出 ・銃(ハンドガン)のマガジン ・食器 ・コピー機の紙
キュー ユニークな回答と多かった回答 ユニーク編 ・学校:基本的に先に入った人から出ていく(卒業していく) ・観覧車 キュー ユニークな回答と多かった回答 ユニーク編 ・学校:基本的に先に入った人から出ていく(卒業していく) ・観覧車 ・髪の毛:先に生えたところから切られるから ・「便通」←食べたものは下から出る(笑) 多数編 ・自動販売機 ・スーパー(コンビニを含む)商品の品だし ・シャープペンシル ・エスカレーター ・行列
キュー(待ち行列、Queue)
本日の内容:キュー キュー 抽象データ型としてのキュー 単方向リストによるキューの実現 循環配列(リングバッファ)によるキューの実現 英国では行列することをqueueingという。 The verb queue means to form a line, and to wait for services. Queue is also the name of this line.
待ち行列 レジ A君の レポート B君の レポート C君の レポート
キュー (Queue) キュー:要素の挿入がいつも一方の端( )からしかできず,要素の削除はその反対の端( )からしかできないリスト 先に入れた要素ほど,先に出る 別名 先入れ先出しリスト (first-in first-out) 先頭 ↓ 末尾 ↓ a1 a2 a3 a4
抽象データ型としてのキュー 抽象データ型: データ構造+操作 キュー 操作 要素の挿入 ( ) 要素を 並べたもの 要素の取出し ( )
キューの操作 CREATE(Q ) TOP(Q )
キューの操作 Enq (x, Q ):要素xをキューQの( )に入れる. Deq (Q ):キューの( )の要素を削除する キューの操作 Enq (x, Q ):要素xをキューQの( )に入れる. Deq (Q ):キューの( )の要素を削除する <同時にSの先頭の要素を返す場合もある>
例 末尾 ↓ 先頭 ↓ Q 初期状態 Enq(A, Q) Enq(B, Q) Enq(C, Q) Deq(Q) Enq(Deq(Q), Q)
例 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
単方向リストによるキューの実現 Queue型 front rear a0 a1 an-1 構造体 struct queue型 rear->element front->element キューの末尾要素 rear->nextはNULL キューの先頭要素
キューの型定義とEnqueueのプログラム例(p38) /* セルを表わす構造体の定義 */ struct cell { int element; struct cell *next; }; … main() struct queue struct cell *front; struct cell *rear; } セルのデータ構造はリストのときと同じ。 ここではint型の要素としたが、どのような型でも良い。 先頭を指すfrontと末尾を指すrearの2つのポインタから成る構造体でキューを定義
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;
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)
① 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));
②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
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
④ 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
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
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;
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
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
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
Deqの実現(単方向リスト版) Deq(Q)[void dequeue(struct queue *S)] S q Q … ② qにS->frontを代入する(=前の先頭要素へのポインタをqに保持しておく) ③ S->frontを前の先頭要素の次(=前の2番目)へのポインタとする ④ 削除するセルの領域を解放 S q ④ free(q); a0 a1 an-1 front rear Q
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
Deqの実現(単方向リスト版) Deq(Q)[void dequeue(struct queue *S)] S S Q Q ・いずれの場合も先頭要素が削除される ・教科書p38のプログラムはvoid関数なので、戻り値はなし 元のキューQが要素1個だった場合 元のキューQが要素2個以上だった場合 S S a1 an-1 front front Q rear rear Q
配列によるキューの実現 element [0] [1] データがある部分 front p [p] a0 a1 rear k [k] an-1
先頭と末尾の要素の位置を格納するためのメンバー キューの型の定義 (配列版) #define N 7 struct QUEUE/* 構造体queueの定義 */ { int element[N]; int front; int rear; }; 先頭と末尾の要素の位置を格納するためのメンバー
配列によるキューの実現 element [0] Deq (キューの先頭の要素を返す場合もある) Enq [1] front p [p] a0 rear k [k] an-1 [k+1] [N-1]
Enq,Deqを繰り返すとどうなるか? N=7の場合 element ⇒これを防ぐ手法の一つが, [0] [1] [2] 3 front [3] A [4] B [5] C 6 rear [6] D
循環配列(Ring Buffer) element[N-1] element[0] front rear a0 a1 an-1 …
循環配列(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
循環配列の問題点 このままでは,「 」と「 」の区別がつかない [0] rear an-1 front a0 a1 [N-1] このままでは,「 」と「 」の区別がつかない キューがFULLの状態 ⇒ 一見問題無いように思えるが… [0] rear an-1 front a0 a1 [N-1]
循環配列の問題点(続き) [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]
解決方法 「キューがFULLの状態」と「キューが空の状態」をどう区別するか? 方法2: 待ち行列が配列いっぱいにならないようにする etc.
方法2: 待ち行列が配列いっぱいにならないようにする例 解決方法 方法2: 待ち行列が配列いっぱいにならないようにする例 ( ) ( ) [0] [0] rear rear an-1 front front a0 a1 [N-1] [N-1]