[자료구조/java] 덱 (Deque) - 연결 자료구조 방식 구현

* 덱 (Deque)

"큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐로서, 큐와 스택의 성질을 모두 가지고 있는 자료구조이다."

따라서, 덱의 insertFront(), deleteFront() 연산은 Front 를 top으로 생각했을 때 스택의 push(), pop() 연산과 같고,

insertRear(), deleteRear() 연산은 rear를 스택의 top으로 생각했을 때 스택의 push(), pop() 연산과 같다.

그리고 덱의 insertRear(), deleteFront() 연산은 일반 큐의 enQueue(), deQueue() 연산과 같다. 

DequeNode.java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

package Deque;   public class DequeNode {     char data;     DequeNode llink;     DequeNode rlink;          public DequeNode() {         this.llink = null;         this.rlink = null;     }          public DequeNode(char data) {         this.data = data;         this.llink = null;         this.rlink = null;     } }

Deque.java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138

package Deque;   public class Deque {     DequeNode front;     DequeNode rear;          public Deque() {         front = null;         rear = null;     }          public boolean isEmpty(){         return (front==null);     }          public void insertFront(char item){         DequeNode node = new DequeNode(item);         if(isEmpty()){             front = node;             rear = node;             node.rlink = null;             node.llink = null;         }else{             node.rlink = front;             node.llink = null;             front.llink = node;             front = node;         }     }          public char deleteFront(){         if(isEmpty()){             System.out.println("덱이 비어있습니다.");             return 0;         }else{             char data = front.data;             if(front.rlink==null){                 front = null;                 rear = null;             }else{                 front = front.rlink;                 front.llink = null;             }             return data;         }     }          public void insertRear(char item){         DequeNode node =  new DequeNode(item);         if(isEmpty()){             front = node;             rear = node;             node.rlink = null;             node.llink = null;         }else{             node.llink = rear;             node.rlink = null;             rear.rlink = node;             rear = node;         }     }          public char deleteRear(){         if(isEmpty()){             System.out.println("덱이 비어있습니다.");             return 0;         }else{             char data = rear.data;             if(rear.llink==null){                 front = null;                 rear = null;             }else{                 rear = rear.llink;                 rear.rlink = null;             }             return data;         }     }          public void removeFront(){         if(isEmpty()){             System.out.println("덱이 비어있습니다.");         }else{             if(front.rlink==null){                 front = null;                 rear = null;             }else{                 front = front.rlink;                 front.llink = null;             }         }     }          public void removeRear(){         if(isEmpty()){             System.out.println("덱이 비어있습니다.");         }else{             if(rear.llink==null){                 front = null;                 rear = null;             }else{                 rear = rear.llink;                 rear.rlink = null;             }         }     }          public char peekRear(){         if(isEmpty()){             System.out.println("덱이 비어있습니다.");             return 0;         }else{             return rear.data;         }     }          public char peekFront(){         if(isEmpty()){             System.out.println("덱이 비어있습니다.");             return 0;         }else{             return front.data;         }     }          public void print(){         if(isEmpty()){             System.out.println("덱이 비어있습니다.");         }else{             DequeNode node = front;             while(node!=null){                 System.out.print(node.data + " ");                 node = node.rlink;             }             System.out.println();         }     } }

DequeTest.java

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38

package Deque;   public class DequeTest {     public static void main(String[] args) {         char deletedItem;         Deque DQ = new Deque();                  DQ.insertFront('A');         DQ.print();                  DQ.insertFront('B');         DQ.print();                  DQ.insertRear('C');         DQ.print();                  deletedItem = DQ.deleteFront();         if(deletedItem != 0){             System.out.println("Front deleted Item : " + deletedItem);         }         DQ.print();                  deletedItem = DQ.deleteRear();         if(deletedItem != 0){             System.out.println("Front deleted Item : " + deletedItem);         }         DQ.print();                  DQ.insertRear('D');         DQ.print();                  DQ.insertFront('E');         DQ.print();                  DQ.insertFront('F');         DQ.print();     } }