[INA240] Data Structures and Practice Chapter 4. Queues [INA240] Data Structures and Practice Youn-Hee Han http://link.kut.ac.kr

0. Queue Concept Queue (큐) Waiting Line (대기열) 가장 먼저 넣은 것이 가장 먼저 빠져 나오는 특성 FIFO (First-In First-Out), FCFS (First-Come First-Served) 스택에 비해서 큐가 더 공정하다… (?) Data Structure

0. Queue Concept Definition of Queue Major operations a linear list in which data can only be inserted at one end (rear) and deleted from the other end (front) Major operations Enqueue: queue insert Dequeue: queue delete QueueFront: retrieve the data at the front (QueueRear: retrieve the data at the rear) Data Structure

1. Queue Operations Enqueue: queue insert operation The new element becomes the rear Queue is already full  overflow Dequeue: queue delete operation The data at the front is returned and removed Queue is empty  underflow Data Structure

1. Queue Operations QueueFront: retrieve data at the front QueueRear: retrieve data at the rear Conflict with general concept of Queue Data Structure

1. Queue Operations Queue Example (1/2) Data Structure

1. Queue Operations Queue Example (2/2) Data Structure

2. Queue Linked List Design Data Structure Queue Head front pointer rear pointer A count of the number of elements Queue의 Enqueue/Dequeue 연산 구현 양쪽 끝에서 일어남 Enqueue는 Rear Pointer에서, Dequeue는 Front Pointer에서 일어남 Data Structure

2. Queue Linked List Design Data Structure C code typedef struct node { void* dataPtr; struct node* link; } QUEUE_NODE; typedef struct { QUEUE_NODE* front; int count QUEUE_NODE* rear; } QUEUE; queueHead front counter rear end queueHead node data link end node front count rear Queue Head structure data link Node structure Data Structure

2. Queue Linked List Design Basic Queue Functions Enqueue 정책 [Queue에 노드가 없을 경우] front pointer는 새로운 노드를 가리킴 rear pointer도 새로운 노드를 가리킴 [Queue에 이미 노드가 있을 경우] front pointer는 변함없음 front pointer가 가리키는 노드의 link pointer가 새로운 노드를 가리킴 - rear pointer가 새로운 노드를 가리킴 Data Structure

2. Queue Linked List Design Basic Queue Functions Dequeue 정책 [Queue에 노드가 하나만 있을 경우] front pointer는 null이 됨 rear pointer도 null이 됨 하나의 노드를 삭제함 [Queue에 노드가 여러 개 있을 경우] rear pointer는 변함없음 front pointer는 삭제될 노드의 link pointer가 가리키는 노드를 가리킴 front pointer가 가리키는 노드를 삭제함 Data Structure

2. Queue Linked List Design 하나의 포인터로 Queue Header를 구현할 수 있을까? 포인터 하나로 구현한 큐 front pointer 한 개로 구현 vs. rear pointer 한 개로 구현? front pointer 하나로만 구현하면 삽입을 위해 끝까지 순회해야 함. rear pointer 하나로만은 구현 불가 front pointer rear pointer Data Structure

2. Queue Linked List Design 하나의 포인터로 Queue Header를 구현할 수 있을까? 원형 연결 리스트 (Circular Singly-linked List) 를 사용한다면? rear pointer 한 개로 구현 가능 마지막요소는 rear 로 접근 첫요소는 rear->next 로 접근 일반적으로는 front와 rear pointer 둘 다 활용한다. rear pointer Data Structure

3. Queue ADT Queue ADT (교재 159~) 구현할 함수 파일명: queues.h queues.h에 queue 관련 Data Structure와 관련 함수을 모두 구현 구현할 함수 QUEUE* createQueue (void)  Queue를 생성한다. QUEUE* destroyQueue (QUEUE* queue)  Queue를 삭제한다. bool enqueue (QUEUE* queue, void* itemPtr); bool dequeue (QUEUE* queue, void** itemPtr); bool queueFront (QUEUE* queue, void** itemPtr); bool queueRear (QUEUE* queue, void** itemPtr); int queueCount (QUEUE* queue)  Queue에 있는 Node의 수를 알아본다. bool emptyQueue (QUEUE* queue)  Queue가 비워 있으면 true 리턴 bool fullQueue (QUEUE* queue)  Queue가 꽉차서 더 이상 새로운 Node를 Enqueue 할 수 없으면 ture 리턴 Data Structure

