Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74

Transcription

1 큐 IT CookBook, C 로배우는쉬운자료구조 ( 개정판 )

2 Contents v 학습목표 자료구조큐에대한개념을스택과비교하여이해한다. 큐의특징과연산방법에대해알아본다. 순차표현방법을이용한큐와연결표현방법을이용한큐를구현해본다. 큐의응용방법을알아본다. v 내용 큐 큐의구현 큐의응용 2/74

3 1. 큐 v 큐 (Queue) 데이터의삽입과삭제가양쪽끝에서일어나는자료구조 삽입은 rear 에서, 삭제는 front 에서됨 순서대로처리해야하는자료를임시적으로저장하는용도로사용 배열또는연결리스트로구현함 v 큐 = 대기열 극장에들어가기위해서도착한순서대로줄을서있다가앞에서부터입장하는줄서기 3/74

4 1. 큐 v 용어 front : 가장먼저저장된데이터 rear : 마지막에저장된데이터 v FIFO(First In First Out) : 선입선출구조 삽입된순서대로일을처리해주는구조 4/74

5 1. 큐 v 큐의연산 enqueue : rear 로데이터를삽입하는작업 dequeue : front 로데이터를삭제하는작업 5/74

6 v 추상자료형큐 큐에대한자료형과연산을추상화하여다음과같이정의할수있다. ADT Queue 데이터 : 0개이상의원소를가진유한순서리스트연산 : Q Queue; item Element; // 새로운큐만들기 createqueue() = create an empty Q; // 큐의 rear 에새로운데이터삽입하기 enqueue(q, item) = insert item at the rear of Q; // 현재큐가비어있는지확인하기 isempty(q) = if (Q is empty) then return true else return false; // 큐의 front 에있는데이터를삭제하고가져오기 dequeue(q) = if (isempty(q)) then return error else { delete and return the front item of Q }; // 큐의 front 에있는데이터를삭제하기 delete(q) = if (isempty(q)) then return error else { delete the front item of Q }; End Queue // 큐의 front 에있는데이터를읽기 peek(q) = if (isempty(q)) then return error else { return the front item of the Q }; 6/74

7 v 큐의연산과정 추상자료형에서정의한연산을이용하여큐의생성과삽입 / 삭제연산 과정을살펴보자. 1 큐생성 :createqueue(); Q [0] [1] [2] front = rear = -1 2 A 삽입 : enqueue(q, A); Q front = -1 [0] [1] [2] A rear 3 B 삽입 : enqueue(q, B); Q A [0] [1] [2] B front = -1 rear 7/74

8 v 큐의연산과정 4 삭제 : dequeue(q); Q A [0] [1] [2] A B front rear 5 C 삽입 : enqueue(q, C); Q [0] [1] [2] B C front rear 6 삭제 : dequeue(q); Q B [0] [1] [2] B C front rear 7 삭제 : dequeue(q); Q C [0] [1] [2] C front rear 8/74

9 2. 큐의구현 - 순차자료구조를이용한큐의구현 v 1 차원배열을이용한큐의구현 큐의크기 = 배열의크기 변수 front : 저장된첫번째원소의인덱스저장 변수 rear : 저장된마지막원소의인덱스저장 v 상태표현 초기상태 : front = rear = -1 공백상태 : front = rear 포화상태 : rear = n-1 (n: 배열의크기, n-1: 배열의마지막인덱스 ) 9/74

10 2. 큐의구현 - 순차자료구조를이용한큐의구현 v 초기공백큐생성알고리즘 크기가 n 인 1 차원배열생성 front 와 rear 를 -1 로초기화 10/74

11 2. 큐의구현 - 순차자료구조를이용한큐의구현 v 공백큐검사알고리즘과포화상태검사알고리즘 공백상태 : front = rear 포화상태 : rear = n-1 (n : 배열의크기, n-1 : 배열의마지막인덱스 ) 11/74

12 2. 큐의구현 - 순차자료구조를이용한큐의구현 v 큐의삽입알고리즘 마지막원소의뒤에삽입해야하므로 1 마지막원소의인덱스를저장한 rear 의값을하나증가시켜삽입할자리준비 2 그인덱스에해당하는배열원소 Q[rear] 에 item 을저장 12/74

