Microsoft PowerPoint - ch08_큐 [호환 모드]

Transcription

1 큐 (Queue) 자바로배우는쉬운자료구조

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

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

4 큐 (2) 큐의구조 4

5 큐 (3) 큐의연산 삽입 : enqueue 삭제 : dequeue 스택과큐의연산비교 5

6 큐 (4) 추상자료형큐 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] 6

7 큐 (5) 큐의연산과정 1 공백큐생성 : createqueue(); Q [0] [1] [2] front = rear = -1 2 원소 A 삽입 : enqueue(q, A); Q [0] [1] [2] A front = -1 rear 3 원소 B 삽입 : enqueue(q, B); Q [0] [1] [2] A B front = -1 rear 7

8 큐 (6) 4 원소삭제 : dequeue(q); Q A 5 원소 C 삽입 : enqueue(q, C); 6 원소삭제 : dequeue(q); 7 원소삭제 : dequeue(q); Q Q B Q C [0] [1] [2] A front B rear [0] [1] [2] B front [0] [1] [2] B front C rear C rear [0] [1] [2] C front rear 8

9 큐의구현 큐의구현 선형큐 (Linear Queue) 1차원배열을이용하여구현 원형큐 (Circular Queue) 선형큐의저장공간제한문제를해결 연결큐 (Linked-list Queue) 연결리스트를이용하여구현 9

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

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

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

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

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

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

16 선형큐의구현 (7) 순차자료구조방식으로구현한큐프로그램 001 interface Queue{ 002 boolean isempty(); 003 void enqueue(char item); 004 char dequeue(); 005 void delete(); 006 char peek(); 007 } class ArrayQueue implements Queue{ 010 private int front; 011 private int rear; 012 private int queuesize; 013 private char itemarray[]; public ArrayQueue(int queuesize){ 016 front = -1; 017 rear = -1; [ 예제 5-4] >> 계속 16

17 선형큐의구현 (8) 018 this.queuesize = queuesize; [ 예제 5-4] 019 itemarray = new char[this.queuesize]; 020 } public boolean isempty(){ 023 return (front == rear); 024 } public boolean isfull(){ 027 return (rear == this.queuesize-1); 028 } 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; >> 계속 17

18 선형큐의구현 (9) 036 System.out.println("Inserted Item : " + item); [ 예제 5-4] 037 } 038 } 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 } } public void delete(){ 052 if(isempty()){ 053 System.out.println("Deleting fail! Array Queue is empty!!"); >> 계속 18

19 선형큐의구현 (10) 054 [ 예제 5-4] 055 } 056 else { front; 058 } 059 } 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 } public void printqueue(){ 071 if(isempty()) >> 계속 19

20 선형큐의구현 (11) 072 System.out.printf("Array Queue is empty!! %n %n"); 073 else{ 074 System.out.printf("Array Queue>> "); 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 } } class Ex8_1{ 084 public static void main(string args[]){ 085 int queuesize = 3; 086 char deleteditem; 087 ArrayQueue Q = new ArrayQueue(queueSize); Q.enQueue('A'); [ 예제 5-4] >> 계속 20

21 선형큐의구현 (12) 090 Q.printQueue(); Q.enQueue('B'); 093 Q.printQueue(); deleteditem = Q.deQueue(); 096 if(deleteditem!= 0) 097 System.out.println("deleted Item : " + deleteditem); 098 Q.printQueue(); Q.enQueue('C'); 101 Q.printQueue(); deleteditem = Q.deQueue(); 104 if(deleteditem!= 0) 105 System.out.println("deleted Item : " + deleteditem); 106 Q.printQueue(); 107 [ 예제 5-4] >> 계속 21

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

23 선형큐의구현 (14) 실행결과 23

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

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

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

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

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

29 원형큐의구현 (6) 원형큐의삽입알고리즘 1 rear의값을조정하여삽입할자리를준비 : rear (rear+1) mod n; 2 준비한자리 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] 29

30 원형큐의구현 (7) 원형큐의삭제알고리즘 1front의값을조정하여삭제할자리를준비 2 준비한자리에있는원소 cq[front] 를삭제하여반환 dequeue(cq) if(isempty(cq)) then Queue_Empty(); else { front (front+1) mod n; // ❶ return cq[front]; // ❷ } end dequeue() [ 알고리즘 8-9] delete(cq) if(isempty(q)) then Queue_Empty(); else front (front+1) mod n; end delete() 30

31 원형큐의구현 (8) 원형큐에서의연산과정 1 createqueue(); 2 enqueue(cq, A); [1] [2] rear [1] [2] A [0] [3] front rear [0] front [3] 31

32 원형큐의구현 (9) 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 32

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

34 원형큐의구현 (11) 018 this.queuesize = queuesize; [ 예제 5-4] 019 itemarray = new char[this.queuesize]; 020 } public boolean isempty(){ 023 return (front == rear); 024 } public boolean isfull(){ 027 return (((rear+1) % this.queuesize) == front); 028 } 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; >> 계속 34

35 원형큐의구현 (12) 036 itemarray[rear] = item; [ 예제 5-4] 037 System.out.println("Inserted Item : " + item); 038 } 039 } 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 } } public void delete(){ >> 계속 35

36 원형큐의구현 (13] 054 if(isempty()){ [ 예제 5-4] 055 System.out.println("Deleting fail! Array Circular Queue is empty!!"); } 058 else { 059 front = (front+1) % this.queuesize; 060 } 061 } 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 >> 계속 36

