[자료 구조] Circular Queue

동적 배열을 사용한 큐에서는 배열의 가장 앞에서부터 데이터를 꺼내오기 때문에, 데이터를 꺼낸 후 그 다음 인덱스의 데이터들을 모두 한 칸씩 이동시켜줘야 한다는 문제가 있다. 이 과정은 자료 하나를 꺼낼 때마다 O(n)의 시간 복잡도를 요구하기 때문에 매우 비효율적이다. 이런 단점을 보완한 것이 원형 큐(circular queue)이다. 원형 큐는 영어로 'ring buffer'라고도 부른다. 원형 큐는 배열의 맨 앞과 뒤를 이어붙인 큐의 구조를 가진다. 그리고 enqueue, dequeue 시 rear, front 포인터의 위치를 처음과 끝 데이터에 맞게 유동적으로 변경한다.

아래와 같은 형태로 enqueue, dequeue를 구현함으로써 동적 배열로 구현한 큐의 문제점을 원형 큐가 극복할 수 있다.

Enqueue

rear의 포인터를 1 증가시키고 그 자리에 데이터를 삽입한다. 만약 (rear + 1)%capacity가 front와 같지 않다면 포화상태가 아니라고 판단하여 (rear + 1)%capacity에 데이터를 삽입한다. 배열의 포화상태 여부를 판단하기 위해 배열의 1칸은 비워두고, (rear + 1)%capacity가 front와 같다면 배열이 포화상태인 것으로 판단하여 데이터 삽입이 이루어지지 않는다.

Dequeue
front의 포인터를 1 증가시키고 그 위치의 데이터를 배열에서 꺼내 사용한다. rear이 front와 같다면 배열이 공백상태인 것으로 판단하여 dequeue가 실행되지 않는다.

원형 큐 데이터 입출력 과정 단계 별 설명

step 1.

먼저 rear과 front가 0의 인덱스에서 시작한다. 현재 상태에서 rear과 front가 같기 때문에 배열이 공백상태인 것으로 판단하여 dequeue는 실행되지 않는다.

step 2.

첫번째 데이터에 대해 enqueue 연산이 실행된 모습이다. (rear+1)%capacity가 front와 다르기 때문에 포화상태가 아니라고 판단하여 enqueue 연산이 실행되었다.

step 3.

두번째 데이터에 대해 enqueue 연산이 실행된 모습이다. 마찬가지로 포화상태가 아니기에 euqueue 연산이 정상적으로 실행되었다.

step 4.

세번째 데이터에 대해 enqueue 연산이 실행된 모습이다. 이 시점부터는 (rear + 1)%capacity(4)가 front와 같기 때문에 enqueue가 실행되지 않는다.

step 5.

첫번째 데이터에 대해 dequeue가 실행된 모습이다. rear과 front가 다르기 때문에 공백 상태가 아니라고 판단하여 dequeue 연산이 실행되며, (front+1)%capacity(4) 위치에 있는 첫번째 데이터를 꺼내온다.

step 6.

두번째 데이터에 대해 dequeue가 실행된 모습이다. 마찬가지로 공백 상태가 아니기에 dequeue 연산이 정상적으로 실행되었다.

step 7.

세번째 데이터에 대해 dequeue가 실행된 모습이다. 이 시점부터는 rear와 front가 같기 때문에 공백 상태라고 판단하여 dequeue 연산이 실행되지 않는다.

자바로 원형 큐 구현하기

public class Circular_Queue {
    
    int rear = 0;            
    int front = 0;            
    int maxsize = 0;        
    int[] circular_Queue;         
    
    public Circular_Queue(int maxsize) {
        this.maxsize = maxsize;
        circular_Queue = new int[this.maxsize];
    }
    
    public boolean isEmpty() {
        if(rear == front) {
            return true;
        }
        return false;
    }
    public boolean isFull() {
        if((rear+1)%maxsize == front) {
            return true;
        }
        return false;
    }
    
    public void enQueue(int num) {
        if(isFull()) {
            System.out.println("큐가 가득 찼습니다");
        }
        else {
            rear = (rear+1) % maxsize;
            circular_Queue[rear]=num;
        }
    }
    
    public int deQueue() {
          if(isEmpty()) {
              return -1;
          }
          else {
              front = (front+1)%maxsize;
              return circular_Queue[front];
          }
      }
}