CHAP 6:큐

큐(QUEUE) 큐: 먼저 들어온 데이터가 먼저 나가는 자료구조 선입선출(FIFO: First-In First-Out) (예)매표소의 대기열 Ticket Box 후단(rear) 전단(front)

큐 ADT 삽입과 삭제는 FIFO순서를 따른다. 삽입은 큐의 후단에서, 삭제는 전단에서 이루어진다. ∙객체: n개의 element형으로 구성된 요소들의 순서있는 모임 ∙연산:   ▪ create() ::=     큐를 생성한다.  ▪ init(q) ::=      큐를 초기화한다.  ▪ is_empty(q) ::=  큐가 비어있는지를 검사한다.  ▪ is_full(q) ::=   큐가 가득 찼는가를 검사한다.  ▪ enqueue(q, e) ::=   큐의 뒤에 요소를 추가한다.  ▪ dequeue(q) ::=   큐의 앞에 있는 요소를 반환한 다음 삭제한다.  ▪ peek(q) ::=    큐에서 삭제하지 않고 앞에 있는 요소를 반환한다. Enqueue: pronounced N-Q Enqueue means adding an item to the end of the queue

큐의 응용 스택과 마찬가지로 프로그래머의 유용한 도구 시뮬레이션의 대기열(공항에서의 비행기들, 은행에서의 대기열) 통신에서의 데이터 패킷들의 모델링에 이용 프린터와 컴퓨터 사이의 버퍼링 소비자 생산자 버퍼 data QUEUE

배열을 이용한 큐 원형큐: 배열을 원형으로 사용하여 큐를 구현 … [3] [2] … [1] [0]

큐의 구조 큐의 전단과 후단을 관리하기 위한 2개의 변수 필요 front: 첫번째 요소 바로 전의 인덱스 rear: 마지막 요소의 인덱스 rear 3 4 2 5 B A 1 6 7 front

3 3 4 4 2 2 5 5 A 1 6 1 6 7 7 rear front rear front (a) 초기상태 (b) A 삽입 rear 3 4 rear 3 4 2 5 B 2 5 B 1 6 A 1 6 7 front 7 front (d) A 삭제 (c) B 삽입

공백상태, 포화상태 공백상태: front == rear 포화상태: front == (rear+1) % size (즉, front가 rear보다 하나 앞에 있으면 포화상태) 공백상태와 포화상태를 구별하기 위하여 하나의 공간은 항상 비워둔다. 3 3 3 4 4 4 C D C D 2 2 2 5 5 5 B E B E F F A A 1 6 1 6 1 6 G G H 7 7 7 rear front rear front front rear (a) 공백상태 (b) 포화상태 (c) 오류상태

큐의 연산 나머지 연산(modulo operation)을 사용하여 인덱스를 원형으로 회전시킨다. // 공백 상태 검출 함수 int is_empty(QueueType *q) { return (q->front == q->rear); } // 포화 상태 검출 함수 int is_full(QueueType *q) return ((q->rear+1)%MAX_QUEUE_SIZE == q->front);

큐의 연산 배열을 이용한 원형큐 프로그램은 교재 참조 // 삽입 함수 void enqueue(QueueType *q, element item) { if( is_full(q) ) error("큐가 포화상태입니다"); q->rear = (q->rear+1) % MAX_QUEUE_SIZE; q->queue[q->rear] = item; } // 삭제 함수 element dequeue(QueueType *q) if( is_empty(q) ) error("큐가 공백상태입니다"); q->front = (q->front+1) % MAX_QUEUE_SIZE; return q->queue[q->front]; 배열을 이용한 원형큐 프로그램은 교재 참조

연결된 큐 연결된 큐(linked queue): 연결리스트로 구현된 큐 front 포인터는 삭제와 관련되며 rear 포인터는 삽입 front는 연결 리스트의 맨 앞에 있는 요소를 가리키며, rear 포인터는 맨 뒤에 있는 요소를 가리킨다 큐에 요소가 없는 경우에는 front와 rear는 NULL A B NULL C D front rear