3. Queue ADT 간단한 Queue ADT Test 프로그램 교재에 없는 내용 (queues_test.c) #include <stdio.h> #include <stdlib.h> #include "stdbool.h" #include "queues.h" int main (void) { int done = false; int* dataPtr; QUEUE* q; q = createQueue (); while (!done) { dataPtr = (int*)malloc(sizeof(int)); printf ("Enter a number: <EOF> to stop: "); if ((scanf ("%d" , dataPtr)) == EOF || fullQueue(q)) done = true; else enqueue (q, dataPtr); } printf ("\n\nThe time-ordered list of numbers:\n"); while (!emptyQueue (q)) { dequeue(q, &dataPtr); printf ("%3d\n", *dataPtr); free (dataPtr); destroyQueue (q); return 0; Enter a number: <EOF> to stop: 3 Enter a number: <EOF> to stop: 5 Enter a number: <EOF> to stop: 7 Enter a number: <EOF> to stop: <CTRL-Z> The time-ordered list of numbers: 3 5 7 Data Structure

3. Queue ADT Queue ADT Data Structure #include "stdbool.h" queues.h #include "stdbool.h" typedef struct node { void* dataPtr; struct node* next; } QUEUE_NODE; typedef struct { QUEUE_NODE* front; QUEUE_NODE* rear; int count; } QUEUE; QUEUE* createQueue (void); QUEUE* destroyQueue (QUEUE* queue); bool dequeue (QUEUE* queue, void** itemPtr); bool enqueue (QUEUE* queue, void* itemPtr); bool queueFront (QUEUE* queue, void** itemPtr); bool queueRear (QUEUE* queue, void** itemPtr); int queueCount (QUEUE* queue); bool emptyQueue (QUEUE* queue); bool fullQueue (QUEUE* queue); Queue ADT Data Structure stdbool.h #ifndef _STDBOOL_H #define _STDBOOL_H typedef int _Bool; #define bool _Bool #define true 1 #define false 0 #define __bool_true_false_are_defined 1 #endif Data Structure

