8 큐

이 장에서 다룰 내용 큐 1 큐의 구현 2 큐의 응용 3

큐 큐(Queue) 스택과 마찬가지로 삽입과 삭제의 위치가 제한된 유한 순서 리스트 큐의 뒤에서는 삽입만 하고, 앞에서는 삭제만 할 수 있는 구조 삽입한 순서대로 원소가 나열되어 가장 먼저 삽입(First-In)한 원소는 맨 앞에 있다가 가장 먼저 삭제(First-Out)된다. ☞ 선입선출 구조 (FIFO, First-In-First-Out) 스택과 큐의 구조 비교

큐 큐의 구조

큐 큐의 연산 삽입 : enQueue 삭제 : deQueue 스택과 큐의 연산 비교

큐 추상 자료형 큐 ADT Queue 데이터 : 0개 이상의 원소를 가진 유한 순서 리스트 연산 : Q∈Queue; item∈Element; createQueue() ∷= create an empty Q; // 공백 큐를 생성하는 연산 isEmpty(Q) ∷= if (Q is empty) then return true else return false; // 큐가 공백인지 아닌지를 확인하는 연산 enQueue(Q, item) ∷= insert item at the rear of Q; // 큐의 rear에 item(원소)을 삽입하는 연산 deQueue(Q) ∷= if (isEmpty(Q)) then return error else { delete and return the front itemof Q }; // 큐의 front에 있는 item(원소)을 큐에서 삭제하고 반환하는 연산 delete(Q) ∷= if (isEmpty(Q)) then return error else { delete the front item of Q }; // 큐의 front에 있는 item(원소)을 삭제하는 연산 peek(Q) ∷= if (isEmpty(Q)) then return error else { return the front item of the Q }; // 큐의 front에 있는 item(원소)을 반환하는 연산 End Queue [ADT 8-1]

큐 A B 큐의 연산 과정 공백 큐 생성 : createQueue(); 원소 A 삽입 : enQueue(Q, A); 원소 B 삽입 : enQueue(Q, B); [0] [1] [2] front = rear = -1 Q [0] [1] [2] Q A rear front = -1 [0] [1] [2] Q A B rear front = -1

큐 A C B C 원소 삭제 : deQueue(Q); 원소 C 삽입 : enQueue(Q, C); Q A front rear [0] [1] [2] Q A B A front rear [0] [1] [2] Q B C front rear [0] [1] [2] Q B C B front rear [0] [1] [2] Q C C front rear

큐의 구현 선형 큐 1차원 배열을 이용한 큐 상태 표현 큐의 크기 = 배열의 크기 변수 front : 저장된 첫 번째 원소의 인덱스 저장 변수 rear : 저장된 마지막 원소의 인덱스 저장 상태 표현 초기 상태 : front = rear = -1 공백 상태 : front = rear 포화 상태 : rear = n-1 (n : 배열의 크기, n-1 : 배열의 마지막 인덱스)

큐의 구현 초기 공백 큐 생성 알고리즘 크기가 n인 1차원 배열 생성 front와 rear를 -1로 초기화 초기 공백 큐 생성 알고리즘 크기가 n인 1차원 배열 생성 front와 rear를 -1로 초기화 createQueue() Q[n]; front ← -1; rear ← -1; end createQueue() [알고리즘 8-1]

큐의 구현 공백 큐 검사 알고리즘과 포화상태 검사 알고리즘 공백 상태 : front = rear 포화 상태 : rear = n-1 (n : 배열의 크기, n-1 : 배열의 마지막 인덱스) isEmpty(Q) if(front=rear) then return true; else return false; end isEmpty() isFull(Q) if(rear=n-1) then return true; end isFull() [알고리즘 8-2]

