Deque(Double-ended Queue)

데큐는 큐의 양쪽 끝에서 삽입과 삭제가 모두 발생할 수 있는 큐로서 스택의 설질과 큐의  성질 모두 가지고 있는 자료조

 - 덱의 insertFront() 연산과 deleteFront()연산은 front를 스택에 top으로 생각했을 때 스택의 push()연산과, pop()연산과 같다.

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

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

연산 수행에 대한 덱의 상태

public class DQNode {
   char data;
   DQNode rlink;
   DQNode llink;
}

public class DQueue {
   DQNode front;
   DQNode rear;

   public DQueue() {
      front = null;
      rear = null;
   }

   public boolean isEmpty() {
      return (front == null);
   }

   public void insertFront(char item) {
      DQNode newNode = new DQNode();
      newNode.data = item;

      if (isEmpty()) {
         front = newNode;
         rear = newNode;
         newNode.rlink = null;
         newNode.llink = null;
      } else {
         front.llink = newNode;
         newNode.rlink = front;
         newNode.llink = null;
         front = newNode;
      }
      System.out.println("Front Inster Item " + item);
   }

   public void insertRear(char item) {
      DQNode newNode = new DQNode();
      newNode.data = item;

      if (isEmpty()) {
         front = newNode;
         rear = newNode;
         newNode.rlink = null;
         newNode.llink = null;
      } else {
         rear.rlink = newNode;
         newNode.rlink = null;
         newNode.llink = rear;
         rear = newNode;
      }

      System.out.println("Rear Insert Item" + item);
   }

   public char deleteFornt() {
      if (isEmpty()) {
         System.out.println("Front Removing Fail!! DQueue is empty!!" );
         return 0;
      }

      char data = front.data;

      if (front.rlink == null) {
         front = null;
         rear = null;
      } else {
         front = front.rlink;
         front.llink = null;
      }

      return data;
   }

   public char deleteRear() {
      if (isEmpty()) {
         System.out.println("Rear Removing Fail!! DQueue is empty!!" );
         return 0;
      }

      char data = rear.data;

      if (rear.llink == null) {
         rear = null;
         front = null;
      } else {
         rear = rear.llink;
         rear.rlink = null;
      }

      return data;
   }



   public void removeFornt() {
      if (isEmpty()) {
         System.out.println("Front Removing Fail!! DQueue is empty!!" );
         return;
      }

      if (front.rlink == null) {
         front = null;
         rear = null;
      } else {
         front = front.rlink;
         front.llink = null;
      }

   }

   public void removeRear() {
      if (isEmpty()) {
         System.out.println("Rear Removing Fail!! DQueue is empty!!" );
         return;
      }

      if (rear.llink == null) {
         rear = null;
         front = null;
      } else {
         rear = rear.llink;
         rear.rlink = null;
      }
   }


   public char peekFront() {
      if (isEmpty()) {
         System.out.println("Front Peeking Fail!! DQueue is empty!!" );
         return 0;
      }

      return front.data;
   }

   public char peekRear() {
      if (isEmpty()) {
         System.out.println("Rear Peeking Fail!! DQueue is empty!!" );
         return 0;
      }

      return front.data;
   }

   public void printDQueue() {
      if (isEmpty()) {
         System.out.println("DQueu is Empty.");
      } else {
         DQNode temp = front;
         System.out.print("DQUEUE>>");

         while (temp != null) {
            System.out.printf("%C", temp.data);
            temp = temp.rlink;
         }

         System.out.println();
         System.out.println();
      }
   }

   public static void main(String[] args) {
      char deleteItem;
      DQueue deque = new DQueue();
      deque.insertFront('A');
      deque.printDQueue();

      deque.insertFront('B');
      deque.printDQueue();

      deque.insertRear('C');
      deque.printDQueue();

      deleteItem = deque.deleteFornt();
      System.out.println("Front delete Item" + deleteItem);
      deque.printDQueue();

      deleteItem = deque.deleteRear();
      System.out.println("Rear delete Item" + deleteItem);
      deque.printDQueue();

      deque.insertRear('D');
      deque.printDQueue();

      deque.insertFront('E');
      deque.printDQueue();

      deque.insertFront('F');
      deque.printDQueue();

      deque.insertFront('G');
      deque.printDQueue();

   }
}