13 2. 큐의구현 - 순차자료구조를이용한큐의구현 v 큐의삭제알고리즘 가장앞에있는원소를삭제해야하므로 1 front 의위치를한자리뒤로이동하여큐에남아있는첫번째원소의위치로이동하여삭제할자리준비 2 그자리의원소를삭제하여반환 13/74

14 2. 큐의구현 - 순차자료구조를이용한큐의구현 v 큐의검색알고리즘 가장앞에있는원소를검색하여반환하는연산 1 현재 front 의한자리뒤 (front+1) 에있는원소, 즉큐에있는첫번째원소를반환 14/74

15 2. 큐의구현 - 순차자료구조를이용한큐의구현 v 순차자료구조로구현한큐의 C 프로그램 01 #include <stdio.h> 02 #include <stdlib.h> 03 #define Q_SIZE typedef char element; //char형을큐 element의자료형으로정의 06 typedef struct{ 07 element queue[q_size]; // 1차원배열큐선언 08 int front, rear; 09 } QueueType; QueueType *createqueue() // 공백큐를생성하는연산 12 { 13 QueueType *Q; 14 Q = (QueueType *)malloc(sizeof(queuetype)); 15 Q->front=-1; // front 초기값설정 16 Q->rear=-1; // rear 초기값설정 17 return Q; 18 } 15/74

16 2. 큐의구현 - 순차자료구조를이용한큐의구현 int isempty(queuetype *Q) // 큐가공백인지확인하는연산 21 { 22 if (Q->front == Q->rear) { 23 printf("\n Queue is empty! \n"); 24 return 1; 25 } 26 else return 0; 27 } int isfull(queuetype *Q) // 큐가포화상태인지확인하는연산 30 { 31 if (Q->rear == Q_SIZE-1) { 32 printf("\n Queue is full! \n"); 33 return 1; 34 } 35 else return 0; 36 } 37 16/74

17 2. 큐의구현 - 순차자료구조를이용한큐의구현 38 void enqueue(queuetype *Q, element item) // 큐의 rear 에원소를삽입하는연산 39 { 40 if(isfull(q)) exit(1); 41 else { 42 Q->rear++; 43 Q->queue[Q->rear] = item; 44 } 45 } element dequeue(queuetype *Q) // 큐의 front 에서원소를삭제하고반환하는연산 48 { 49 if (isempty(q)) exit(1); 50 else { 51 Q->front++; 52 return Q->queue[Q->front]; 53 } 54 } 55 17/74

18 2. 큐의구현 - 순차자료구조를이용한큐의구현 56 void del(queuetype *Q) // 큐의 front 에서원소를삭제하는연산 57 { 58 if (isempty(q)) exit(1); 59 else Q->front++; 60 } element peek(queuetype *Q) // 큐의가장앞에있는원소를검색하여반환하는연산 63 { 64 if (isempty(q)) exit(1); 65 else return Q->queue[Q->front+1]; 66 } void printq(queuetype *Q) // 큐의내용을출력하는연산 69 { 70 int i; 71 printf(" Queue : ["); 72 for(i=q->front+1; i<=q->rear; i++) 73 printf("%3c", Q->queue[i]); 74 printf(" ] \n"); 75 } 18/74

19 2. 큐의구현 - 순차자료구조를이용한큐의구현 void main(void) 78 { 79 QueueType *Q1 = createqueue(); 80 element data; 81 printf(" 삽입 A>>"); enqueue(q1, 'A'); printq(q1); 82 printf(" 삽입 B>>"); enqueue(q1, 'B'); printq(q1); 83 printf(" 삭제 >>"); dequeue(q1); printq(q1); 84 printf(" 삽입 C>>"); enqueue(q1, 'C'); printq(q1); 85 data = peek(q1); printf(" peek item : %c \n", data); 86 printf(" 삭제 >>"); dequeue(q1); printq(q1); 87 printf(" 삭제 >>"); dequeue(q1); printq(q1); getchar(); 90 } 19/74

20 2. 큐의구현 - 순차자료구조를이용한큐의구현 실행결과 > 20/74