큐의 구현 큐의 삽입 알고리즘 마지막 원소의 뒤에 삽입해야 하므로 ① 마지막 원소의 인덱스를 저장한 rear의 값을 하나 증가시켜 삽입할 자리 준비 ② 그 인덱스에 해당하는 배열원소 Q[rear]에 item을 저장 enQueue(Q, item) if(isFull(Q)) then Queue_Full(); else { rear ← rear+1; // ❶ Q[rear] ← item; // ❷ } end enQueue() [알고리즘 8-3]

큐의 구현 큐의 삭제 알고리즘 가장 앞에 있는 원소를 삭제해야 하므로 ① front의 위치를 한자리 뒤로 이동하여 큐에 남아있는 첫 번째 원소의 위치로 이동하여 삭제할 자리 준비 ② 그 자리의 원소를 삭제하여 반환 deQueue(Q) if(isEmpty(Q)) then Queue_Empty(); else { front ← front+1; // ❶ return Q[front]; // ❷ } end deQueue() delete(Q) else front ← front+1; end delete() [알고리즘 8-4]

큐의 구현 큐의 검색 알고리즘 가장 앞에 있는 원소를 검색하여 반환하는 연산 ① 현재 front의 한자리 뒤(front+1)에 있는 원소, 즉 큐에 있는 첫 번째 원소를 반환 peek(Q) if(isEmpty(Q)) then Queue_Empty(); else return Q[front+1]; end peek() [알고리즘 8-5]

큐의 구현 순차 자료구조 방식으로 구현한 큐 프로그램 001 interface Queue{ 002 boolean isEmpty(); 003 void enQueue(char item); 004 char deQueue(); 005 void delete(); 006 char peek(); 007 } 008 009 class ArrayQueue implements Queue{ 010 private int front; 011 private int rear; 012 private int queueSize; 013 private char itemArray[]; 014 015 public ArrayQueue(int queueSize){ 016 front = -1; 017 rear = -1; [예제 5-4] >> 계속

큐의 구현 018 this.queueSize = queueSize; 019 itemArray = new char[this.queueSize]; 020 } 021 022 public boolean isEmpty(){ 023 return (front == rear); 024 } 025 026 public boolean isFull(){ 027 return (rear == this.queueSize-1); 028 } 029 030 public void enQueue(char item){ 031 if(isFull()){ 032 System.out.println("Inserting fail! Array Queue is full!!"); 033 } 034 else{ 035 itemArray[++rear] = item; [예제 5-4] >> 계속

큐의 구현 036 System.out.println("Inserted Item : " + item); 037 } 038 } 037 } 038 } 039 040 public char deQueue(){ 041 if(isEmpty()) { 042 System.out.println("Deleting fail! Array Queue is empty!!"); 043 return 0; 044 } 045 else{ 046 return itemArray[++front]; 047 } 048 049 } 050 051 public void delete(){ 052 if(isEmpty()){ 053 System.out.println("Deleting fail! Array Queue is empty!!"); [예제 5-4] >> 계속

큐의 구현 054 055 } 056 else { 057 ++front; 058 } 059 } 060 055 } 056 else { 057 ++front; 058 } 059 } 060 061 public char peek(){ 062 if(isEmpty()){ 063 System.out.println("Peeking fail! Array Queue is empty!!"); 064 return 0; 065 } 066 else 067 return itemArray[front+1]; 068 } 069 070 public void printQueue(){ 071 if(isEmpty()) [예제 5-4] >> 계속

큐의 구현 072 System.out.printf("Array Queue is empty!! %n %n"); 073 else{ 075 for(int i=front+1; i<=rear; i++) 076 System.out.printf("%c ", itemArray[i]); 077 System.out.println();System.out.println(); 078 } 079 } 080 081 } 082 083 class Ex8_1{ 084 public static void main(String args[]){ 085 int queueSize = 3; 086 char deletedItem; 087 ArrayQueue Q = new ArrayQueue(queueSize); 088 089 Q.enQueue('A'); [예제 5-4] >> 계속

큐의 구현 090 Q.printQueue(); 091 092 Q.enQueue('B'); 093 Q.printQueue(); 094 095 deletedItem = Q.deQueue(); 096 if(deletedItem != 0) 097 System.out.println("deleted Item : " + deletedItem); 098 Q.printQueue(); 099 100 Q.enQueue('C'); 101 Q.printQueue(); 102 103 deletedItem = Q.deQueue(); 104 if(deletedItem != 0) 105 System.out.println("deleted Item : " + deletedItem); 106 Q.printQueue(); 107 [예제 5-4] >> 계속

큐의 구현 108 deletedItem = Q.deQueue(); 109 if(deletedItem != 0) 110 System.out.println("deleted Item : " + deletedItem); 111 Q.printQueue(); 112 113 deletedItem = Q.deQueue(); 114 if(deletedItem != 0) 115 System.out.println("deleted Item : " + deletedItem); 116 Q.printQueue(); 117 } 118 } [예제 5-4] >> 계속

