자료구조: CHAP 6 큐 2017. 5. 18 컴퓨터공학과 하 상 호.

Presentation on theme: "자료구조: CHAP 6 큐 2017. 5. 18 컴퓨터공학과 하 상 호."— Presentation transcript:

1 자료구조: CHAP 6 큐 컴퓨터공학과 하 상 호

2 큐(queue)란? Ticket Box

3 큐(queue)란? 선입 선출의 리스트 한쪽 끝에서 삽입되고, 다른 끝에서 삭제만 허용되는 유한 순서 리스트
전단: 삭제가 일어나는 곳 후단: 삽입이 일어나는 곳 선입 선출의 리스트 FIFO(First-In First-Out) Vs. 스택 후단(rear) 전단(front)

4 큐의 ADT 객체: 0개 이상의 원소를 가진 유한 순서 리스트 연산: q: 큐, e: 원소 create() ::= 큐 생성
init(q) ::= 큐를 초기화 is_empty(q) ::= if (q가 비어 있으면) then return true else return false is_full(q) ::= if (q가 꽉 차있으면) then return true enqueue(q, e) ::= if (!is_full(q)) then q의 후단에 e를 삽입 else return error deqeueu(q) ::= if (is_empty(s)) then return error else q의 전단에서 항목을 삭제하여 반환 peek(q) ::= if (is_empty(s)) then return error else q의 전단에서 항목을 삭제하지 않고 반환

5 큐의 구현 배열 이용 연결 리스트 이용 A B NULL C D front rear

6 배열 이용 큐 구현 선형 큐 문제점은? 일차원 배열로 표현: q(n), n은 배열의 크기
2개의 인덱스 변수 필요: front, rear 초기화: front = rear = -1 큐의 만원 조건: rear = n-1 큐의 공백 조건: front = rear 문제점은? enqueue(q, item) ? dequeue(q) ? [0] [-1] [1] [2] [3] [4] [5] front rear

7 배열 이용 큐 구현 원형 큐 배열을 원형으로 구성 선형 큐의 문제점 해결 큐의 삭제로 인한 빈 공간 초래 … [3] [2]
[0] [1] [2] [3] [MAX_SIZE-1] [MAX_SIZE-2] …

8 원형 큐 구성 front, rear를 0으로 초기화
rear <- (rear + 1) mod n front <- (front + 1) mod n 큐의 공백 조건은? 1 2 3 4 5 6 7 front rear A B 큐의 포화 조건은?

9 원형 큐 동작 1 2 3 4 5 6 7 front rear A B 삽입 초기상태 삽입 삭제

10 원형 큐 공백/포화 상태 공백 상태: front = rear 포화 상태: front = (rear + 1) mod n 3 3
4 4 C D 2 2 5 5 B E F A 1 6 1 6 G 7 7 front rear front rear 공백 상태 포화 상태

11 원형 큐 연산 나머지 연산자 이용 enqueue(q, item) dequeue(q) is_empty(q)
if front = rear then return true; else return false; end is_empty is_full(q) if (rear + 1) mod n = front end is_full

12 Test: 원형 큐 크기가 6인 원형 큐 q에서 다음과 같이 삽입과 삭제 연산이 이루어질 경우에, 각 단계에서의 원형 큐의 내용(큐의 내용, front, near의 값)을 나타내라. enqueue(q, 1) enqueue(q, 2) enqueue(q, 3) dequeue(q) enqueue(q,4) enqueue(q,5)

13 원형 큐 데이터 타입 구현 queueType을 다음과 같이 정의 원형 큐 연산을 정의해보라.
#define MAX_QUEUE_SIZE 100 typedef int element; typedef struct { element queue[MAX_QUEUE_SIZE]; int front, rear; } queue_type;

14 queueType 연산 init(queue_type* q) { } int is_empty(queue_type q)
#define MAX_QUEUE_SIZE 100 typedef int element; typedef struct { element queue[MAX_QUEUE_SIZE]; int front, rear; } queue_type; queueType 연산 init(queue_type* q) { } int is_empty(queue_type q) int is_full(queue_type q)

15 queueType 연산 enqueue(queue_type* q, element item) { }
#define MAX_QUEUE_SIZE 100 typedef int element; typedef struct { element queue[MAX_QUEUE_SIZE]; int front, rear; } queue_type; enqueue(queue_type* q, element item) { } element dequeue(queue_type* q)

16 예제: 원형 큐 연산 #define MAX_QUEUE_SIZE 5 typedef int element; typedef struct { element queue[MAX_QUEUE_SIZE]; int front, rear; } queue_type; … queue_type q; init(&q); enqueue(&q, 1); enqueue(&q, 2); enqueue(&q, 3); dequeue(&q); enqueue(&q, 4); enqueue(&q, 5); enqueue(&q, 6); 다음 각 큐 연산시 큐의 상태를 그려라. 여러분은 q에 포함된 항목, front, rear의 위치를 보여야 한다.

17 원형 큐 원형 큐의 공간을 모두 사용하려면?

