04장.큐

Transcription

1 DATA STRUCTURES USING C CHAPTER 큐 1/33

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

3 큐 ADT 삽입과삭제는 FIFO 순서를따른다. 삽입은큐의후단에서, 삭제는전단에서이루어진다. 데이터 : 선입선출 (FIFO) 의접근방법을유지하는요소들의모음 연산 : init(): 큐를초기화한다. enqueue(e): 주어진요소 e 를큐의맨뒤에추가한다. dequeue(): 큐가비어있지않으면맨앞요소를삭제하고반환한다. is_empty(): 큐가비어있으면 true 를아니면 false 를반환한다. peek(): 큐가비어있지않으면맨앞요소를삭제하지않고반환한다. is_full(): 큐가가득차있으면 true 을아니면 false 을반환한다. size(): 큐의모든요소들의개수를반환한다. 3/33

4 큐의연산 enqueue(a) A enqueue(b) A B enqueue(c) A B C dequeue() A B C dequeue() B C 4/33

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

6 배열을이용한큐 : 선형큐 배열을선형으로사용하여큐를구현 [-1] [0] [1] [2] [3] [4] front rear (a) 초기상태 front rear (d) enqueue(5) front rear (b) enqueue(3) front rear (e) dequeue() front rear (c) enqueue(7) front rear (f) dequeue() 삽입을계속하기위해서는요소들을이동시켜야함 [-1] [0] [1] [2] [3] [4] [-1] [0] [1] [2] [3] [4] front rear 항목들을전단쪽으로모두이동 front rear 6/33