21 2. 큐의구현 - 원형큐 v 선형큐의잘못된포화상태인식 큐에서삽입과삭제를반복하면서아래와같은상태일경우, 앞부분에빈자리가있지만 rear=n-1 상태이므로포화상태로인식하고더이상의삽입을수행하지않는다. v 선형큐의잘못된포화상태인식의해결방법 -1 저장된원소들을배열의앞부분으로이동시키기 순차자료에서의이동작업은연산이복잡하여효율성이떨어짐 21/74

22 2. 큐의구현 - 원형큐 v 선형큐의잘못된포화상태인식의해결방법 -2 1차원배열을사용하면서논리적으로배열의처음과끝이연결되어있다고가정하고사용 원형큐 v 원형큐의논리적구조 22/74

23 2. 큐의구현 - 원형큐 v 원형큐의구조 초기공백상태 : front = rear = 0 front 와 rear 의위치가배열의마지막인덱스 n-1 에서논리적인다음자리인인덱스 0 번으로이동하기위해서나머지연산자 mod 를사용 3 4 = 0 3 ( 몫 =0, 나머지 =3) 3 mod 4 = 3 삽입위치 삭제위치 선형큐 rear = rear + 1 front = front + 1 원형큐 rear = (rear+1) mod n front = (front+1) + mod n 사용조건 공백상태와포화상태구분을쉽게하기위해서 front 가있는자리는사용하지않고항상빈자리로둔다. 23/74

24 2. 큐의구현 - 원형큐 v 초기공백원형큐생성알고리즘 크기가 n 인 1 차원배열생성 front 와 rear 를 0 으로초기화 24/74

25 2. 큐의구현 - 원형큐 v 원형큐의공백상태와포화상태검사알고리즘 공백상태 : front = rear 포화상태 : 삽입할 rear의다음위치 = front의현재위치 (rear+1) mod n = front 25/74

26 2. 큐의구현 - 원형큐 v 원형큐의삽입알고리즘 1 rear의값을조정하여삽입할자리를준비 : rear (rear+1) mod n; 2 준비한자리 cq[rear] 에원소 item을삽입 26/74

27 2. 큐의구현 - 원형큐 v 원형큐의삭제알고리즘 1 front의값을조정하여삭제할자리를준비 2 준비한자리에있는원소 cq[front] 를삭제하여반환 27/74

28 2. 큐의구현 - 원형큐 v 원형큐에서의연산과정 1 createqueue(); 2 enqueue(cq, A); rear [1] [2] [1] [2] A [0] [3] [0] [3] front rear front 28/74

29 2. 큐의구현 - 원형큐 3 enqueue(cq, B); rear 4 dequeue(cq); front rear [1] [2] A B [1] [2] A B [0] [3] [0] [3] front 5 enqueue(cq, C); front 6 enqueue(cq, D); front [1] [2] B [1] [2] B [0] C [3] [0] D C [3] rear rear 29/74

30 2. 큐의구현 - 순차자료구조로구현한원형큐프로그램 v 순차자료구조로구현한원형큐의 C 프로그램 001 #include <stdio.h> 002 #include <stdlib.h> 003 #define cq_size //char형을큐 element의자료형으로정의 005 typedef char element; 006 typedef struct{ 007 element queue[cq_size]; // 1차원배열큐선언 008 int front, rear; 009 } cqueuetype; cqueuetype *createqueue() 013 { 014 cqueuetype *cq; 015 cq = (cqueuetype *)malloc(sizeof(cqueuetype)); 016 cq->front=0; // 원형큐의 front 초기값설정 017 cq->rear=0; // 원형큐의 rear 초기값설정 018 return cq; 019 } /74

31 2. 큐의구현 - 순차자료구조로구현한원형큐프로그램 021 int isempty(cqueuetype *cq) // 원형큐가공백인지확인하는연산 022 { 023 if (cq->front == cq->rear) { 024 printf("\n Circular Queue is empty! \n"); 025 return 1; 026 } 027 else return 0; 028 } int isfull(cqueuetype *cq) // 원형큐가포화상태인지확인하는연산 031 { 032 if (((cq->rear + 1) % cq_size) == cq->front) { 033 printf("\n Circular Queue is full! \n"); 034 return 1; 035 } 036 else return 0; 037 } /74