18 연결리스트 이용 큐 구현 연결된 큐(linked queued) 연결된 큐 구성 배열로 구현된 큐와 비교하면?
연결리스트로 구현된 큐 연결된 큐 구성 2개의 포인터: front: 삭제를 위해서 rear: 삽입을 위해서 초기값은? 배열로 구현된 큐와 비교하면? A B NULL C D front rear

19 연결된 큐 삽입 연산 (1) 고려사항 q = null인 경우 A B C D front rear NULL node 삽입

20 연결된 큐 삽입 연산 (2) enqueue(q, item) // q에 item을 포함하는 노드를 생성하여 추가
end enqueue //// 노드 생성 및 초기화 if (q가 비어 있으면) then else endif

21 연결된 큐 삭제 연산 (1) 고려사항 삭제 q = null인 경우 삭제 후 q가 null이 되는 경우
A B C D front rear NULL node 삭제

22 연결된 큐 삭제 연산 (2) dequeue(q) // q로부터 한 개 노드를 삭제하여 포함된 data 반환
end dequeue if (q가 비어 있으면) then else

23 연결된 큐 데이터 타입 구현 연결된 큐의 연산을 정의해보라. // 큐의 노드 표현 typedef int element;
typedef struct node node; typedef node* nodeptr; typedef struct { element data; nodeptr link; } node; // 연결된 큐 표현 nodeptr front; nodeptr rear; } queue_type;

24 연결된 큐 연산 void init(queue_type *q) { // 큐를 초기화하고, 반환 }
typedef struct { element data; nodeptr link; } node; nodeptr front; nodeptr rear; } queue_type; 연결된 큐 연산 void init(queue_type *q) { // 큐를 초기화하고, 반환 } int is_empty(queue_type q) { // 큐가 비어있는지 여부 검사

25 연결된 큐 연산 void enqueue(queue_type* q, element item) { }
typedef struct { element data; nodeptr link; } node; nodeptr front; nodeptr rear; } queue_type; 연결된 큐 연산 void enqueue(queue_type* q, element item) { } element dequeue(queue_type* q)

26 예제: 연결 큐 연산 다음 각 큐 연산 결과를 그려라. typedef struct { element data;
node* link; } node; node* front; node* rear; } queue_type; … queue_type q; init(&q); enqueue(&q, 1); enqueue(&q, 2); enqueue(&q, 3); dequeue(&q); enqueue(&q, 4); 다음 각 큐 연산 결과를 그려라.

27 덱(deque) 정의 전단(front) 후단(rear) 큐의 전단과 후단에서 모두 삽입과 삭제가 가능한 큐
덱(deque: double-ended queue)라고 함 전단(front) 후단(rear) add_front delete_front peek_front add_rear delete_rear peek_rear

28 덱(deque) 추상데이터 타입 ∙객체: 0개 이상의 원소를 가진 유한 순서 리스트 ∙연산: dq: 덱, e: 원소
▪ create() ::= 덱, dq를 생성한다. ▪ 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) ::= 덱의 뒤에서 삭제하지 않고 뒤에 있는 요소를 반환한다.

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

30 덱의 구현 덱을 구현하기에 적절한 자료구조는? 전단(front) 후단(rear) add_front delete_front
peek_front add_rear delete_rear peek_rear

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

32 덱의 삽입 연산 연결리스트의 연산과 유사 헤드포인터 대신 head와 tail 포인터 사용
void add_rear(deque_type* q, element item)

33 덱의 삭제 연산 void delete_front(deque_type* q)

34 큐의 응용: 버퍼 큐는 서로 다른 속도로 실행되는 두 프로세스 간의 상호 작용을 조화시키는 버퍼 역할을 담당

35 큐의 응용: 버퍼 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);                      데이터 소비;      }   

36 큐의 응용: Queuing theory 큐를 이용하는 문제를 다루는 분야 은행/슈퍼마켓 – 서비스 대기 시간
컴퓨터 – 응답 대기 시간 대중교통: 기차, 버스 등 – 평균 대기 시간

37 큐의 응용: 시뮬레이션 큐잉이론에 따라 시스템의 특성을 시뮬레이션하여 분석 서버 고객의 평균 대기시간 시뮬레이션 arrival
고객은 랜덤한 간격으로 도착 고객 서비스 시간을 랜덤하게 결정 한 고객 서비스가 종료되면, 대기큐로부터 다른 고객을 서비스 주어진 시간동안 고객들의 평균 대기시간을 계산 서버 arrival

38 예제: 은행 시뮬레이션(프로그램 6.10) int serviceTime = 0; // 고객의 서비스 시간 표현
clock = 0; // 현재 시간을 표현 while (clock < 시뮬레이션 기간) { // clock++; if (고객이 도달했으면) {// 확률적으로 판단 // 고객을 큐에 삽입 // 이때, 고객의 arrival time, service time을 설정 // service time은 난수 발생으로 설정 } if (serviceTime > 0) //현재 서버가 고객을 서비스 중이면 serviceTime--;’ else { // 큐로부터 고객을 꺼내서 새로운 서비스를 시작 // 고객의 serviceTime 설정 // 고객의 대기시간 계산 // 서비스 받은 고객 수 증가 // 고객이 평균 대기시간을 계산하여 출력

39 프로그램 6.10: 은행 서비스 시뮬레이션 // 시뮬레이션 프로그램 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();