강의 #6 큐(Queue).

Presentation on theme: "강의 #6 큐(Queue)."— Presentation transcript:

1 강의 #6 큐(Queue)

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

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

4 큐(Queue) ADT (2) 삽입(enqueue) & 삭제(dequeue) 연산 예:

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

6 큐의 구현 배열을 이용한 큐 연결리스트를 이용한 큐 두 개의 변수를 사용 선형 큐(Linear Queue)
원형 큐(Circular Queue) 연결리스트를 이용한 큐 두 개의 변수를 사용 큐의 전단(front) – 데이터를 삭제하는 위치 큐의 후단(rear) – 데이터를 삽입하는 위치

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

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

9 선형 큐의 동작 삽입 & 삭제 연산 동작 계속적인 삽입 연산을 위해 원소 이동이 필요

10 원형 큐의 동작 1 2 3 4 5 6 7 front rear (a) 초기상태 1 2 3 4 5 6 7 front rear A
1 2 3 4 5 6 7 front rear (a) 초기상태 1 2 3 4 5 6 7 front rear A (b) A 삽입 rear= rear%M

11 1 2 3 4 5 6 7 front rear B (d) A 삭제 1 2 3 4 5 6 7 front rear A B (c) B 삽입 front= front%M 1 2 3 4 5 6 7 front rear (e) C 삽입 B C 1 2 3 4 5 6 7 front rear (f) D 삽입 B C D

12 공백상태, 포화상태 공백상태: 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) 오류상태

13 원형 큐의 구현 (1) 배열과 두 개의 인덱스 변수를 가진 구조체로 원형 큐를 정의
#define MAX_QUEUE_SIZE 100 typedef int element; typedef struct { element queue[MAX_QUEUE_SIZE]; int front, rear; } QueueType; // 공백 상태 검출 함수 int is_empty(QueueType *q) { return (q->front == q->rear); } // 포화 상태 검출 함수 int is_full(QueueType *q) return ((q->rear+1)%MAX_QUEUE_SIZE == q->front);

14 원형 큐의 구현 (2) 삽입 및 삭제 연산에서 나머지(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]; element peek(QueueType *q) return q->queue[(q->front+1)&MAX_QUEUE_SIZE];

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

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

17 연결된 큐의 구현 (1) 큐 노드와 두 개의 큐 포인터 변수를 가진 큐를 정의 typedef int element;
typedef struct QueueNode{ element item; struct QueueNode *link; } QueueNode; typedef struct { struct QueueNode *front, *rear; } QueueType; // 공백 상태 검출 함수 int is_empty(QueueType *q) { return (q->front == NULL); } // 포화 상태 검출 함수 int is_full(QueueType *q) return (q->rear == NULL);

18 연결된 큐의 구현 (2) 삽입 및 삭제 연산에서 나머지(modulo) 연산을 사용하여 인덱스를 원형으로 회전시킨다.
// 삽입 함수 void enqueue(QueueType *q, element item) { QueueNode * temp= (QueueNode *)malloc(sizeof(QueueNode); if (temp == NULL) error(“메모리를 할당할 수 없습니다.”): else { temp->item = item; temp->link = NULL; if (is_empty(q) ) { q->front = temp; q->rear = temp; } q->rear->link = temp;

19 연결된 큐의 구현 (3) // 삭제 함수 // 삭제 함수 element dequeue(QueueType *q)
{ QueueNode * temp = front; element item; if( is_empty(q) ) error("큐가 공백상태입니다"); else { item = temp->item; q->front = temp->link; if (q->front == NULL) q->rear = NULL; free(temp); return item; } // 삭제 함수 element peek(QueueType *q) { QueueNode * temp = front; element item; if( is_empty(q) ) error("큐가 공백상태입니다"); else { item = temp->item; return item; }

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

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

22 덱의 연산 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)

23 덱의 구현 양쪽에서 삽입, 삭제가 가능하여야 하므로 일반적으로 이중연결리스트 사용
typedef int element;           // 요소의 타입 typedef struct DlistNode {     // 노드의 타입      element data;      struct DlistNode *llink;      struct DlistNode *rlink; } DlistNode; typedef struct DequeType {     // 덱의 타입      DlistNode *head;      DlistNode *tail; } DequeType; DlistNode *create_node(DlistNode *link, element item, DlistMode *rlink) { DlistNode *node =(DlistNode *)malloc(sizeof(DlistNode)); if (node == NULL) error(“메모리 할당 오류”); node->llink = llink; node->data = item; node->rlink = rlink; return node; }

24 덱에서의 삽입연산 연결리스트의 연산과 유사 헤드포인터 대신 head와 tail 포인터 사용
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; 연결리스트의 연산과 유사 헤드포인터 대신 head와 tail 포인터 사용

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

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

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

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

29 큐의 응용: 시물레이션(2) 시뮬레이션은 하나의 반복 루프 현재시각을 나타내는 clock이라는 변수를 하나 증가
is_customer_arrived 함수를 호출한다. is_customer_arrived 함수는 랜덤 숫자를 생성하여 시뮬레이션 파라미터 변수인 arrival_prov와 비교하여 작으면 새로운 고객이 들어왔다고 판단 고객의 아이디, 도착시간, 서비스 시간 등의 정보를 만들어 구조체에 복사하고 이 구조체를 파라미터로 하여 큐의 삽입 함수 enqueue()를 호출한다. 고객이 필요로 하는 서비스 시간은 역시 랜덤숫자를 이용하여 생성 지금 서비스하고 있는 고객이 끝났는지를 검사: 만약 service_time이 0이 아니면 어떤 고객이 지금 서비스를 받고 있는 중임을 의미 clock이 하나 증가했으므로 service_time을 하나 감소시킨다. 만약 service_time이 0이면 현재 서비스받는 고객이 없다는 것을 의미한다. 따라서 큐에서 고객 구조체를 하나 꺼내어 서비스를 시작한다.

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