연결된 큐에서의 삽입과 삭제 삽입 삭제 front rear temp A B C D NULL front rear A B C D

덱(deque) 덱(deque)은 double-ended queue의 줄임말로서 큐의 전단(front)과 후단(rear)에서 모두 삽입과 삭제가 가능한 큐 전단(front) 후단(rear) add_front delete_front get_front add_rear delete_rear get_rear

덱 ADT ∙객체: n개의 element형으로 구성된 요소들의 순서있는 모임 ∙연산: ▪ create() ::= 덱을 생성한다. ▪ init(dq) ::= 덱을 초기화한다. ▪ is_empty(dq) ::= 덱이 공백상태인지를 검사한다. ▪ is_full(dq) ::= 덱이 포화상태인지를 검사한다. ▪ add_front(dq, e) ::= 덱의 앞에 요소를 추가한다. ▪ add_rear(dq, e) ::= 덱의 뒤에 요소를 추가한다. ▪ delete_front(dq) ::= 덱의 앞에 있는 요소를 반환한 다음 삭제한다 ▪ delete_rear(dq) ::= 덱의 뒤에 있는 요소를 반환한 다음 삭제한다. ▪ get_front(dq) ::= 덱의 앞에 있는 요소를 삭제하지 않고 반환한다. ▪ get_rear(dq) ::= 덱의 뒤에 있는 요소를 삭제하지 않고 반환한다.

덱의 연산 front rear front rear C A B D A add_front(dq, A) add_rear(dq, D) add_rear(dq, B) delete_front(dq) front rear front rear A B C A B delete_rear(dq) add_front(dq, C)

덱의 구현 양쪽에서 삽입, 삭제가 가능하여야 하므로 일반적으로 이중연결 리스트 사용 typedef int element;            // 요소의 타입 typedef struct DlistNode {     // 노드의 타입      element data;      struct DlistNode *llink;      struct DlistNode *rlink; } DlistNode; typedef struct DequeType {     // 덱의 타입      DlistNode *head;      DlistNode *tail; } DequeType;

덱에서의 삽입연산

덱에서의 삽입연산 void add_rear(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; }

덱에서의 삽입연산 // void add_front(DequeType *dq, element item) { DlistNode *new_node = create_node(NULL, item, dq->head); if( is_empty(dq)) dq->tail = new_node; else dq->head->llink = new_node; dq->head = new_node; }

덱에서의 삭제연산

덱에서의 삭제연산 // 전단에서의 삭제 element delete_front(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 == NULL) // 공백상태이면 dq->tail = NULL; else // 공백상태가 아니면 dq->head->llink=NULL; } return item;

큐의 응용: 버퍼 큐는 서로 다른 속도로 실행되는 두 프로세스 간의 상호 작용을 조화시키는 버퍼 역할을 담당 CPU와 프린터 사이의 프린팅 버퍼, 또는 CPU와 키보드 사이의 키보드 버퍼 대개 데이터를 생산하는 생산자 프로세스가 있고 데이터를 소비하는 소비자 프로세스가 있으며 이 사이에 큐로 구성되는 버퍼가 존재

QueueType buffer; /* 생산자 프로세스 */ producer() {      while(1){              데이터 생산;              while( lock(buffer) != SUCCESS ) ;              if( !is_full(buffer) ){                      enqueue(buffer, 데이터);              }              unlock(buffer);      } } /* 소비자 프로세스 */ consumer()               while( lock(buffer) != SUCCESS )  ;              if( !is_empty(buffer) ){                      데이터 = dequeue(buffer);                      데이터 소비;      }   

큐의 응용: 시뮬레이션 시스템의 특성을 시뮬레이션하여 분석하는 데 이용 고객에 대한 서비스를 수행하는 서버와 서비스를 받는 고객들을 고려 예를 들어, 은행에서 고객이 들어와서 서비스를 받고 나가는 과정을 시뮬레이션 고객들이 기다리는 평균시간을 계산 큐잉 이론(Queueing Theory): 대기자 수와 대기 시간의 관계를 수학적으로 분석한 이론을 '대기 이론' 혹은 '큐잉 이론(Queueing Theory)'이라 한다.  

