[자료구조] 원형 큐(Circular Queue) 설명 및 구현

1. 원형 큐

1차원 배열을 사용한 순차 자료구조 방식에서는 큐가 포화 상태가 아닐 경우에만 삽입 연산을 할 수 있었습니다. 하지만 앞에 빈자리가 있음에도 불구하고 rear가 배열의 마지막 인덱스와 값이 같다면 포화 상태로 인식하여 삽입 연산을 수행하지 못하였습니다. 이를 잘못된 포화상태라고 부릅니다.

 

이런 경우에 큐의 빈자리를 사용하기 위해 저장되어 있는 원소를 배열의 앞부분으로 이동시켜 위치를 조정해 줘도 되지만 이는 큐의 효율성을 떨어트립니다. 따라서 이러한 선형 큐의 잘못된 포화상태 문제를 해결하기 위해 원형 큐를 사용합니다.

 

원형 큐는 선형 큐와 마찬가지로 1차원 배열로 구현하지만, 논리적으로 배열의 처음과 끝이 연결되어 있는 것으로 생각하는 것입니다.

2. 원형 큐 알고리즘

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

 

원형 큐에서는 공백 상태와 포화 상태의 구분을 쉽게 하기 위해서 front가 있는 자리는 사용하지 않고 항상 빈자리로 둡니다.

· 원형 큐 생성

createCircularQueue()
    cQ[n];
    front ← 0;
    rear ← 0;
end createCircularQueue()

새로 생성한 공백의 원형 큐는 front와 rear의 초기값으로 0을 설정합니다.

· 공백 상태 검사

isEmpty(cQ)
    if(front = rear) then return true;
    else return false;
end isEmpty()

원형 큐에서 공백 상태가 되는 경우는 처음 원형 큐를 생성한 경우와 마지막에 삽입한 rear의 원소를 삭제하여 front가 rear의 위치에 있는 경우입니다.

· 포화 상태 검사

isFull(cQ)
    if((rear + 1) mod n) = front) then return true;
    else return false;
end isFull()

원형 큐에 모든 원소를 채우고 rear의 다음 위치((rear + 1) mod n)가 현재의 front 위치와 같다면 더 이상 원소를 삽입할 수 없는 포화 상태가 됩니다.

· 삽입 알고리즘

enQueue(cQ, item)
    if(ifFull()) then full();
    else{
        rear ← (rear + 1) mod n;
        cQ[rear] ← item;
    }
end enQueue()

원형 큐에서 다음 인덱스를 정하기 위해서 나머지 연산자 mod를 사용합니다.

 

예를 들어 크기가 5인 원형 큐에서 현재 rear의 위치가 3이라면 (3 + 1) mod 5 = 4이 되어 cQ[4]이 되고

 

현재 위치가 4이라면 (4 + 1) mod 5 = 0이 되어 다음 삽입할 인덱스의 위치는 cQ[0]이 됩니다.

 

따라서 mod 연산자를 통해 1차원 배열을 마치 논리적으로 배열의 처음과 끝이 연결되어 있는 것처럼 구현할 수 있습니다.

· 삭제 알고리즘

deQueue(cQ)
	if(isEmpty()) then empty();
    else{
        front ← (front + 1) mod n;
        return cQ[front];
    }
end deQueue()

삽입 연산과 마찬가지로 mod 연산자를 사용하여 다음 인덱스를 정합니다.

 

예를 들어 크기가 5인 원형 큐에서 현재 rear의 위치가 0이고 front의 위치가 3이라면 (3 + 1) mod 5 = 4이 되어 cQ[4] 위치의 원소를 삭제합니다.

 

현재 인덱스의 위치 4에서 다음 인덱스의 원소를 삭제하기 위해 (4 + 1) mod 5 = 0이 되어 cQ[0] 위치의 원소를 삭제합니다.

 

따라서 rear와 front의 값이 0으로 같아 원형 큐는 공백상태가 됩니다.

3. 원형 큐 구현

· Queue

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

 

· ArrayCircularQueue

public class CircularQueue implements Queue {
	private int front;
	private int rear;
	private int queueSize;
	private char[] queue;

	// 연결 큐 초기화
	public CircularQueue(int queueSize) {
		this.front = 0;
		this.rear = 0;
		this.queueSize = queueSize;
		this.queue = new char[this.queueSize];
	}

	@Override
	public boolean isEmpty() {
		return (front == rear); // front와 rear가 0인 경우와 마지막에 삽입한 rear의 원소를 삭제하여 front가 rear의 위치에 있을 경우 공백상태
	}

	public boolean isFull() {
		return ((rear + 1) % this.queueSize == front); // (rear + 1) % 스택 사이즈 값과 front 값이 같으면 포화상태
	}

	@Override
	public void enQueue(char data) {
		if (isFull()) {
			System.out.println("원형 큐가 포화상태입니다.");
		} else {
			rear = (rear + 1) % this.queueSize; // rear의 값을 1 증가
			queue[rear] = data;
		}
	}

	@Override
	public char deQueue() {
		if (isEmpty()) {
			System.out.println("원형 큐가 공백상태입니다.");
			return 0;
		} else {
			front = (front + 1) % this.queueSize; // front의 값을 1 증가
			return queue[front];
		}
	}

	@Override
	public char peek() {
		if (isEmpty()) {
			System.out.println("원형 큐가 공백상태입니다.");
			return 0;
		} else {
			return queue[(front + 1) % this.queueSize]; // 가장 먼저 들어온 값 반환
		}
	}

	@Override
	public void delete() {
		if (isEmpty()) {
			System.out.println("원형 큐가 공백상태입니다.");
		} else {
			front = (front + 1) % this.queueSize; // front의 값을 1 증가
		}
	}

	// 원형 큐 출력
	public void printQueue() {
		if (isEmpty()) {
			System.out.println("원형 큐가 공백상태입니다.");
		} else {
			System.out.printf("Q = ");
			for (int i = (front + 1) % this.queueSize; i != (rear + 1) % this.queueSize; i = ++i % this.queueSize) {
				System.out.printf("%c ", queue[i]);
			}
			System.out.println("\n");
		}
	}
}

 

· MainForCircularQueue

public class MainForCircularQueue {
	public static void main(String[] args) {
		CircularQueue q = new CircularQueue(5);
		char data = 0;

		System.out.println("1. 원형 큐에 원소 4개 삽입하기");
		for (char c = 'A'; c <= 'D'; c++) {
			q.enQueue(c);
		}
		q.printQueue();

		System.out.println("2. 가장 먼저 들어온 값 반환하기");
		data = q.peek();
		System.out.printf("%c\n\n", data);

		System.out.println("3. 원형 큐의 원소 3개 디큐");
		for (int i = 0; i < 3; i++) {
			data = q.deQueue();
			System.out.printf("삭제된 원소: %c\n", data);
			q.printQueue();
		}

		System.out.println("4. 원형 큐에 원소 2개 삽입하기");
		for (char c = 'E'; c <= 'F'; c++) {
			q.enQueue(c);
		}
		q.printQueue();

		System.out.println("5. 원형 큐 원소 1개 삭제하기");
		q.delete();
		q.printQueue();
	}
}

 

· 실행 결과