큐의 구현 실행 결과

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

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

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

큐의 구현 초기 공백 원형 큐 생성 알고리즘 크기가 n인 1차원 배열 생성 front와 rear를 0 으로 초기화 createQueue() cQ[n]; front ← 0; rear ← 0; end createQueue() [알고리즘 8-6]

큐의 구현 원형 큐의 공백상태 검사 알고리즘과 포화상태 검사 알고리즘 공백 상태 : front = rear 포화 상태 : 삽입할 rear의 다음 위치 = front의 현재 위치 (rear+1) mod n = front isEmpty(cQ) if(front=rear) then return true; else return false; end isEmpty() isFull(cQ) if(((rear+1) mod n)=front) then return true; end isFull() [알고리즘 8-7]

큐의 구현 원형 큐의 삽입 알고리즘 ① rear의 값을 조정하여 삽입할 자리를 준비 : rear ← (rear+1) mod n; ② 준비한 자리 cQ[rear]에 원소 item을 삽입 enQueue(cQ, item) if(isFull(cQ)) then Queue_Full(); else { rear ← (rear+1) mod n; // ❶ cQ[rear] ← item; // ❷ } end enQueue() [알고리즘 8-8]

큐의 구현 원형 큐의 삭제 알고리즘 ① front의 값을 조정하여 삭제할 자리를 준비 ② 준비한 자리에 있는 원소 cQ[front]를 삭제하여 반환 deQueue(cQ) if(isEmpty(cQ)) then Queue_Empty(); else { front ← (front+1) mod n; // ❶ return cQ[front]; // ❷ } end deQueue() delete(cQ) if(isEmpty(Q)) then Queue_Empty(); else front ← (front+1) mod n; end delete() [알고리즘 8-9]

큐의 구현 원형 큐에서의 연산 과정 ① createQueue(); ② enQueue(cQ, A); A rear rear [0] [1] [2] [3] rear front rear [1] [2] A [0] [3] front

큐의 구현 ③ enQueue(cQ, B); ④ deQueue(cQ); ⑤ enQueue(cQ, C);                            ⑥ enQueue(cQ, D); rear front rear [1] [2] [1] [2] A B A B [0] [3] [0] [3] front front front [1] [2] B [1] [2] B C D C [0] [3] rear [0] [3] rear

큐의 구현 순차 자료구조 방식으로 구현한 원형 큐 프로그램 001 interface Queue{ 002 boolean isEmpty(); 003 void enQueue(char item); 004 char deQueue(); 005 void delete(); 006 char peek(); 007 } 008 009 class ArrayCQueue implements Queue{ 010 private int front; 011 private int rear; 012 private int queueSize; 013 private char itemArray[]; 014 015 public ArrayCQueue(int queueSize){ 016 front = 0; 017 rear = 0; [예제 5-4] >> 계속

큐의 구현 018 this.queueSize = queueSize; 019 itemArray = new char[this.queueSize]; 020 } 021 022 public boolean isEmpty(){ 023 return (front == rear); 024 } 025 026 public boolean isFull(){ 027 return (((rear+1) % this.queueSize) == front); 028 } 029 030 public void enQueue(char item){ 031 if(isFull()){ 032 System.out.println("Inserting fail! Array Circular Queue is full!!"); 033 } 034 else{ 035 rear = (rear+1) % this.queueSize; [예제 5-4] >> 계속

큐의 구현 036 itemArray[rear] = item; 037 System.out.println("Inserted Item : " + item); 038 } 039 } 040 041 public char deQueue(){ 042 if(isEmpty()) { 043 System.out.println("Deleting fail! Array Circular Queue is empty!!"); 044 return 0; 045 } 046 else{ 047 front = (front+1) % this.queueSize; 048 return itemArray[front]; 049 } 050 051 } 052 053 public void delete(){ [예제 5-4] >> 계속

큐의 구현 054 if(isEmpty()){ 055 System.out.println("Deleting fail! Array Circular Queue is empty!!"); 056 057 } 058 else { 059 front = (front+1) % this.queueSize; 060 } 061 } 062 063 public char peek(){ 064 if(isEmpty()){ 065 System.out.println("Peeking fail! Array Circular Queue is empty!!"); 066 return 0; 067 } 068 else 069 return itemArray[(front+1) % this.queueSize]; 070 } 071 [예제 5-4] >> 계속

큐의 구현 072 public void printQueue(){ 073 if(isEmpty()) 074 System.out.println("Array Circular Queue is empty!!"); 075 else{ 076 System.out.printf("Array Circular Queue>> "); 077 for(int i=(front+1) % this.queueSize; i!=(rear+1)% this.queueSize; i=++i % this.queueSize) 078 System.out.printf("%c ", itemArray[i]); 079 System.out.println(); System.out.println(); 080 } 081 } 082 083 } 084 085 086 class Ex8_2{ 087 public static void main(String args[]){ 088 int queueSize = 4; [예제 5-4] >> 계속

큐의 구현 089 char deletedItem; 090 ArrayCQueue cQ = new ArrayCQueue(queueSize); 091 092 cQ.enQueue('A'); 093 cQ.printQueue(); 094 095 cQ.enQueue('B'); 096 cQ.printQueue(); 097 098 deletedItem = cQ.deQueue(); 099 if(deletedItem != 0) 100 System.out.println("deleted Item : " + deletedItem); 101 cQ.printQueue(); 102 103 cQ.enQueue('C'); 104 cQ.printQueue(); 105 106 cQ.enQueue('D'); [예제 5-4] >> 계속

큐의 구현 실행 결과 107 cQ.printQueue(); 108 109 cQ.enQueue('E'); 111 } 112 } [예제 5-4]

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

큐의 구현 초기 공백 연결 큐 생성 알고리즘 초기화 : front = rear = null createLinkedQueue() front ← null; rear ← null; end createLinkedQueue() [알고리즘 8-10]

큐의 구현 공백 연결 큐 검사 알고리즘 공백 상태 : front = rear = null isEmpty(LQ) if(front=null) then return true; else return false; end isEmpty() [알고리즘 8-11]

큐의 구현 연결 큐의 삽입 알고리즘 enQueue(LQ, item) new ← getNode(); new.data ← item; // ❶ new.link ← null; if (isEmpty(LQ)) then { // ❷ 연결 큐가 공백인 경우 rear ← new; front ← new; } else { // ❸ 연결 큐에 노드가 있는 경우 rear.link ← new; end enQueue() [알고리즘 8-12]

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

큐의 구현 ③ 큐가 공백이 아닌 경우, 즉 노드가 있는 경우에는 현재 큐의 마지막 노 드의 뒤에 새 노드를 삽입하고 마지막 노드를 가리키는 rear가 삽입한 새 노드를 가리키도록 설정한다.

큐의 구현 연결 큐의 삭제 알고리즘 deQueue(LQ) if(isEmpty(LQ)) then Queue_Empty(); else { old ← front; // ❶ item ← front.data; front ← front.link; // ❷ if (isEmpty(LQ)) then rear ← null; // ❸ returnNode(old); // ❹ return item; } end deQueue() delete(LQ) old ← front; front ← front.link; if(isEmpty(LQ)) then rear ← null; returnNode(old); end delete() [알고리즘 8-13]

큐의 구현 ① 삭제연산에서 삭제할 노드는 큐의 첫 번째 노드로서 포인터 front가 가 리키고 있는 노드이다. front가 가리키는 노드를 포인터 old가 가리키게 하여 삭제할 노드를 지정한다. ② 삭제연산 후에는 현재 front 노드의 다음 노드가 front 노드(첫번째 노드) 가 되어야하므로, 포인터 front를 재설정한다.

큐의 구현 ③ 현재 큐에 노드가 하나뿐이어서 삭제연산 후에 공백 큐가 되는 경우 : ☞ 큐의 마지막 노드가 없어지므로 포인터 rear를 null로 설정한다. ④ 포인터 old가 가리키고 있는 노드를 삭제하고, 메모리 공간을 시스템에 반환(returnNode())한다

큐의 구현 연결 큐의 검색 알고리즘 연결 큐의 첫 번째 노드, 즉 front 노드의 데이터 필드 값을 반환 peek(LQ) if(isEmpty(LQ)) then Queue_Empty() else return (front.data); end peek() [알고리즘 8-14]

큐의 구현 연결 큐에서의 연산 과정 ① 공백 큐 생성 : createLinkedQueue(); ② 원소 A 삽입 : enQueue(LQ, A); ③ 원소 B 삽입 : enQueue(LQ, B);

큐의 구현 ④ 원소 삭제 : deQueue(LQ); ⑤ 원소 C 삽입 : enQueue(LQ, C);

큐의 구현 ⑥ 원소 삭제 : deQueue(LQ); ⑦ 원소 삭제 : deQueue(LQ);

큐의 구현 연결 자료구조 방식을 이용하여 구현한 연결 큐 프로그램 001 interface Queue{ 002 boolean isEmpty(); 003 void enQueue(char item); 004 char deQueue(); 005 void delete(); 006 char peek(); 007 } 008 009 class QNode{ 010 char data; 011 QNode link; 012 } 013 014 class LinkedQueue implements Queue{ 015 QNode front; 016 QNode rear; 017 [예제 8-3] >> 계속

큐의 구현 018 public LinkedQueue(){ 019 front = null; 020 rear = null; 021 } 022 023 public boolean isEmpty(){ 024 return (front == null); 025 } 026 027 public void enQueue(char item){ 028 QNode newNode = new QNode(); 029 newNode.data = item; 030 newNode.link = null; 031 if(isEmpty()){ 032 front = newNode; 033 rear = newNode; 034 } 035 else { [예제 8-3] >> 계속

큐의 구현 036 rear.link = newNode; 037 rear = newNode; 038 } 038 } 039 System.out.println("Inserted Item : " + item); 040 } 041 042 public char deQueue(){ 043 if(isEmpty()) { 044 System.out.println("Deleting fail! Linked Queue is empty!!"); 045 return 0; 046 } 047 else{ 048 char item = front.data; 049 front = front.link; 050 if(front == null) 051 rear = null; 052 return item; 053 } [예제 8-3] >> 계속

큐의 구현 054 } 055 056 public void delete(){ 057 if(isEmpty()){ 054 } 055 056 public void delete(){ 057 if(isEmpty()){ 058 System.out.println("Deleting fail! Linked Queue is empty!!"); 059 } 060 061 else { 062 front = front.link; 063 if(front == null) 064 rear = null; 065 } 066 } 067 068 public char peek(){ 069 if(isEmpty()){ 070 System.out.println("Peeking fail! Linked Queue is empty!!"); 071 return 0; [예제 8-3] >> 계속

큐의 구현 072 } 073 else 074 return front.data; 075 } 076 072 } 073 else 074 return front.data; 075 } 076 077 public void printQueue(){ 078 if(isEmpty()) 079 System.out.printf("Linked Queue is empty!! %n %n"); 080 else{ 081 QNode temp = front; 082 System.out.printf("Linked Queue>> "); 083 while(temp != null){ 084 System.out.printf("%c ", temp.data); 085 temp = temp.link; 086 } 087 System.out.println();System.out.println(); 088 } 089 } [예제 8-3] >> 계속

큐의 구현 090 } 091 092 class Ex8_3{ 093 public static void main(String args[]){ 094 char deletedItem; 095 LinkedQueue LQ = new LinkedQueue(); 096 097 LQ.enQueue('A'); 098 LQ.printQueue(); 099 100 LQ.enQueue('B'); 101 LQ.printQueue(); 102 103 deletedItem = LQ.deQueue(); 104 if(deletedItem != 0) 105 System.out.println("deleted Item : " + deletedItem); 106 LQ.printQueue(); 107 [예제 8-3] >> 계속

큐의 구현 108 LQ.enQueue('C'); 109 LQ.printQueue(); 110 111 deletedItem = LQ.deQueue(); 112 if(deletedItem != 0) 113 System.out.println("deleted Item : " + deletedItem); 114 LQ.printQueue(); 115 116 deletedItem = LQ.deQueue(); 117 if(deletedItem != 0) 118 System.out.println("deleted Item : " + deletedItem); 119 LQ.printQueue(); 120 121 deletedItem = LQ.deQueue(); 122 if(deletedItem != 0) 123 System.out.println("deleted Item : " + deletedItem); 124 LQ.printQueue(); 125 } 126 } [예제 8-3]

큐의 구현 실행 결과

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

큐의 구현 덱에 대한 추상 자료형 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 }; [ADT 8-2]