32 2. 큐의구현 - 순차자료구조로구현한원형큐프로그램 039 void enqueue(cqueuetype *cq, element item) // 원형큐의 rear 에원소를삽입하는연산 040 { 041 if(isfull(cq)) exit(1); 042 else { 043 cq->rear = (cq->rear + 1) % cq_size; 044 cq->queue[cq->rear] = item; 045 } 046 } element dequeue(cqueuetype *cq) // 원형큐의 front 에서원소를삭제하고반환하는연산 050 { 051 if (isempty(cq)) exit(1); 052 else { 053 cq->front = (cq->front + 1) % cq_size; 054 return cq->queue[cq->front]; 055 } 056 } /74

33 2. 큐의구현 - 순차자료구조로구현한원형큐프로그램 058 void del(cqueuetype *cq) // 원형큐의 front에서원소를삭제하는연산 059 { 060 if (isempty(cq)) exit(1); 061 else cq->front = (cq->front + 1) % cq_size; 062 } // 원형큐의가장앞에있는원소를검색하여반환하는연산 065 element peek(cqueuetype *cq) 066 { 067 if (isempty(cq)) exit(1); 068 else return cq->queue[(cq->front+1) % cq_size]; 069 } /74

34 2. 큐의구현 - 순차자료구조로구현한원형큐프로그램 071 // 원형큐의내용을출력하는연산 072 void printq(cqueuetype *cq) 073 { 074 int i, first, last; 075 first = (cq->front+1) % cq_size; 076 last = (cq->rear+1) % cq_size; 077 printf(" Circular Queue : ["); 078 i=first; 079 while(i!=last) { 080 printf("%3c",cq->queue[i]); 081 i = (i+1) % cq_size; 082 } 083 printf(" ] \n"); 084 } /74

35 2. 큐의구현 - 순차자료구조로구현한원형큐프로그램 087 void main(void) 088 { 089 cqueuetype *cq1 = createqueue(); 090 element data; 091 printf(" 삽입 A>>"); enqueue(cq1, 'A'); printq(cq1); 092 printf(" 삽입 B>>"); enqueue(cq1, 'B'); printq(cq1); 093 printf(" 삭제 >>"); dequeue(cq1); printq(cq1); 094 printf(" 삽입 C>>"); enqueue(cq1, 'C'); printq(cq1); 095 data = peek(cq1); printf(" peek item : %c \n", data); 096 printf(" 삽입 D>>"); enqueue(cq1, 'D'); printq(cq1); 097 printf(" 삽입 E>>"); enqueue(cq1, 'E'); printq(cq1); getchar(); 100 } 35/74

36 2. 큐의구현 - 순차자료구조로구현한원형큐프로그램 실행결과 > 36/74

37 2. 큐의구현 - 연결자료구조를이용한큐의구현 v 단순연결리스트를이용한큐 큐의원소 : 단순연결리스트의노드 원소순서 : 노드의링크포인터로연결 변수 front: 첫번째노드를가리키는포인터변수 변수 rear : 마지막노드를가리키는포인터변수 v 상태표현 초기상태와공백상태 : front = rear = null v 연결큐의구조 37/74

38 2. 큐의구현 - 연결자료구조를이용한큐의구현 v 초기공백연결큐생성알고리즘 초기화 : front = rear = null 38/74

39 2. 큐의구현 - 연결자료구조를이용한큐의구현 v 공백연결큐검사알고리즘 공백상태 : front = rear = null 39/74

40 2. 큐의구현 - 연결자료구조를이용한큐의구현 v 연결큐의삽입알고리즘 40/74

41 2. 큐의구현 - 연결자료구조를이용한큐의구현 1 삽입할새노드를생성하여데이터필드에 item 을저장한다. 삽입할새노드는연결큐의마지막노드가되어야하므로링크필드에 null 을저장한다. 2 새노드를삽입하기전에연결큐가공백인지아닌지를검사한다. 연결큐가공백인경우에는삽입할새노드가큐의첫번째노드이자마지막노드이므로 포인터 front 와 rear 가모두새노드를가리키도록설정한다. 41/74

42 2. 큐의구현 - 연결자료구조를이용한큐의구현 3 큐가공백이아닌경우, 즉노드가있는경우에는 현재큐의마지막노드의뒤에새노드를삽입하고 마지막노드를가리키는 rear 가삽입한새노드를가리키도록설정한다. 42/74

