연결큐

순차 자료구조 방식에는 몇가지 문제가 있다.

 - 사용 크기가 제한되어 있어서 큐의 길이를 마음대로 변경할 수 없다.

 - 원소가 없을 때에도 항상 처음 크기를 유지하고 있어야 하므로 메모리도 낭비 된다.

연결큐의 알고리즘

1. 공백 연결 큐 생성

createLinkedQueue()

   fornt <- null;

   rear <- null;

end createLinkedQueue()   

 - 삽입할 새 노드를 생성하여 데이터 필드에 item을 저장.

 - 삽입할 새 노드는 연결 큐의 마지막 노드가 되어야 하므로 링크 필드에 null을 저장

2. 공백 연결 큐 검사

isEmpty(LQ)

if(front=null) then return true;

else return false;

end isEmpty()

 

- 새 노드를 삽입하기 전 연결 큐가 공백인지 검사

- 연결 큐가 공백인 경우에 삽입할 새 노드가 큐의 첫 번째 노드이자 마지막 노드이므로 참조변수 front와 rear가 모두 새 노드를 가리키도록 설정

3. 연결 큐의 삽입 알고리즘

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()

 - 큐가 공백이 아닌경우 현재 큐의 마지막 노드의 뒤에 새 노드를 삽입

 - 마지막 노드를 가리키는 rear 가 삽입한 새노드를 가리키게 한다.

4. 연결 큐의 삭제 알고리즘

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)

if(isEmpty(LQ) then Queue_Empty();

else {

old <- front;

front <- front.link;

if (isEmpty(LQ) then rear <- null;

returnNode(old);

}

end delete()

- 삭제할 노드는 front가 가리키고 있는 첫 번째 노드

- front가 가리키는 노드를 참보변수 old가 가리키게 하여 삭제할 노드 지정

 - 삭제 연산 후에는 현재 front 노드의 다음 노드가 front가 되어야 하므로 front를  그 다음 노드(front.link)로 재설정

 

 

 - 현재 큐에 노드가 하나뿐이어서 재설정한 fornt가 null이 되는 경우에는 삭제 연산 후에 공백 큐가 될 것이므로 rear 를 null로 설정

 - old가 가리키고 있는 노드를 삭제하여 메모리 공간을 시스템에 반환 

5. 연결 큐의 검색 알고리즘

peek(LQ)

if(isEmpty(LQ)) then Queue_Empty()

else return (front,data);

end peek()

 - 큐에서 검색 연산은 항상 큐의 첫번째 노드, 즉 front 노드의 데이터 필드 값을 반환

소스 

public interface Queue {
   boolean isEmpty();
   void enQueue(char item);
   char deQueue();
   void delete();
   char peek();
}

public class LinkedQueue implements Queue {
   private QNode front;
   private QNode rear;

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

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

   @Override
   public void enQueue(char item) {
      QNode newNode = new QNode();
      newNode.data = item;
      newNode.link = null;

      if (isEmpty()) {
         front = newNode;
         rear = newNode;
      } else {
         rear.link = newNode;
         rear = newNode;
      }

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

   @Override
   public char deQueue() {
      if (isEmpty()) {
         System.out.println("Deleteing fail.");
         return 0;
      }

      char item = front.data;
      front = front.link;

      if (front == null) {
         rear = null;
      }

      return item;
   }

   @Override
   public void delete() {
      if (isEmpty()) {
         System.out.println("Deleting fail!");
      }

      front = front.link;

      if (front == null) {
         rear = null;
      }
   }

   @Override
   public char peek() {
      if (isEmpty()) {
         System.out.println("Peeking Fail!");
         return 0;
      }

      return front.data;
   }

   public void printQueue() {
      if (isEmpty()) {
         System.out.println("Linked Queue is Empty.");
      }

      QNode temp = front;
      System.out.printf("Linked Queue>> ");

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

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

   public static void main(String[] args) {
      char deletedItem;
      LinkedQueue lq = new LinkedQueue();

      lq.enQueue('A');
      lq.printQueue();

      lq.enQueue('B');
      lq.printQueue();

      deletedItem = lq.deQueue();

      if (deletedItem != 0){
         System.out.println("delete Item : " + deletedItem);
      }

      lq.printQueue();

      lq.enQueue('C');
      lq.printQueue();

      deletedItem = lq.deQueue();

      if (deletedItem != 0){
         System.out.println("delete Item : " + deletedItem);
      }

      lq.printQueue();

      deletedItem = lq.deQueue();

      if (deletedItem != 0){
         System.out.println("delete Item : " + deletedItem);
      }

      lq.printQueue();

      deletedItem = lq.deQueue();

      if (deletedItem != 0){
         System.out.println("delete Item : " + deletedItem);
      }

      lq.printQueue();

   }

public class QNode {
   char data;
   QNode link;
}