큐의 구현 // 덱의 rear에 있는 item(원소)을 덱에서 삭제하고 반환하는 연산 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(원소)을 삭제하는 연산 peekFront(DQ) ∷= if (isEmpty(DQ)) then return null else { return the front item of the DQ }; // 덱의 front에 있는 item(원소)을 반환하는 연산 peekRear(DQ) ∷= if (isEmpty(DQ)) then return null else { return the rear item of the DQ }; // 덱의 rear에 있는 item(원소)을 반환하는 연산 End deque [ADT 8-2]

덱 덱에서의 연산 과정 ① createDeque(); ② insertFront(DQ, 'A'); ③ insertFront(DQ, 'B'); ④ insertRear(DQ, 'C'); front rear DQ A B C

덱 ⑤ deleteFront(DQ); ⑥ deleteRear(DQ); ⑦ insertRear(DQ, 'D'); ⑧ insertFront(DQ, 'E'); A C front rear DQ B D E

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

덱의 구현 이중 연결 리스트를 이용한 덱 프로그램 001 class DQNode{ 002 char data; 003 DQNode rlink; 004 DQNode llink; 005 } 006 007 class DQueue{ 008 DQNode front; 009 DQNode rear; 010 011 public DQueue(){ 012 front = null; 013 rear = null; 014 } 015 016 public boolean isEmpty(){ 017 return (front == null); [예제 8-4] >> 계속

덱의 구현 018 } 019 020 public void insertFront(char item){ 018 } 019 020 public void insertFront(char item){ 021 DQNode newNode = new DQNode(); 022 newNode.data = item; 023 if(isEmpty()){ 024 front = newNode; 025 rear = newNode; 026 newNode.rlink = null; 027 newNode.llink = null; 028 } 029 else { 030 front.llink = newNode; 031 newNode.rlink = front; 032 newNode.llink = null; 033 front = newNode; 034 } 035 System.out.println("Front Inserted Item : " + item); [예제 8-4] >> 계속

덱의 구현 036 } 037 038 public void insertRear(char item){ 036 } 037 038 public void insertRear(char item){ 039 DQNode newNode = new DQNode(); 040 newNode.data = item; 041 if(isEmpty()){ 042 front = newNode; 043 rear = newNode; 044 newNode.rlink = null; 045 newNode.llink = null; 046 } 047 else { 048 rear.rlink = newNode; 049 newNode.rlink = null; 050 newNode.llink = rear; 051 rear = newNode; 052 } 053 System.out.println("Rear Inserted Item : " + item); [예제 8-4] >> 계속

덱의 구현 054 } 055 056 public char deleteFront(){ 057 if(isEmpty()) { 054 } 055 056 public char deleteFront(){ 057 if(isEmpty()) { 058 System.out.println("Front Deleting fail! Dqueue is empty!!"); 059 return 0; 060 } 061 else{ 062 char item = front.data; 063 if(front.rlink == null){ 064 front = null; 065 rear = null; 066 } 067 else { 068 front = front.rlink; 069 front.llink = null; 070 } 071 return item; [예제 8-4] >> 계속

덱의 구현 072 } 073 } 074 075 public char deleteRear(){ 072 } 073 } 074 075 public char deleteRear(){ 076 if(isEmpty()) { 077 System.out.println("Rear Deleting fail! Dqueue is empty!!"); 078 return 0; 079 } 080 else{ 081 char item = rear.data; 082 if(rear.llink == null){ 083 rear = null; 084 front = null; 085 } 086 else { 087 rear = rear.llink; 088 rear.rlink = null; 089 } [예제 8-4] >> 계속

덱의 구현 090 return item; 091 } 092 } 093 094 public void removeFront(){ 091 } 092 } 093 094 public void removeFront(){ 095 if(isEmpty()) { 096 System.out.println("Front Removing fail! Dqueue is empty!!"); 097 } 098 else{ 099 if(front.rlink == null){ 100 front = null; 101 rear = null; 102 } 103 else { 104 front = front.rlink; 105 front.llink = null; 106 } 107 } [예제 8-4] >> 계속

덱의 구현 108 } 109 110 public void removeRear(){ 111 if(isEmpty()) { 108 } 109 110 public void removeRear(){ 111 if(isEmpty()) { 112 System.out.println("Rear Removing fail! Dqueue is empty!!"); 113 } 114 else{ 115 if(rear.llink == null){ 116 rear = null; 117 front = null; 118 } 119 else { 120 rear = rear.llink; 121 rear.rlink = null; 122 } 123 } 124 } 125 [예제 8-4] >> 계속

덱의 구현 126 public char peekFront(){ 127 if(isEmpty()){ 128 System.out.println("Front Peeking fail! DQueue is empty!!"); 129 return 0; 130 } 131 else 132 return front.data; 133 } 134 135 public char peekRear(){ 136 if(isEmpty()){ 137 System.out.println("Rear Peeking fail! DQueue is empty!!"); 138 return 0; 139 } 140 else 141 return rear.data; 142 } 143 [예제 8-4] >> 계속

덱의 구현 144 public void printDQueue(){ 145 if(isEmpty()) 146 System.out.printf("DQueue is empty!! %n %n"); 147 else{ 148 DQNode temp = front; 149 System.out.printf("DQueue>> "); 150 while(temp != null){ 151 System.out.printf("%c ", temp.data); 152 temp = temp.rlink; 153 } 154 System.out.println(); System.out.println(); 155 } 156 } 157 } 158 159 class Ex8_4{ 160 public static void main(String args[]){ 161 char deletedItem; [예제 8-4] >> 계속

덱의 구현 162 DQueue DQ = new DQueue(); 163 164 DQ.insertFront('A'); 165 DQ.printDQueue(); 166 167 DQ.insertFront('B'); 168 DQ.printDQueue(); 169 170 DQ.insertRear('C'); 171 DQ.printDQueue(); 172 173 deletedItem = DQ.deleteFront(); 174 if(deletedItem != 0) 175 System.out.println("Front deleted Item : " + deletedItem); 176 DQ.printDQueue(); 177 178 deletedItem = DQ.deleteRear(); 179 if(deletedItem != 0) [예제 8-4] >> 계속

덱의 구현 180 System.out.println("Rear deleted Item : " + deletedItem); 181 DQ.printDQueue(); 182 183 DQ.insertRear('D'); 184 DQ.printDQueue(); 185 186 DQ.insertFront('E'); 187 DQ.printDQueue(); 188 189 DQ.insertFront('F'); 190 DQ.printDQueue(); 191 } 192 } [예제 8-4] >> 계속

덱의 구현 실행 결과

큐의 응용 운영체제의 작업 큐 프린터 버퍼 큐 스케줄링 큐 CPU에서 프린터로 보낸 데이터 순서대로(선입선출) 프린터에서 출력하 기 위해서 선입선출 구조의 큐 사용 스케줄링 큐 CPU 사용을 요청한 프로세서들의 순서를 스케줄링하기 위해 큐를 사용

큐의 응용 시뮬레이션 큐잉 시스템 시뮬레이션을 위한 수학적 모델링에서 대기행렬과 대기시간 등을 모델링하기 위해서 큐잉 이론(Queue theory) 사용