슬라이드 1

Transcription

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

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

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

8 공백상태, 포화상태 공백상태 : front == rear 포화상태 : front % M==(rear+1) % M 공백상태와포화상태를구별하기위하여하나의공간은항상비워둔다 B C D E 5 2 B C D E A G F 6 1 A H G F front rear front rear 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 front rear A B NULL C D NULL

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

13 연결된큐에서의삽입

14 연결된큐에서의삭제

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

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

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

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

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

20 덱에서의삽입연산

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

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

23 덱에서의삭제연산

24 덱에서의삭제연산 // 전단에서의삭제 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 return item; // 공백상태가아니면 dq->head->llink=null;

25 덱에서의삭제연산

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

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

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

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

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

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

32 시뮬레이션프로그램 // 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; // 고객들이기다린시간

33 시뮬레이션프로그램 // 랜덤숫자를생성하여고객이도착했는지도착하지않았는지를판단 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);

34 시뮬레이션프로그램 // 큐에서기다리는고객을꺼내어고객의서비스시간을반환한다. 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;

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

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