원형 큐

선형 큐의 문제점

 

 -  rear가 배열의 마지막 위치에 있을때 앞에 빈자리가 있는 경우에도 포화 상태로 인식하고 삽입 연산을 하지 않는다.   큐의 빈자리를 사용하려면  앞으로 이동시켜 위치를 조정시켜야 하는데 복잡하여 큐의 효율성을 떨어뜨린다.

 

이런 문제를 해결하기 위해 원형 큐(Circular Queue)를 사용한다.

 

 

초기 공백 상태일때는 front와 rear 값이 0이 되고, 공백 상태와 포화 상태를 쉽게 구분하기 위해서 자리 하나를 항상 비워둠.

원형큐의 공백 조건 상태는 front=rear가 된다

rear는 앞으로 이동하면서 원소를 삽입하고 front는 rear가 이동한 방향으로 따라가면서 원소를 삭제

배열의 인덱스가 n-1 다음에 다시 0이 되어야 하므로 사용할 다음 인덱스를 정하기 위해서 나머지 연산자 mod를 사용

 

 

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

 

 

 

 

public class CicularQueue implements Queue{
   private int front;
   private int rear;
   private int queueSize;
   private char itemArray[];

   public CicularQueue(int queueSize) {
      front = 0;
      rear = 0;
      this.queueSize = queueSize;
      itemArray = new char[this.queueSize];
   }

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

   public boolean isFull() {
      return ((rear + 1) % this.queueSize) == front;
   }

   @Override
   public void enQueue(char item) {
      if (isFull()) {
         System.out.println("Inserting fail. Queue is full");
         return;
      }

      rear = (rear + 1) % this.queueSize;
      itemArray[rear] = item;
      System.out.println("Insert Item : " + item);

   }

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

      front = (front + 1) % this.queueSize;
      return itemArray[front];
   }

   @Override
   public void delete() {
      if (isEmpty()) {
         System.out.println("Deleting faile. Queue is Empty.");
         return;
      }

      front = (front +1) % this.queueSize;
   }

   @Override
   public char peek() {
      if (isEmpty()) {
         System.out.println("Peeking fail. Queue is Empty.");
         return 0;
      }

      return itemArray[(front + 1) % this.queueSize];
   }

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

      System.out.print("Array Circular Queue>> ");

      for(int i=(front + 1) % this.queueSize; i != (rear + 1) % this.queueSize; i=++i % this.queueSize) {
         System.out.printf("%c", itemArray[i]);
      }
      System.out.println();
      System.out.println();
   }

 

public static void main(String[] args) {
   CicularQueue Q = new CicularQueue(4);

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

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

   System.out.println("delete item" + Q.deQueue());
   Q.printQueue();

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

   Q.enQueue('D');
   Q.printQueue();

   Q.enQueue('E');
   Q.printQueue();

}

 

 

결과

 

 

 

 

1. front 와 rear 초기값으로 0을 설정

2. 공백상태가 되는 경우는 front와 rear가 항상 같이있는 상태이다.

3. (rear + 1) mod n 은 현재의 front 위치가 되어 더이상 원소를 삽입할 수 없는 포화 상태이다.

4. 삽입 연산은 rear 의 값을 조정하여 삽입할 자리를 준비하고 준비한 자리 cQ[rear]에 원소 item을 삽입, 원형 큐에 삽입할 자리를 정하기 위해 mod를 사용

 

현재 rear의 위치가 2라면 (2 + 1) mod 4 = 3 이 되어 다음 삽입할 위치는 cQ[3]이 된다

현재 rear의 위치가 3라면 (3 + 1) mod 4 = 0 이 되어 다음 삽입할 위치는 cQ[0]이 된다.

 

5. 삭제 연산은 front의 값을 조정하여 삭제할 자리를 준비하고 준비한 자리에 있는 원소 cQ[front] 를 삭제 하여 반환

 

 

원형 큐의 연산과정

 

1. CreateQueue();                           2. enQueue(A);

3. enQueue(B);                           4. deQueue(A);

 

5. enQueue(C);                                                    6. enQueue(D);