7 해결방법 원형큐 원형큐 : 배열을원형으로사용하여큐를구현 [3] [2] [1] [0] [[MAX_QUEUE_SIZE-2] [MAX_QUEUE_SIZE-1] 7/33

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

9 원형큐의삽입과삭제연산예 [3] [4] [3] [4] [3] [4] [2] [5] [2] [5] [2] rear B [5] [1] [6] rear [1] A [6] [1] A [6] rear front [0] 초기상태 [7] front [0] [0] [7] [7] front enqueue( A) enqueue( B) rear [2] rear [3] [3] [3] [4] rear [4] [4] [2] C C D B [5] B [5] B [2] [5] [1] [1] [1] front [6] front [6] front [6] [0] [7] [0] [7] [0] [7] dequeue() enqueue( C) enqueue( D) 9/33

10 공백상태, 포화상태 공백상태 : front == rear 포화상태 : front % M==(rear+1) % M 공백상태와포화상태를구별방법은? 하나의공간은항상비워둠 [3] [4] [3] [4] [3] [4] [2] [2] [2] [5] [5] [5] [1] [1] [1] [6] [6] [6] [0] [7] [0] [7] [0] [7] front rear front rea r front rea r ( a) 공백상태 ( b) 포화상태 ( c) 오류상태 10/33

11 큐의연산 나머지 (modulo) 연산을사용하여인덱스를원형으로회전시킨다. 삽입연산 enqueue(x) rear (rear+1) mod MAX_QUEUE_SIZE; data[rear] x; 삭제연산 dequeue() front (front+1) mod MAX_QUEUE_SIZE; return data[front]; 11/33

12 원형큐의구현 원형큐를위한데이터 int 큐에서 Element 는 int 로지정 전역변수사용 원형큐의단순한연산들 #define MAX_QUEUE_SIZE 100 #define Element int Element data[max_queue_size]; int front; int rear; void init_queue() { front = rear = 0; ; } int is_empty() { return front == rear;; } int is_full() { return (rear+1)%max_queue_size == front; } int size() { return (rear-front+max_queue_size)%max_queue_size; } 12/33

13 원형큐의구현 void enqueue( Element val ) { if( is_full() ) error(" 큐포화에러 "); rear = (rear+1) % MAX_QUEUE_SIZE; data[rear] = val; } Element dequeue( ) { if( is_empty() ) error(" 큐공백에러 "); front = (front+1) % MAX_QUEUE_SIZE; return data[front]; } Element peek( ) { if( is_empty() ) error(" 큐공백에러 "); return data[(front+1) % MAX_QUEUE_SIZE]; } 13/33

14 사용방법 void main() { int i; init_queue( ); for( i=1 ; i<10 ; i++ ) enqueue( i ); print_queue(" 선형큐 enqueue 9 회 "); printf("\tdequeue() --> %d\n", dequeue()); printf("\tdequeue() --> %d\n", dequeue()); printf("\tdequeue() --> %d\n", dequeue()); print_queue(" 선형큐 dequeue 3 회 "); } 9 번 enqueue() 연산후 설명출력현재항목수큐내용 3 번 dequeue() 연산후 14/33

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

16 덱 ADT 큐와데이터는동일 연산은추가됨 데이터 : 전단과후단을통한접근을허용하는요소들의모음 연산 : init(): 덱을초기화한다. add_front(e): 주어진요소 e 를덱의맨앞에추가한다. delete_front(): 전단요소를삭제하고반환한다. add_rear(e): 주어진요소 e 를덱의맨뒤에추가한다. delete_rear(): 후단요소를삭제하고반환한다. is_empty(): 공백상태이면 TRUE 를아니면 FALSE 를반환한다. get_front(): 전단요소를삭제하지않고반환한다. get_rear(): 후단요소를삭제하지않고반환한다. is_full(): 덱이가득차있으면 TRUE 를아니면 FALSE 를반환한다. size(): 덱내의모든요소들의개수를반환한다. 16/33

17 덱의연산 전단 후단 add_front(a): A add_rear(b): A B add_front(c): C A B add_rear(d): C A B D delete_front(): C A B D delete_rear(): A B D 17/33

18 원형덱의연산 큐와데이터는동일함 연산은유사함. 큐와알고리즘이동일한연산 init_deque() : 원형큐의 init_queue() print_deque(): 원형큐의 print_queue() add_rear(): 원형큐의 enqueue() delete_front(): 원형큐의 dequeue() get_front(): 원형큐의 peek() 18/33

19 원형덱의연산 덱에서추가된연산 delete_rear(), add_front(), get_real() 반대방향의회전이필요 예 : [2] B front (front-1+max_queue_size) % MAX_QUEUE_SIZE; rear (rear -1+MAX_QUEUE_SIZE) % MAX_QUEUE_SIZE; [3] C rear [4] D [5] rear [2] B [3] C [4] [5] rear [2] B [3] C [4] [5] [1] front A [0] [7] [6] [1] front A [6] [0] [7] delete_rear() [1] A E [0] [6] [7] front add_front(e) 19/33

20 원형덱의구현 void init_deque( ) { init_queue( ); } void add_rear(element val) { enqueue( val);} Element delete_front( ) { return dequeue(); } Element get_front( ) { return peek(); } void print_queue(char msg[]) { print_queue(msg); } void add_front( Element val ) { if( is_full() ) error(" 덱포화에러 "); data[front] = val; front = (front-1+max_queue_size) % MAX_QUEUE_SIZE; } Element delete_rear( ) { Element ret; if( is_empty() ) error(" 덱공백에러 "); ret = data[rear]; rear = (rear-1+max_queue_size) % MAX_QUEUE_SIZE; return ret; } Element get_rear( ){ if( is_empty() ) error(" 덱공백에러 "); return data[rear]; } 20/33

21 원형덱테스트프로그램 void main() { int i; init_deque( ); for( i=1 ; i<10 ; i++ ) { if( i % 2 ) add_front( i ); else add_rear( i ); } print_queue(" 원형덱홀수 - 짝수 "); printf("\tdelete_front() --> %d\n", delete_front()); printf("\tdelete_rear () --> %d\n", delete_rear ()); printf("\tdelete_front() --> %d\n", delete_front()); print_queue(" 원형덱삭제 - 홀짝홀 "); } 21/33

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

23 큐의응용 : 은행시뮬레이션 입력 : 시뮬레이션할최대시간 ( 예 : 10 [ 단위시간 ]) 단위시간에도착하는고객수 ( 예 : 0.5 [ 고객수 / 단위시간 ]) 한고객에대한최대서비스시간 ( 예 : 5 [ 단위시간 / 고객 ]) 출력 : 고객들의평균대기시간 서비스인원 ( 은행원 ): 1명 고객정보 : 단위시간에도착하는고객수를바탕으로무작위로발생 서비스시간 : 일정한범위내에서무작위로결정 23/33

24 은행시뮬레이션테스트프로그램 typedef struct BankCustomer { int id; // 고객번호 int tarrival; // 도착시간 int tservice; // 서비스에필요한시간 } Customer; typedef Customer Element; int double int int int int... nsimulation; probarrival; tmaxservice; totalwaittime; ncustomers; nservedcustomers; #include <time.h> void main() { srand( (unsigned int)time(null) ); read_sim_params( ); run_simulation(); print_result(); } 24/33

25 실행결과예 시뮬레이션파라미터입력 각단위시간별이벤트출력 시뮬레이션결과출력 25/33

26 덱의응용 : 미로탐색 DFS 깊이우선탐색 (DFS, Depth First Search) 이웃위치탐색순서 typedef struct { int x; int y; } Location2D; 출구 스택 (3,3) (4,3) (4,4) (4,5) (2,2) (2,3) (1,3) (1,3) (1,3) (1,3) (1,0) (1,1) (2,1) (3,1) (3,1) (3,1) (3,1) (3,1) (3,1) 26/33

27 미로탐색 DFS 입구 ( 1, 0) ( 1, 2) ( 1, 1) ( 2, 1) ( 1, 3) ( 2, 1) ( 1, 4) ( 2, 3) ( 2, 1) ( 2, 3) ( 2, 1) 출구 ( 3, 3) ( 2, 1) ( 3, 4) ( 4, 3) ( 2, 1) ( 3, 5) ( 4, 3) ( 2, 1) 27/33

28 int DFS() { int x, y; Location2D here; init_deque( ); add_rear( getlocation2d(0,1) ); printf("dfs: "); while ( is_empty() == 0 ) { here = delete_rear( ); print_elem( here ); x = here.x; y = here.y; if( map[y][x] == 'x' ) return 1; else { map[y][x] = '.'; if( is_valid( x-1, y ) ) add_rear(getlocation2d(x-1,y)); if( is_valid( x+1, y ) ) add_rear(getlocation2d(x+1,y)); if( is_valid( x, y-1 ) ) add_rear(getlocation2d(x,y-1)); if( is_valid( x, y+1 ) ) add_rear(getlocation2d(x,y+1)); } } return 0; } 28/33

29 덱의응용 : 미로탐색 BFS 너비우선탐색 (BFS, Breadth First Search) 삭제 이웃위치탐색순서 큐 (1,0) (1,1) (2,1) (3,1) (2,2) (2,2) (4,1) (4,1) (2,3) (2,3) (1,3) (3,3) (3,3) (1,4) (1,4) (4,3) 출구 (4,3) (4,4) (4,5) 삽입 29/33

30 30/33

31 전역변수와객체지향프로그래밍 전역변수 + 전역함수 좋지않은프로그래밍습관? 하나의큐만사용가능 전역변수를많이사용하면좋지않다는데 왜이책에서는전역변수를많이사용하지? 좋지않은코드일까? 아하! 이런코드가클래스와연결이되는구나! C++ 이나자바처럼객체지향언어도공부하고싶었는데 여러개의큐가필요한경우해결방안? C++: 클래스로전환가능 어렵지않음! C 언어 : 구조체선언및매개변수전달 오히려더복잡함! 31/33

32 C++ 클래스로전환 class Queue { Element data[max_queue_size]; // 요소의배열 int front, rear; public: void init_queue( ) { front = rear = 0; ; } int is_empty( ) { return front == rear;; }... void print_queue(char msg[])... }; void main() { int i; Queue q; q.init_queue( ); for( i=1 ; i<10 ; i++ ) q.enqueue( i ); q.print_queue(" 원형큐 enqueue 9회 "); printf("\tdequeue() --> %d\n", q.dequeue()); printf("\tdequeue() --> %d\n", q.dequeue()); printf("\tdequeue() --> %d\n", q.dequeue()); q.print_queue(" 원형큐 dequeue 3회 "); } 32/33

33 C 구조체선언및매개변수전달 typedef int Element; typedef struct CircularQueue { Element data[max_queue_size]; int front, rear; } Queue; void init_queue(queue *q) { q->front = q->rear = 0; ; } int is_empty(queue *q) { return q->front == q->rear; }... void enqueue( Queue *q, Element val ) Element dequeue( Queue *q )... void main() { int i; Queue q; init_queue( &q ); for( i=1 ; i<10 ; i++ ) enqueue( &q, i ); print_queue(&q, " 선형큐 enqueue 9 회 "); printf("\tdequeue() --> %d\n", dequeue(&q)); printf("\tdequeue() --> %d\n", dequeue(&q)); printf("\tdequeue() --> %d\n", dequeue(&q)); print_queue( &q, " 선형큐 dequeue 3 회 "); } 33/33