37 원형큐의구현 (14] 072 public void printqueue(){ [ 예제 5-4] 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 } } class Ex8_2{ 087 public static void main(string args[]){ 088 int queuesize = 4; >> 계속 37

38 원형큐의구현 (15) 089 char deleteditem; 090 ArrayCQueue cq = new ArrayCQueue(queueSize); cq.enqueue('a'); 093 cq.printqueue(); cq.enqueue('b'); 096 cq.printqueue(); deleteditem = cq.dequeue(); 099 if(deleteditem!= 0) 100 System.out.println("deleted Item : " + deleteditem); 101 cq.printqueue(); cq.enqueue('c'); 104 cq.printqueue(); cq.enqueue('d'); [ 예제 5-4] >> 계속 38

39 원형큐의구현 (16) 107 cq.printqueue(); cq.enqueue('e'); 110 cq.printqueue(); 111 } 112 } [ 예제 5-4] 실행결과 39

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

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

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

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

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

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

46 연결큐의구현 (7) 연결큐의삭제알고리즘 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() [ 알고리즘 8-13] delete(lq) if(isempty(lq)) then Queue_Empty(); else { old front; front front.link; if(isempty(lq)) then rear null; returnnode(old); } end delete() 46

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

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

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

50 연결큐의구현 (11) 연결큐에서의연산과정 1 공백큐생성 : createlinkedqueue(); 2 원소 A 삽입 : enqueue(lq, A); 3 원소 B 삽입 : enqueue(lq, B); 50

51 연결큐의구현 (12) 4 원소삭제 : dequeue(lq); 5 원소 C 삽입 : enqueue(lq, C); 51

52 연결큐의구현 (13) 6 원소삭제 : dequeue(lq); 7 원소삭제 : dequeue(lq); 52

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

54 연결큐의구현 (15) 018 public LinkedQueue(){ 019 front = null; 020 rear = null; 021 } public boolean isempty(){ 024 return (front == null); 025 } 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] >> 계속 54

55 연결큐의구현 (16) 036 rear.link = newnode; [ 예제 8-3] 037 rear = newnode; 038 } 039 System.out.println("Inserted Item : " + item); 040 } 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 } >> 계속 55

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

57 연결큐의구현 (18) 072 } 073 else 074 return front.data; 075 } 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] >> 계속 57

58 연결큐의구현 (19) 090 } class Ex8_3{ 093 public static void main(string args[]){ 094 char deleteditem; 095 LinkedQueue LQ = new LinkedQueue(); LQ.enQueue('A'); 098 LQ.printQueue(); LQ.enQueue('B'); 101 LQ.printQueue(); deleteditem = LQ.deQueue(); 104 if(deleteditem!= 0) 105 System.out.println("deleted Item : " + deleteditem); 106 LQ.printQueue(); 107 [ 예제 8-3] >> 계속 58

59 연결큐의구현 (20) 108 LQ.enQueue('C'); 109 LQ.printQueue(); deleteditem = LQ.deQueue(); 112 if(deleteditem!= 0) 113 System.out.println("deleted Item : " + deleteditem); 114 LQ.printQueue(); deleteditem = LQ.deQueue(); 117 if(deleteditem!= 0) 118 System.out.println("deleted Item : " + deleteditem); 119 LQ.printQueue(); deleteditem = LQ.deQueue(); 122 if(deleteditem!= 0) 123 System.out.println("deleted Item : " + deleteditem); 124 LQ.printQueue(); 125 } 126 } [ 예제 8-3] 59

60 연결큐의구현 (21) 실행결과 60

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

62 덱 (Deque) (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 }; [ADT 8-2] 62

63 덱 (Deque) (3) // 덱의 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] 63

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

65 덱 (Deque) (5) 5 deletefront(dq); B front DQ A C rear 6 deleterear(dq); DQ A C front rear 7 insertrear(dq, 'D'); DQ A D front rear 8 insertfront(dq, 'E'); DQ E A D front rear 65

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

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

68 덱의구현 (2) 018 } 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] >> 계속 68

69 덱의구현 (3) 036 } 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] >> 계속 69

70 덱의구현 (4) 054 } [ 예제 8-4] 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; >> 계속 70

71 덱의구현 (5) 072 } [ 예제 8-4] 073 } 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 } >> 계속 71

72 덱의구현 (6) 090 return item; [ 예제 8-4] 091 } 092 } 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 } >> 계속 72

73 덱의구현 (7) 108 } [ 예제 8-4] 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 >> 계속 73

74 덱의구현 (8) 126 public char peekfront(){ [ 예제 8-4] 127 if(isempty()){ 128 System.out.println("Front Peeking fail! DQueue is empty!!"); 129 return 0; 130 } 131 else 132 return front.data; 133 } 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 >> 계속 74

75 덱의구현 (9) 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 } class Ex8_4{ 160 public static void main(string args[]){ 161 char deleteditem; [ 예제 8-4] >> 계속 75

76 덱의구현 (10) 162 DQueue DQ = new DQueue(); [ 예제 8-4] DQ.insertFront('A'); 165 DQ.printDQueue(); DQ.insertFront('B'); 168 DQ.printDQueue(); DQ.insertRear('C'); 171 DQ.printDQueue(); deleteditem = DQ.deleteFront(); 174 if(deleteditem!= 0) 175 System.out.println("Front deleted Item : " + deleteditem); 176 DQ.printDQueue(); deleteditem = DQ.deleteRear(); 179 if(deleteditem!= 0) >> 계속 76

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

78 덱의구현 (12) 실행결과 78

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

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

81 자바로배우는쉬운자료구조