/ 큐 (QUEUE) Chapter 큐 : 먼저들어온데이터가먼저나가는자료구조 선입선출 (FIFO: First-In First-Out) ( 예 ) 매표소의대기열 큐 Ticket ox Dongwon Jeong djeong@kunsan.ac.kr Department of Kunsan National University 전단 () 후단 () 학습목표 큐 DT 큐의개념및추상데이터타입에대한이해 큐의구현방법 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 배열 링크드리스트 덱 / 데크의개념과구현방법 객체 : n개의 element형으로구성된요소들의순서있는모임 연산 : create() ::= 큐를생성한다. init(q) ::= 큐를초기화한다. is_empty(q) ::= 큐가비어있는지를검사한다. is_full(q) ::= 큐가가득찼는가를검사한다. enqueue(q, e) ::= 큐의뒤에요소를추가한다. dequeue(q) ::= 큐의앞에있는요소를반환한다음삭제한다. peek(q) ::= 큐에서삭제하지않고앞에있는요소를반환한다. 3
/ 큐의응용 큐의구조 직접적인응용 시뮬레이션의대기열 ( 공항에서의비행기들, 은행에서의대기열 ) 통신에서의데이터패킷들의모델링에이용 프린터와컴퓨터사이의버퍼링 간접적인응용 스택과마찬가지로프로그래머의도구 많은알고리즘에서사용됨 큐의전단과후단을관리하기위한 개의변수필요 : 첫번째요소하나앞의인덱스 : 마지막요소의인덱스 data 0 4 배열을이용한큐 (a) 초기상태 (b) 삽입 선형큐 (Linear queue) 배열을선형으로사용하여큐를구현 삽입을계속하기위해서는요소들을이동시켜야함 문제점이많아사용되지않음 [-] [0] [] [] [3] [4] [] [-] [0] [] [] [3] [4] [] 원형큐 (Circular queue) 배열을원형으로사용하여큐를구현 [] [] [3] [0] [MX_SIZE-] [MX_SIZE-] (c) 삽입 (d) 삭제 0 0
3 / 공백상태, 포화상태 연결된큐 공백상태 : == 포화상태 : % M==(+) % M 공백상태와포화상태를구별하기위하여하나의공간은항상비워둔다. C D E F G C D E F H G 연결된큐 (linked queue): 연결리스트로구현된큐 포인터는삭제와관련되며 포인터는삽입 는연결리스트의맨앞에있는요소를가리키며, 포인터는맨뒤에있는요소를가리킨다 큐에요소가없는경우에는 와 는 C D (a) 공백상태 (b) 포화상태 (c) 오류상태 8 0 큐의연산 연결된큐에서의삽입과삭제 나머지 (modulo) 연산을사용하여인덱스를원형으로회전시킨다. temp // 공백상태검출함수 int is_empty(queuetype *q) return (q-> == q->); // 포화상태검출함수 int is_full(queuetype *q) return ((q->+)%mx_queue_size == q->); // 삽입함수 void enqueue(queuetype *q, element item) if( is_full(q) ) error(" 큐가포화상태입니다 "); q-> = (q->+) % MX_QUEUE_SIZE; q->queue[q->] = item; // 삭제함수 element dequeue(queuetype *q) if( is_empty(q) ) error(" 큐가공백상태입니다 "); q-> = (q->+) % MX_QUEUE_SIZE; return q->queue[q->]; 삽입 삭제 C D C D C D temp C D 9
4 / 덱 (deque) 덱의연산 덱 (deque) 데크 Double-ended queue의줄임말 큐의전단 () 와후단 () 에서모두삽입과삭제가가능한큐 ddd_(dq, ) C D ddd_(dq, D) add_ add_ D delete_ delete_ ddd_(dq, ) delete_(dq) get_ 전단 () 후단 () get_ C ddd_(dq, C) delete_(dq) 4 덱 DT 덱의구현 객체 : 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) ::= 덱의뒤에서삭제하지않고뒤에있는요소를반환한다. 양쪽에서삽입, 삭제가가능하여야하므로일반적으로이중연결리스트사용 typedef int element; typedef struct DlistNode element data; struct DlistNode *llink; struct DlistNode *rlink; DlistNode; typedef struct DequeType DlistNode *head; DlistNode *tail; DequeType; // 요소의타입 // 노드의타입 // 덱의타입 3
/ 덱에서의삽입연산 큐의응용 : 버퍼 void add_(dequetype *dq, element item) DlistNode *new_node = create_node(dq->tail, item, ); if( is_empty(dq)) dq->head = new_node; else dq->tail->rlink = new_node; dq->tail = new_node; // void add_(dequetype *dq, element item) DlistNode *new_node = create_node(, item, dq->head); 연결리스트의연산과유사 헤드포인터대신 head 와 tail 포인터사용 큐는서로다른속도로실행되는두프로세스간의상호작용을조화시키는버퍼역할을담당 CPU와프린터사이의프린팅버퍼, 또는 CPU와키보드사이의키보드버퍼 대개데이터를생산하는생산자프로세스가있고데이터를소비하는소비자프로세스가있으며이사이에큐로구성되는버퍼가존재 if( is_empty(dq)) dq->tail = new_node; else dq->head->llink = new_node; dq->head = new_node; 8 덱에서의삭제연산 QueueType buffer; // 전단에서의삭제 element delete_(dequetype *dq) element item; DlistNode *removed_node; 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 == ) // 공백상태이면 dq->tail = ; else // 공백상태가아니면 dq->head->llink=; return item; /* 생산자프로세스 */ producer() while() 데이터생산 ; while( lock(buffer) == SUCCESS ) ; if(!is_full(buffer) ) enqueue(buffer, 데이터 ); unlock(buffer); /* 생산자프로세스 */ consumer() while() while( lock(buffer) == SUCCESS ) ; if(!is_empty(buffer) ) 데이터 = dequeue(buffer); 데이터소비 ; unlock(buffer); 9
/ 큐의응용 : 시뮬레이션 큐의응용 : 시물레이션 큐잉이론에따라시스템의특성을시뮬레이션하여분석하는데이용 큐잉모델은고객에대한서비스를수행하는서버와서비스를받는고객들로이루어진다 은행에서고객이들어와서서비스를받고나가는과정을시뮬레이션 고객들이기다리는평균시간을계산 // 시뮬레이션프로그램 void main() int service_time=0; clock=0; while(clock < duration) clock++; printf(" 현재시각 =%d\n",clock); if (is_customer_arrived()) insert_customer(clock); if (service_time > 0) service_time--; else service_time = remove_customer(); print_stat(); 0 큐의응용 : 시물레이션 시뮬레이션은하나의반복루프 현재시각을나타내는 clock이라는변수를하나증가 is_customer_arrived 함수를호출한다. is_customer_arrived 함수는랜덤숫자를생성 하여시뮬레이션파라미터변수인 arrival_prov와비교하여작으면새로운고객이들 어왔다고판단 고객의아이디, 도착시간, 서비스시간등의정보를만들어구조체에복사하고이구조 체를파라미터로하여큐의삽입함수 enqueue() 를호출한다. 여기서고객이필요로하는서비스시간은역시랜덤숫자를이용하여생성된다. 지금서비스하고있는고객이끝났는지를검사 : 만약 service_time이 0이아니면어떤 고객이지금서비스를받고있는중임을의미한다. clock이하나증가했으므로service_time을하나감소시킨다. 만약 service_time이 0이면현재서비스받는고객이없다는것을의미한다. 따라서큐 에서고객구조체를하나꺼내어서비스를시작한다.. 요약 큐의정의 큐를위한추상데이터타입 큐의주요연산 큐구현방법 배열을위한큐의구현 링크드리스트를이용한큐의구현 덱의정의 3
/ Dongwon Jeong djeong@kunsan.ac.kr http://ist.kunsan.ac.kr/ Lab. of Information Sciences & Technology, Department of Informatics & Statistics, Kunsan National Unversity, Gunsan, Korea 4