CHAP 6: 큐 yicho@gachon.ac.kr 1
큐 (QUEUE) 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 Ticket Box 전단 () 후단 () 2
큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 객체 : n 개의 element 형으로구성된요소들의순서있는모임 연산 : create() ::= 큐를생성한다. init(q) ::= 큐를초기화한다. is_empty(q) ::= 큐가비어있는지를검사한다. is_full(q) ::= 큐가가득찼는가를검사한다. enqueue(q, e) ::= 큐의뒤에요소를추가한다. dequeue(q) ::= 큐의앞에있는요소를반환한다음삭제한다. peek(q) ::= 큐에서삭제하지않고앞에있는요소를반환한다. 3
큐의응용 직접적인응용 시뮬레이션의대기열 ( 공항에서의비행기들, 은행에서의대기열 ) 통신에서의데이터패킷들의모델링에이용 프린터와컴퓨터사이의버퍼링 간접적인응용 스택과마찬가지로프로그래머의도구 많은알고리즘에서사용됨 생산자버퍼소비자 data QUEUE 4
배열을이용한큐 선형큐 : 배열을선형으로사용하여큐를구현 ( 그림 6-5,6-6) 삽입을계속하기위해서는요소들을이동시켜야함 문제점이많아사용되지않음 [-1] [0] [1] [2] [3] [4] [5] [-1] [0] [1] [2] [3] [4] [5] 원형큐 : 배열을원형으로사용하여큐를구현 [3] [2] [1] 5 [0] [MAX_SIZE-2] [MAX_SIZE-1]
큐의구조 큐의전단과후단을관리하기위한 2 개의변수필요 : 첫번째요소하나앞의인덱스 : 마지막요소의인덱스 3 4 2 B 5 1 A 6 0 7 6
3 4 3 4 2 5 2 5 1 6 1 A 6 0 7 0 7 (a) 초기상태 (b) A 삽입 3 4 3 4 2 B 5 2 B 5 1 A 6 1 6 0 7 0 7 7 (c) B 삽입 (d) A 삭제
공백상태, 포화상태 공백상태 : == 포화상태 : % M==(+1) % M 공백상태와포화상태를구별하기위하여하나의공간은항상비워둔다. 3 4 3 4 3 4 2 5 2 B C D E 5 2 B C D E 5 1 6 1 A G F 6 1 A H G F 6 0 7 0 7 0 7 (a) 공백상태 (b) 포화상태 (c) 오류상태 8
큐의연산 나머지 (modulo) 연산을사용하여인덱스를원형으로회전시킨다. // 공백상태검출함수 int is_empty(queuetype *q) { } return (q-> == q->); // 포화상태검출함수 int is_full(queuetype *q) { } return ((q->+1)%max_queue_size == q->); 9
큐의연산 10 나머지 (modulo) 연산을사용하여인덱스를원형으로회전시킨다. (p226-227) // 삽입함수 void enqueue(queuetype *q, element item) { } if( is_full(q) ) error(" 큐가포화상태입니다 "); q-> = (q->+1) % MAX_QUEUE_SIZE; q->queue[q->] = item; // 삭제함수 element dequeue(queuetype *q) { } if( is_empty(q) ) error(" 큐가공백상태입니다 "); q-> = (q->+1) % MAX_QUEUE_SIZE; return q->queue[q->];
연결된큐 연결된큐 (linked queue): 연결리스트로구현된큐 포인터는삭제와관련되며 포인터는삽입 는연결리스트의맨앞에있는요소를가리키며, 포인터는맨뒤에있는요소를가리킨다 큐에요소가없는경우에는 와 는 NULL A B NULL C D NULL 11
연결된큐에서의삽입과삭제 temp 프로그램 6.2 A B C D NULL 삽입 Rear 에서 A B C D NULL 프로그램 6.3 삭제 Front 에서 A B C D temp NULL 12 A B C D NULL
덱 (deque) 덱 (deque) 은 double-ended queue 의줄임말로서큐의전단 () 와후단 () 에서모두삽입과삭제가가능한큐 add_ add_ delete_ delete_ get_ 전단 () 후단 () get_ 13
덱 ADT 객체 : n 개의 element 형으로구성된요소들의순서있는모임 연산 : create() ::= 덱을생성한다. init(dq) ::= 덱을초기화한다. is_empty(dq) ::= 덱이공백상태인지를검사한다. is_full(dq) ::= 덱이포화상태인지를검사한다. add_(dq, e) ::= 덱의앞에요소를추가한다. add_(dq, e) ::= 덱의뒤에요소를추가한다. delete_(dq) ::= 덱의앞에있는요소를반환한다음삭제한다 delete_(dq) ::= 덱의뒤에있는요소를반환한다음삭제한다. get_(q) ::= 덱의앞에서삭제하지않고앞에있는요소를반환한다. get_(q) ::= 덱의뒤에서삭제하지않고뒤에있는요소를반환한다. 14
덱의연산 A C A B D add_(dq, A) add_(dq, D) A B A B D add_(dq, B) delete_(dq) C A B A B add_(dq, C) delete_(dq) 15
덱의구현 양쪽에서삽입, 삭제가가능하여야하므로일반적으로이중연결리스트사용 typedef int element; // 요소의타입 typedef struct DlistNode { element data; struct DlistNode *llink; struct DlistNode *rlink; } DlistNode; // 노드의타입 typedef struct DequeType { DlistNode *head; DlistNode *tail; } DequeType; // 덱의타입 16
덱에서의삽입연산 연결리스트의연산과유사 헤드포인터대신 head 와 tail 포인터사용 17
덱에서의삽입연산 void add_(dequetype *dq, element item) { } DlistNode *new_node = create_node(dq->tail, item, NULL); if( is_empty(dq)) dq->head = new_node; else dq->tail->rlink = new_node; dq->tail = new_node; 18
덱에서의삽입연산 // void add_(dequetype *dq, element item) { DlistNode *new_node = create_node(null, item, dq->head); } if( is_empty(dq)) else dq->tail = new_node; dq->head->llink = new_node; dq->head = new_node; 19
20 덱에서의삭제연산
덱에서의삭제연산 // 전단에서의삭제 element delete_(dequetype *dq) { element item; DlistNode *removed_node; 21 } if (is_empty(dq)) error(" 공백덱에서삭제 "); else { } removed_node = dq->head; // 삭제할노드 item = removed_node->data; // 데이터추출 dq->head = dq->head->rlink; // 헤드포인터변경 free(removed_node); // 메모리공간반납 if (dq->head == NULL) // 공백상태이면 dq->tail = NULL; else return item; // 공백상태가아니면 dq->head->llink=null;
덱에서의삭제연산 // 전단에서의삭제 element delete_(dequetype *dq) { element item; DlistNode *removed_node; 22 } if (is_empty(dq)) error(" 공백덱에서삭제 "); else { } removed_node = dq->tail; // 삭제할노드 item = removed_node->data; // 데이터추출 dq->tail = dq->tail->llink; // 헤드포인터변경 free(removed_node); // 메모리공간반납 if (dq->tail == NULL) // 공백상태이면 dq->head = NULL; else return item; // 공백상태가아니면 dq->tail->rlink=null;
큐의응용 : 버퍼 큐는서로다른속도로실행되는두프로세스간의상호작용을조화시키는버퍼역할을담당 CPU 와프린터사이의프린팅버퍼, 또는 CPU 와키보드사이의키 보드버퍼 대개데이터를생산하는생산자프로세스가있고데이터를소비하는소비자프로세스가있으며이사이에큐로구성되는버퍼가존재 23
큐의응용 : 시뮬레이션 큐잉이론에따라시스템의특성을시뮬레이션하여분석하는데이용 큐잉모델은고객에대한서비스를수행하는서버와서비스를받는고객들로이루어진다 은행에서고객이들어와서서비스를받고나가는과정을시뮬레이션 고객들이기다리는평균시간을계산 24