43 2. 큐의구현 - 연결자료구조를이용한큐의구현 v 연결큐삭제알고리즘 43/74

44 2. 큐의구현 - 연결자료구조를이용한큐의구현 1 삭제연산에서삭제할노드는큐의첫번째노드로서포인터 front 가가리키고있는노드이 다. front 가가리키는노드를포인터 old 가가리키게하여삭제할노드를지정한다. 2 삭제연산후에는현재 front 노드의다음노드가 front 노드 ( 첫번째노드 ) 가되어야하므로, 포인터 front 를재설정한다. 44/74

45 2. 큐의구현 - 연결자료구조를이용한큐의구현 3 현재큐에노드가하나뿐이어서삭제연산후에공백큐가되는경우 : 큐의마지막노드가없어지므로포인터 rear 를 null 로설정한다. 4 포인터 old 가가리키고있는노드를삭제하고, 메모리공간을시스템에반환 (returnnode()) 한다 45/74

46 2. 큐의구현 - 연결자료구조를이용한큐의구현 v 연결큐의검색알고리즘 연결큐의첫번째노드, 즉 front 노드의데이터필드값을반환 46/74

47 2. 큐의구현 - 연결자료구조를이용한큐의구현 v 연산을수행하는동안연결큐의상태 1 공백큐생성 : createlinkedqueue(); null front null rear 2 원소 A 삽입 : enqueue(lq, A); 3 원소 B 삽입 : enqueue(lq, B); 100 번지 100 번지 200 번지 A null A 200 B null front rear 100 front 200 rear 47/74

48 2. 큐의구현 - 연결자료구조를이용한큐의구현 4 원소삭제 : dequeue(lq); 200 번지 B null front rear 5 원소 C 삽입 : enqueue(lq, C); 200 번지 300 번지 B 300 C null 200 front 300 rear 48/74

49 2. 큐의구현 - 연결자료구조를이용한큐의구현 6 원소삭제 : dequeue(lq); 300 번지 C null front rear 7 원소삭제 : dequeue(lq); null front null rear 49/74

50 2. 큐의구현 - 연결자료구조로구현한연결큐프로그램 v 연결자료구조로구현한연결큐의 C 프로그램 001 #include <stdio.h> 002 #include <malloc.h> typedef char element; // char 형을연결큐 element 의자료형으로정의 005 typedef struct QNode{ // 연결큐의노드를구조체로정의 006 element data; 007 struct QNode *link; 008 } QNode; typedef struct{ // 연결큐에서사용하는포인터 front 와 rear 를구조체로정의 011 QNode *front, *rear; 012 } LQueueType; LQueueType *createlinkedqueue() // 공백연결큐생성연산 015 { 016 LQueueType *LQ; 017 LQ = (LQueueType *)malloc(sizeof(lqueuetype)); 018 LQ->front=NULL; 019 LQ->rear=NULL; 020 return LQ; 021 } /74

51 2. 큐의구현 - 연결자료구조를이용한큐의구현 023 int isempty(lqueuetype *LQ) // 연결큐가공백인지확인하는연산 024 { 025 if (LQ->front == NULL) { 026 printf("\n Linked Queue is empty! \n"); 027 return 1; 028 } 029 else return 0; 030 } void enqueue(lqueuetype *LQ, element item) // 연결큐의 rear에원소를삽입하는연산 033 { 034 QNode *newnode=(qnode *)malloc(sizeof(qnode)); 035 newnode->data = item; 036 newnode->link = NULL; 037 if(lq->front == NULL) { // 현재연결큐가공백인경우 038 LQ->front = newnode; } 041 else { // 현재연결큐가공백이아닌경우 042 LQ->rear->link = newnode; 043 LQ->rear = newnode; 044 } 045 } 51/74

52 2. 큐의구현 - 연결자료구조를이용한큐의구현 047 element dequeue(lqueuetype *LQ) // 연결큐에서 front 원소를삭제하고반환하는연산 048 { 049 QNode *old = LQ->front; 050 element item; 051 if (isempty(lq)) return 0; 052 else { 053 item = old->data; 054 LQ->front = LQ->front->link; 055 if(lq->front == NULL) 056 LQ->rear = NULL; 057 free(old); 058 return item; 059 } 060 } /74

