Internet Computing Laboratory @ KUT Youn-Hee Han Chapter 3. Queues Internet Computing Laboratory @ KUT Youn-Hee Han

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 queueHead front counter rear end queueHead node data link end node Data Structure C code front count rear Queue Head structure data link Node structure typedef struct node { void* dataPtr; struct node* link; } QUEUE_NODE; typedef struct { QUEUE_NODE* front; int count QUEUE_NODE* rear; } QUEUE; 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가 새로운 노드를 가리킴 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 하나로만은 구현 불가 원형 연결 리스트 (Circular Singly-linked List) 를 사용한다면? rear pointer 한 개로 구현 가능 마지막요소는 Rear 로 접근 첫요소는 Rear->Next 로 접근 일반적으로는 front와 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, (void**)&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 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); 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/2): 올바른 방법 int main (void) { … dataPtr = (int*)malloc(sizeof(int)); dequeue(q, (void**)&dataPtr); } bool dequeue (QUEUE* queue, void** itemPtr) { … *itemPtr = queue->front->dataPtr; } deque 함수호출시 &dataPtr=0x0012ff54 dataPtr Heap space 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 xxx yyy dequeue에서 placeholder 처리 (2/2): 잘못된 방법 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 주소값인 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 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; Data Structure