CHAP 6:큐.

Presentation on theme: "CHAP 6:큐."— Presentation transcript:

1 CHAP 6:큐

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

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

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

5 배열을 이용한 큐 선형큐: 배열을 선형으로 사용하여 큐를 구현 원형큐: 배열을 원형으로 사용하여 큐를 구현
삽입을 계속하기 위해서는 요소들을 이동시켜야 함 문제점이 많아 사용되지 않음 원형큐: 배열을 원형으로 사용하여 큐를 구현 [0] [-1] [1] [2] [3] [4] [5] front rear [0] [1] [2] [3] [MAX_SIZE-1] [MAX_SIZE-2] …

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

7 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 삽입

8 공백상태, 포화상태 공백상태: front == rear 포화상태: front % M==(rear+1) % M
공백상태와 포화상태를 구별하기 위하여 하나의 공간은 항상 비워둔다. 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) 오류상태

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

10 큐의 연산 나머지(modulo) 연산을 사용하여 인덱스를 원형으로 회전시킨다. // 삽입 함수
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];

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

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

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

14 덱 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(q) ::= 덱의 앞에서 삭제하지 않고 앞에 있는 요소를 반환한다. ▪ get_rear(q) ::= 덱의 뒤에서 삭제하지 않고 뒤에 있는 요소를 반환한다.

15 덱의 연산 front rear front rear C A B D A ddd_front(dq, A) ddd_rear(dq, D)
ddd_rear(dq, B) delete_front(dq) front rear front rear A B C A B delete_rear(dq) ddd_front(dq, C)

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

17 덱에서의 삽입연산 연결리스트의 연산과 유사 헤드포인터 대신 head와 tail 포인터 사용

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

19 덱에서의 삽입연산 // 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; }

20 덱에서의 삭제연산

21 덱에서의 삭제연산 // 전단에서의 삭제 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;

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

23 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);                      데이터 소비;      }   

24 큐의 응용: 시뮬레이션 큐잉이론에 따라 시스템의 특성을 시뮬레이션하여 분석하는 데 이용
큐잉모델은 고객에 대한 서비스를 수행하는 서버와 서비스를 받는 고객들로 이루어진다 은행에서 고객이 들어와서 서비스를 받고 나가는 과정을 시뮬레이션 고객들이 기다리는 평균시간을 계산

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

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

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

28 시뮬레이션 프로그램 // 0에서 1사이의 실수 난수 생성 함수 double random()
return rand()/(double)RAND_MAX; // 시뮬레이션에 필요한 여러가지 상태 변수 int duration=10; // 시물레이션 시간 double arrival_prob=0.7; // 하나의 시간 단위에 도착하는 평균 고객의 수 int max_serv_time=5; // 하나의 고객에 대한 최대 서비스 시간 int clock; // 시뮬레이션의 결과 int customers; // 전체고객수 int served_customers; // 서비스받은 고객수 int waited_time; // 고객들이 기다린 시간

29 시뮬레이션 프로그램 // 랜덤 숫자를 생성하여 고객이 도착했는지 도착하지 않았는지를 판단
int is_customer_arrived() if( random() < 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=(int)(max_serv_time*random()) + 1; enqueue(&queue, customer); printf("고객 %d이 %d분에 들어옵니다. 서비스시간은 %d분입니다.", customer.id, customer.arrival_time, customer.service_time); }

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

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

32 큐의 응용: 시물레이션 // 시뮬레이션 프로그램 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();