53 2. 큐의구현 - 연결자료구조를이용한큐의구현 062 int del(lqueuetype *LQ) // 연결큐에서 front 원소를삭제하는연산 063 { 064 QNode *old = LQ->front; 065 if (isempty(lq)) return 0; 066 else { 067 LQ->front = LQ->front->link; 068 if(lq->front == NULL) 069 LQ->rear = NULL; 070 free(old); 071 return 1; 072 } 073 } element peek(lqueuetype *LQ) // 연결큐에서 front 원소를검색하여반환하는연산 076 { 077 element item; 078 if (isempty(lq)) return 0; 079 else { 080 item = LQ->front->data; 081 return item; 082 } 083 } /74

54 2. 큐의구현 - 연결자료구조를이용한큐의구현 085 void printlq(lqueuetype *LQ) // 연결큐를출력하는연산 086 { 087 QNode *temp = LQ->front; 088 printf(" Linked Queue : ["); 089 while(temp) { 090 printf("%3c", temp->data); 091 temp = temp->link; 092 } 093 printf(" ] \n"); 094 } void main(void) 097 { 098 LQueueType *LQ1 = createlinkedqueue(); 099 element data; 100 printf(" 삽입 A>>"); enqueue(lq1, 'A'); printlq(lq1); 101 printf(" 삽입 B>>"); enqueue(lq1, 'B'); printlq(lq1); 102 printf(" 삭제 >>"); dequeue(lq1); printlq(lq1); 103 printf(" 삽입 C>>"); enqueue(lq1, 'C'); printlq(lq1); 104 data = peek(lq1); printf(" peek item : %c \n", data); 105 printf(" 삽입 D>>"); enqueue(lq1, 'D'); printlq(lq1); 106 printf(" 삽입 E>>"); enqueue(lq1, 'E'); printlq(lq1); getchar(); 109 } 54/74

55 2. 큐의구현 - 연결자료구조를이용한큐의구현 실행결과 > 55/74

56 Queue-2 2. 덱 v 덱 (Deque, double-ended queue) 큐 2 개를반대로붙여서만든자료구조 Queue-1 삭제 삽입 Þ 삽입 삭제 삽입 삭제 Deque 삽입 삭제 front 저장된원소중에서가장앞부분원소 rear 저장된원소중에서가장뒷부분원소 56/74

57 2. 덱 덱에대한추상자료형 ADT deque 데이터 : 0 개이상의원소를가진유한순서리스트연산 : DQ deque; item Element; createdeque() = create an empty DQ; // 공백덱을생성하는연산 isempty(dq) = if (DQ is empty) then return true else return false; // 덱이공백인지아닌지를확인하는연산 insertfront(dq, item) = insert item at the front of DQ; // 덱의 front 앞에 item( 원소 ) 을삽입하는연산 insertrear(dq, item) = insert item at the rear of DQ; // 덱의 rear 뒤에 item( 원소 ) 을삽입하는연산 deletefront(dq) = if (isempty(dq)) then return null else { delete and return the front item of DQ }; // 덱의 front 에있는 item( 원소 ) 을덱에서삭제하고반환하는연산 deleterear(dq) = if (isempty(dq)) then return null else { delete and return the rear item of DQ }; // 덱의 rear 에있는 item( 원소 ) 을덱에서삭제하고반환하는연산 57/74

58 2. 덱 덱에대한추상자료형 End deque removefront(dq) = if (isempty(dq)) then return null else { remove the front item of DQ }; // 덱의 front 에있는 item( 원소 ) 을삭제하는연산 removerear(dq) = if (isempty(dq)) then return null else { remove the rear item of DQ }; // 덱의 rear 에있는 item( 원소 ) 을삭제하는연산 getfront(dq) = if (isempty(dq)) then return null else { return the front item of the DQ }; // 덱의 front 에있는 item( 원소 ) 을반환하는연산 getrear(dq) = if (isempty(dq)) then return null else { return the rear item of the DQ }; // 덱의 rear 에있는 item( 원소 ) 을반환하는연산 58/74

