Internet Computing KUT Youn-Hee Han

Presentation on theme: "Internet Computing KUT Youn-Hee Han"— Presentation transcript:

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

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

3 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

4 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

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

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

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

8 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

9 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

10 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

11 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

12 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

13 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

14 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

15 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

16 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

17 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

18 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 0x itemPtr queue 0x0012ff54 0x00384fa8 *itemPtr 주소값인 0x 이 Assign됨 front count rear 0x 3 0x003832e8 dataPtr next 0x 0x Data Structure

19 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= 0x dataPtr Heap space 주소값인 0x 이 Assign됨 xxx yyy 0x itemPtr queue 0x 0x00384fa8 main()에서 정의된 dataPtr 값은 그대로 변함없음! front count rear 0x 3 0x003832e8 dataPtr next 0x 0x Data Structure

20 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

21 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

22 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