시뮬레이션 프로그램 typedef struct{ int id; int arrival_time; int service_time; }element; element queue[MAX_QUEUE_SIZE]; int front, rear; }QueueType; QueueType queue;

시뮬레이션 프로그램 // 시뮬레이션에 필요한 여러가지 상태 변수 int duration=10; // 시뮬레이션 시간 double arrival_prob=0.7; // 하나의 단위 시간에 고객이 도착할 확률 int max_serv_time=5; // 하나의 고객에 대한 최대 서비스 시간 int clock; // 시뮬레이션의 결과 int customers; // 전체고객수 int served_customers; // 서비스받은 고객수 int waited_time; // 고객들이 기다린 시간

시뮬레이션 프로그램 // 랜덤 숫자를 생성하여 고객이 도착했는지 도착하지 않았는지를 판단 int is_customer_arrived() { double random_prob = (double) rand()/RAND_MAX; if( random_prob < arrival_prob ) return TRUE; else return FALSE; } // 새로 도착한 고객을 큐에 삽입 void insert_customer(int arrival_time) element customer; customer.id = customers++; customer.arrival_time = arrival_time; customer.service_time=(rand()%5) + 1; enqueue(&queue, customer); printf("고객 %d이 %d분에 들어옵니다. 서비스시간은 %d분입니다.", customer.id, customer.arrival_time, customer.service_time); rand () -  The function rand() generates the sequence of pseudo random numbers. It generates the random number between(inclusive) 0 and RAND_MAX.  RAND_MAX is a constant defined in header file “stdlib.h”. 보통, RAND_MAX = 32767

시뮬레이션 프로그램 // 큐에서 기다리는 고객을 꺼내어 고객의 서비스 시간을 반환한다. int remove_customer() { element customer; int service_time=0; if (is_empty(&queue)) return 0; customer = dequeue(&queue); service_time = customer.service_time; served_customers++; waited_time += clock - customer.arrival_time; printf("고객 %d이 %d분에 서비스를 시작합니다. 대기시간은 %d분이었습니다." , customer.id, clock, clock - customer.arrival_time); return service_time; }

시뮬레이션 프로그램 // 통계치를 출력한다. print_stat() printf("서비스 받은 고객수 = %d", served_customers); printf("전체 대기 시간 = %d분", waited_time); printf("1인당 평균 대기 시간 = %f분", (double)waited_time/served_customers); printf("아직 대기중인 고객수 = %d", customers - served_customers); }

시뮬레이션 프로그램 // 시뮬레이션 프로그램 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(); if (service_time > 0) // 현재 서비스중인 고객에게 계속 서비스 제공해야 하는 경우 service_time--; // 현재 서비스중인 고객에게 계속 서비스 제공

시뮬레이션 프로그램 설명 시뮬레이션은 하나의 반복 루프 현재시각을 나타내는 clock이라는 변수를 매 반복마다 하나씩 증가 is_customer_arrived 함수를 호출한다. is_customer_arrived 함수는 랜덤 숫자를 생성하여 시뮬레이션 파라미터 변수인 arrival_prob와 비교하여 작으면 새로운 고객이 들어왔다고 판단 고객의 아이디, 도착시간, 서비스 시간 등의 정보를 만들어 구조체에 복사하고 이 구조체를 파라미터로 하여 큐의 삽입 함수 enqueue()를 호출한다.

시뮬레이션 프로그램 설명 고객이 필요로 하는 서비스 시간은 역시 랜덤숫자를 이용하여 생성된다. 지금 서비스하고 있는 고객이 끝났는지를 검사: 만약 service_time이 0이 아니면 어떤 고객이 지금 서비스를 받고 있는 중임을 의미한다. clock이 하나 증가했으므로 service_time을 하나 감소시킨다. 만약 service_time이 0이면 현재 서비스 받는 고객이 없다는 것을 의미한다. 따라서 큐에서 고객 구조체를 하나 꺼내어 서비스를 시작한다.