59 2. 덱 덱에서의연산과정 1 createdeque(); DQ 2 insertfront(dq, 'A'); 3 insertfront(dq, 'B'); 4 insertrear(dq, 'C'); front DQ front DQ front A B A rear rear rear DQ front B A C rear 59/74

60 2. 덱 5 deletefront(dq); B DQ front A C rear 6 deleterear(dq); DQ A C 7 insertrear(dq, 'D'); front rear DQ 8 insertfront(dq, 'E'); front A D rear DQ front E A D rear 60/74

61 2. 덱 9 insertfront(dq, 'F'); front F E A D rear 덱의구현 양쪽끝에서삽입 / 삭제연산을수행하면서크기변화와저장된원소의순서변화가많으므로순차자료구조는비효율적 양방향으로연산이가능한이중연결리스트를사용한다. llink null data rlink llink data rlink llink data rlink null front rear 61/74

62 2. 덱 - 이중연결리스트를이용한덱프로그램 v 이중연결리스트를이용한덱의 C 프로그램 001 #include <stdio.h> 002 #include <malloc.h> typedef char element; // char 형을덱 element 의자료형으로정의 005 typedef struct DQNode{ // 이중연결리스트덱의노드구조를구조체로정의 006 element data; 007 struct DQNode *llink; 008 struct DQNode *rlink; 009 } DQNode; typedef struct{ // 덱에서사용하는포인터 front 와 rear 를구조체로정의 012 DQNode *front, *rear; 013 } DQueType; DQueType *createdque() // 공백덱을생성하는연산 016 { 017 DQueType *DQ; 018 DQ = (DQueType *)malloc(sizeof(dquetype)); 019 DQ->front=NULL; 020 DQ->rear=NULL; 021 return DQ; 022 } /74

63 2. 덱 - 이중연결리스트를이용한덱프로그램 024 int isempty(dquetype *DQ) // 덱이공백인지확인하는연산 025 { 026 if (DQ->front == NULL) { 027 printf("\n Linked Queue is empty! \n"); 028 return 1; 029 } 030 else return 0; 031 } void insertfront(dquetype *DQ, element item) // 덱의 front 앞으로삽입하는연산 034 { 035 DQNode *newnode=(dqnode *)malloc(sizeof(dqnode)); 036 newnode->data = item; 037 if(dq->front == NULL) { // 덱이공백인경우 038 DQ->front = newnode; 039 DQ->rear = newnode; 040 newnode->rlink = NULL; 041 newnode->llink = NULL; 042 } 043 else { // 덱이공백이아닌경우 044 DQ->front->llink = newnode; 045 newnode->rlink = DQ->front; 046 newnode->llink = NULL; 047 DQ->front = newnode; 048 } 049 } 63/74

64 2. 덱 - 이중연결리스트를이용한덱프로그램 051 void insertrear(dquetype *DQ, element item) // 덱의 rear 뒤로삽입하는연산 052 { 053 DQNode *newnode=(dqnode *)malloc(sizeof(dqnode)); 054 newnode->data = item; 055 if(dq->rear == NULL) { // 덱이공백인경우 056 DQ->front = newnode; 057 DQ->rear = newnode; 058 newnode->rlink = NULL; 059 newnode->llink = NULL; 060 } 061 else { // 덱이공백이아닌경우 062 DQ->rear->rlink = newnode; 063 newnode->rlink = NULL; 064 newnode->llink = DQ->rear; 065 DQ->rear = newnode; 066 } 067 } /74

65 2. 덱 - 이중연결리스트를이용한덱프로그램 069 element deletefront(dquetype *DQ) // 덱의 front 노드를삭제하고반환하는연산 070 { 071 DQNode *old = DQ->front; 072 element item; 073 if (isempty(dq)) return 0; 074 else { 075 item = old->data; 076 if(dq->front->rlink == NULL) { 077 DQ->front = NULL; 078 DQ->rear = NULL; 079 } 080 else { 081 DQ->front = DQ->front->rlink; 082 DQ->front->llink = NULL; 083 } 084 free(old); 085 return item; 086 } 087 } /74