3. Queue ADT createQueue QUEUE* createQueue (void) { QUEUE* queue; queue = (QUEUE*) malloc (sizeof (QUEUE)); if (queue) { queue->front = NULL; queue->rear = NULL; queue->count = 0; } return queue; Data Structure

3. Queue ADT enqueue bool enqueue (QUEUE* queue, void* itemPtr) { QUEUE_NODE* newPtr; if (!(newPtr = (QUEUE_NODE*)malloc(sizeof(QUEUE_NODE)))) return false; newPtr->dataPtr = itemPtr; newPtr->next = NULL; if (queue->count == 0) queue->front = newPtr; // 1) else queue->rear->next = newPtr; // 2) queue->rear = newPtr; // 3) (queue->count)++; // 4) return true; } 1) 4) 3) dataPtr next dataPtr next 3) 4) dataPtr next dataPtr next dataPtr next 2) dataPtr next Data Structure

3. Queue ADT dequeue bool dequeue (QUEUE* queue, void** itemPtr) { QUEUE_NODE* deleteLoc; if (!queue->count) return false; *itemPtr = queue->front->dataPtr; deleteLoc = queue->front; // 1) if (queue->count == 1) queue->rear = queue->front = NULL; // 2) else queue->front = queue->front->next; // 3) (queue->count)--; // 4) free (deleteLoc); return true; } 4) 2) 2) 1) dataPtr next 4) 1) 3) dataPtr next dataPtr next dataPtr next Data Structure

3. Queue ADT xxx yyy dequeue에서 placeholder 처리 (1/3): 잘못된 방법 int main (void) { … dataPtr = (int*)malloc(sizeof(int)); dequeue(q, dataPtr); } bool dequeue (QUEUE* queue, void* itemPtr) { … *itemPtr = queue->front->dataPtr; } deque 함수호출시 dataPtr= 0x00383330 dataPtr Heap space dataPtr이 지닌 0x00383880이 Assign됨 xxx yyy 0x00383330 itemPtr queue 0x0038333 0x00384fa8 Error: int 값 저장 장소에 주소값 할당 and void 포인터형 변수인 itremPtr을 derefencing 할 때에는 실제 타입으로 형변환 필요 *itemPtr front count rear 0x00383260 3 0x003832e8 dataPtr next 0x00383880 0x00383880 Data Structure

3. Queue ADT xxx yyy dequeue에서 placeholder 처리 (2/3): 잘못된 방법 int main (void) { … dataPtr = (int*)malloc(sizeof(int)); dequeue(q, dataPtr); } bool dequeue (QUEUE* queue, void* itemPtr) { … itemPtr = queue->front->dataPtr; } deque 함수호출시 dataPtr= 0x00383330 dataPtr Heap space dataPtr이 지닌 0x00383880이 Assign됨 xxx yyy 0x00383330 itemPtr queue 0x0038333 0x00384fa8 main()에서 정의된 dataPtr 값은 그대로 변함없음! front count rear 0x00383260 3 0x003832e8 dataPtr next 0x00383880 0x00383880 Data Structure

3. Queue ADT xxx yyy dequeue에서 placeholder 처리 (3/3): 올바른 방법 int main (void) { … dataPtr = (int*)malloc(sizeof(int)); dequeue(q, &dataPtr); } bool dequeue (QUEUE* queue, void** itemPtr) { … *itemPtr = queue->front->dataPtr; } dequeue 함수호출시 &dataPtr=0x0012ff54 dataPtr Heap space dataPtr의 주소를 할당함 xxx yyy 0x00383330 itemPtr queue 0x0012ff54 0x00384fa8 *itemPtr 주소값인 0x00383880이 Assign됨 front count rear 0x00383260 3 0x003832e8 dataPtr next 0x00383880 0x00383880 Data Structure

3. Queue ADT queueFront queueRear bool queueFront (QUEUE* queue, void** itemPtr) { if (!queue->count) return false; else { *itemPtr = queue->front->dataPtr; return true; } bool queueRear (QUEUE* queue, void** itemPtr) { if (!queue->count) return true; else { *itemPtr = queue->rear->dataPtr; return false; } Data Structure

3. Queue ADT emptyQueue fullQueue bool emptyQueue (QUEUE* queue) { return (queue->count == 0); } bool fullQueue (QUEUE* queue) { QUEUE_NODE* temp; temp = (QUEUE_NODE*)malloc(sizeof(QUEUE_NODE)); if (temp) { free (temp); return false; } return true; Data Structure

3. Queue ADT queueCount destroyQueue int queueCount(QUEUE* queue) { return queue->count; } QUEUE* destroyQueue (QUEUE* queue) { QUEUE_NODE* deletePtr; if (queue) { while (queue->front != NULL) { free (queue->front->dataPtr); deletePtr = queue->front; queue->front = queue->front->next; free (deletePtr); } free (queue); return NULL; front pointer Data Structure

4. Queuing Theory Queuing theory a field of applied mathematics that is used to predict performance of queues. Queuing Type Single-server queue Hot-food vender Multi-server queue Many bank tellers in a bank Multiple single-server queues Two common Elements in Queuing Theory Customer Any person or thing needing service Service Any activity needed to accomplish the required result Two factors affecting a queue Arrival Rate ( Queue Time) Service Time Response Time Queue Time + Service Time ….. Server .…... Customer Queue Servers Leaving Customer Multi-server Queuing System Data Structure

5. Queue Applications Business Online Application Customer online requests, jobs, or orders Computer System Job (or process) scheduling Print spool 교재에서 주어진 두 개의 Queue Applications Categorizing data Queue Simulation To study the performance of any queue application (Optional Study) 교재 외에 PPT 자료에서 주어지는 Queue Application Goal Seeking  BFS (Breadth First Search) Data Structure

5. Queue Applications Goal of Categorizing Data (교재 168~) For example Rearrange data in separated groups without destroying their original order in each group For example Four different groups Group 1: less than 10 Group 2: between 10 and 19 Group 3: between 20 and 29 Group 4: between 30 and greater Input Output Note: the numbers in each group have kept their original order 3 22 12 6 10 34 65 29 9 30 81 4 5 19 20 57 44 99 | 3 6 9 4 5 | 12 10 19 | 22 29 20 | 34 65 30 81 57 44 99 | Data Structure

5. Queue Applications Structures for Categorizing Data Initialization before calling fillQueues After calling fillQueues Data Structure

5. Queue Applications Source Codes: Categorizing Data File Name: catagorize.c #include <stdio.h> #include <stdlib.h> #include "stdbool.h" #include "queues.h" void fillQueues (QUEUE*, QUEUE*, QUEUE*, QUEUE*); void printQueues (QUEUE*, QUEUE*, QUEUE*, QUEUE*); void printOneQueue (QUEUE* pQueue); int main (void) { QUEUE* q0to9; QUEUE* q10to19; QUEUE* q20to29; QUEUE* qOver29; q0to9 = createQueue (); q10to19 = createQueue (); q20to29 = createQueue (); qOver29 = createQueue (); fillQueues (q0to9, q10to19, q20to29, qOver29); printQueues (q0to9, q10to19, q20to29, qOver29); return 0; } Data Structure

5. Queue Applications Source Codes: Categorizing Data File Name: catagorize.c void fillQueues (QUEUE* q0to9, QUEUE* q10to19, QUEUE* q20to29, QUEUE* qOver29) { int category; int item; int* dataPtr; int i; printf("Categorizing data:\n"); srand(79); for (i = 1; i <= 25; i++) { if (!(dataPtr = (int*) malloc (sizeof (int)))) printf("Overflow in fillQueues\a\n"), exit(100); *dataPtr = item = rand() % 51; // (0 ~ RAND_MAX)%51, RAND_MAX=32767 category = item / 10; printf("%3d", item); if (!(i % 11)) printf("\n"); Data Structure

5. Queue Applications Source Codes: Categorizing Data File Name: catagorize.c switch (category) { case 0 : enqueue (q0to9, dataPtr); break; case 1 : enqueue (q10to19, dataPtr); case 2 : enqueue (q20to29, dataPtr); default : enqueue (qOver29, dataPtr); } printf("\nEnd of data categorization\n\n"); return; Data Structure

5. Queue Applications Source Codes: Categorizing Data File Name: catagorize.c void printQueues (QUEUE* q0to9, QUEUE* q10to19, QUEUE* q20to29, QUEUE* qOver29) { printf("Data 0.. 9:"); printOneQueue (q0to9); printf("Data 10..19:"); printOneQueue (q10to19); printf("Data 20..29:"); printOneQueue (q20to29); printf("Data over 29:"); printOneQueue (qOver29); return; } Data Structure

5. Queue Applications Source Codes: Categorizing Data File Name: catagorize.c void printOneQueue (QUEUE* pQueue) { int lineCount; int* dataPtr; lineCount = 0; while (!emptyQueue (pQueue)) { dequeue (pQueue, (void*)&dataPtr); if (lineCount++ >= 10) { lineCount = 1; printf ("\n "); } printf("%3d ", *dataPtr); printf("\n"); return; Data Structure

5. Queue Applications C로 Random Number 만들기 void srand(unsigned int seed); Random Number Generation에 대한 seed 값 설정 흔히 사용하는 초기화 방법 int rand( void ); 하나의 (pseudo-)random number (정수)를 하나 발생시킴 발생되는 정수의 범위: 0 ~ RAND_MAX (32767) 두 함수 모두 <stdlib.h>를 필요로 함 time_t seed; //time_t의 구조체 변수 seed 변수 생성 time(&seed); //시스템 상의 현재 시간을 seed에 얻어온다. srand((unsigned int) seed); //srand 호출을 통하여 Random Number Generation에 대한 seed값 설정 Data Structure

5. Queue Applications C로 Random Number 만들기 For example #include <stdio.h> #include <stdlib.h> const int LOW = 10; const int HIGH = 1000; const int NUM_DATA = 50000; int main(void) { int data[50000]; int i; time_t seed; time(&seed); srand((unsigned int) seed); for (i = 0 ; i < NUM_DATA ; i++) { data[i] = rand() % (HIGH - LOW + 1) + LOW; } for (i = 0 ; i < NUM_DATA-1 ; i++) { printf ("%d\t", data[i]); Data Structure

5. Queue Applications Goal Seeking  너비우선탐색 (BFS: Breadth First Search) 소모적 탐색(消耗, Exhaustive Search) 방법의 일종 탐색 순서에 있어서 깊이보다는 폭을 우선적으로 취한다. 탐색 방법 0) A가 Origin 1) A에서 거리가 1인 모든 노드를 방문 2) 다음 방문한 노드에서 부터 거리가 1인 모든 노드, 즉 A에서 거리가 2인 모든 노드들을 방문한다. 3) 위와 같은 방법 반복 F까지의 경로가 있는가? A-B-G-C-E-H-D-F Data Structure

5. Queue Applications BFS을 위한 Queue 시작 노드를 enqueue dequeue와 동시에 인접 노드들을 enqueue 한번 enqueue한 노드는 다시 enqueue하지 않음 Queue에서 dequeue된 노드를 순차적으로 나열하면 그것이 BFS의 탐색 순서가 됨 Data Structure

5. Queue Applications BFS의 Pseudo-code BreadthFirstSearch(Origin) { createQueue();                 새로운 큐를 만들기 enqueue(Origin);              출발지를 큐에 삽입 Mark Origin as Visited;      출발지를 가 본 것으로 표시 while (!queueEmpty( )) { 빈 큐가 아닐 동안 queueFront(Front);      큐 front에 있는 노드를 Front로 복사 dequeue( );             큐 front 제거         for (Each Unvisited Nodes C Adjacent to Front) { enqueue(C);             큐에 삽입             Mark C as Visited;  가 본 것으로 표시         }      } } Data Structure

5. Queue Applications DFS vs. BFS Data Structure