66 2. 덱 - 이중연결리스트를이용한덱프로그램 089 element deleterear(dquetype *DQ) // 덱의 rear 노드를삭제하고반환하는연산 090 { 091 DQNode *old = DQ->rear; 092 element item; 093 if (isempty(dq)) return 0; 094 else { 095 item = old->data; 096 if(dq->rear->llink == NULL) { 097 DQ->front = NULL; 098 DQ->rear = NULL; 099 } 100 else { 101 DQ->rear = DQ->rear->llink; 102 DQ->rear->rlink = NULL; 103 } 104 free(old); 105 return item; 106 } 107 } /74

67 2. 덱 - 이중연결리스트를이용한덱프로그램 109 int removefront(dquetype *DQ) // 덱의 front 노드를삭제하는연산 110 { 111 DQNode *old = DQ->front; 112 if (isempty(dq)) return 0; 113 else if(dq->front->rlink == NULL) { 114 DQ->front = NULL; 115 DQ->rear = NULL; 116 } 117 else { 118 DQ->front = DQ->front->rlink; 119 DQ->front->llink = NULL; 120 } 121 free(old); return 1; 122 } /74

68 2. 덱 - 이중연결리스트를이용한덱프로그램 124 int removerear(dquetype *DQ) // 덱의 rear 노드를삭제하는연산 125 { 126 DQNode *old = DQ->rear; 127 if (isempty(dq)) return 0; 128 else if(dq->rear->llink == NULL) { 129 DQ->front = NULL; 130 DQ->rear = NULL; 131 } 132 else { 133 DQ->rear = DQ->rear->llink; 134 DQ->rear->rlink = NULL; 135 } 136 free(old); return 1; 137 } element peekfront(dquetype *DQ) // 덱의 front 노드의데이터필드를반환하는연산 140 { 141 element item; 142 if (isempty(dq)) return 0; 143 else { 144 item = DQ->front->data; 145 return item; 146 } 147 } /74

69 2. 덱 - 이중연결리스트를이용한덱프로그램 149 element peekrear(dquetype *DQ) // 덱의 rear 노드의데이터필드를반환하는연산 150 { 151 element item; 152 if (isempty(dq)) return 0; 153 else { 154 item = DQ->rear->data; 155 return item; 156 } 157 } void printdq(dquetype *DQ) // 덱의 front 노드부터 rear 노드까지출력하는연산 160 { 161 DQNode *temp = DQ->front; 162 printf("deque : ["); 163 while(temp) { 164 printf("%3c", temp->data); 165 temp = temp->rlink; 166 } 167 printf(" ] \n"); 168 } /74

70 2. 덱 - 이중연결리스트를이용한덱프로그램 170 void main(void) 171 { 172 DQueType *DQ1 = createdque(); 173 element data; 174 printf("front 삽입 A>> "); insertfront(dq1, 'A'); printdq(dq1); 175 printf("front 삽입 B>> "); insertfront(dq1, 'B'); printdq(dq1); 176 printf("rear 삽입 C>> "); insertrear(dq1, 'C'); printdq(dq1); 177 printf("front 삭제 >> "); deletefront(dq1); printdq(dq1); 178 printf("rear 삭제 >> "); deleterear(dq1); printdq(dq1); 179 printf("rear 삽입 D>> "); insertrear(dq1, 'D'); printdq(dq1); 180 printf("front 삽입 E>> "); insertfront(dq1, 'E'); printdq(dq1); 181 printf("front 삽입 F>> "); insertfront(dq1, 'F'); printdq(dq1); data = peekfront(dq1); printf("peek Front item : %c \n", data); 184 data = peekrear(dq1); printf("peek Rear item : %c \n", data); getchar(); 187 } 70/74

71 2. 덱 - 이중연결리스트를이용한덱프로그램 실행결과 > 71/74

72 3. 큐의응용 v 운영체제의작업큐 프린터버퍼큐 CPU에서프린터로보낸데이터순서대로 ( 선입선출 ) 프린터에서출력하기위해서선입선출구조의큐사용 스케줄링큐 CPU 사용을요청한프로세서들의순서를스케줄링하기위해서큐를사용 v 시뮬레이션큐잉시스템 시뮬레이션을위한수학적모델링에서대기행렬과대기시간등을 모델링하기위해서큐잉이론 (Queue theory) 사용 72/74