[자료구조] 원형 큐 Circular Queue

0. 원형 큐 Circular Queue 란?

 

원형 큐란 선형 큐의 단점을 보완한 자료구조

   => 선형 큐란?

 

데이터의 입력과 출력 순서는 선입선출 (FIFO : Fisrt In First Out)

인큐 (enqueue) : 큐에 데이터를 넣는 작업

디큐 (dequeue) : 큐에서 데이터를 꺼내는 작업

프런트 (front) : 데이터를 꺼내는 쪽

리어 (rear) : 데이터를 넣는 쪽

 

모두 선형 큐랑 같지만,

공간을 낭비하거나 배열 요소를 앞쪽으로 옮기지 않아도 되도록 링 버퍼를 사용하여 구현

   링 버퍼(ring buffer) : 배열의 처음과 끝이 연결되었다고 보는 자료구조. 실제로 연결되어 있지는 않음

 

원형 큐의 enque(), deque()

 

 

 

1. 원형 큐 구현

 

int[] cque : 원형 큐 본체용 배열

int max : 원형 큐 용량. 원형 큐에 저장할 수 있는 최대 데이터 수

int front : 원형 큐에 저장된 데이터의 가장 처음 위치. 다음 dequeue()를 실행할 위치

int rear : 원형 큐에 저장된 데이터의 가장 마지막 위치+1. 다음 enqueue()를 실행할 위치

int num : 현재 원형 큐에 저장되어 있는 데이터 수. front와 rear의 값이 같은 경우 원형 큐가 비어있는지 가득찼는지 구분하기 위해 필요. 원형 큐가 비어있으면 num == 0, 원형 큐가 가득 차 있으면 num == max

 

- CQueue() : 생성자

public CQueue(int capacity) {
	num = front = rear = 0;
	max = capacity;
	try {
		cque = new int[max];
	} catch (OutOfMemoryError e) {
		max = 0;
	}
}

• 매개변수 : 생성할 원형 큐의 용량
• 원형 큐를 생성하면 비어있으므로 num, front, rear는 0
• 매개변수로 전달받은 capacity를 원형 큐 용량을 나타내는 max에 복사
• 요소 수가 max인 배열 cque 생성
• try-catch문을 사용하여 원형 큐 본체 생성에 실패할 경우, max를 0으로 설정하여 다른 메서드가 존재하지 않는 배열에 잘못 접근하는 것을 막음

 

 

- enque() : 원형 큐에 데이터를 인큐

public int enque(int x) throws OverFlowQueueException {
	if(num >= max) {
		throw new OverFlowQueueException();
	}
	cque[rear++] = x;
	num++;
	if(rear == max) {
		rear = 0;
	}
	return x;
}

• 매개변수 : 인큐할 값
• 원형 큐가 가득 차서 인큐할 수 없는 경우, 미리 작성한 OverFlowQueueException 을 throw
• 원형 큐에 매개변수로 전달받은 데이터를 추가한 후, rear 증가
• 데이터가 추가되었으므로 num++
• 인큐하기 전의 rear 값이 max-1 과 같으면 인큐한 후 rear 값이 max 값과 같아져 실제 배열에는 없는 que[max]를 가리키게 된다. 따라서 rear == max의 경우 rear를 0으로 변경해야 한다.
• 반환값 : 인큐한 값

 

 

- deque() : 원형 큐에서 데이터를 디큐

public int deque() throws EmptyQueueException {
	if(num <= 0) {
		throw new EmptyQueueException();
	}
	int x = cque[front++];
	num--;
	if(front == max) {
		front = 0;
	}
	return x;
}

• 원형 큐에서 데이터를 제거
• 원형 큐가 비어있어 디큐할 수 없는 경우, 미리 작성한 EmptyQueueException 을 throw
• 데이터를 실제로 제거하는 것이 아니라 front를 증가시킴으로써 다음에 같은 인덱스에 enque()시 데이터가 덮어씌워짐
• 데이터가 삭제되었으므로 num--
• 디큐하기 전의 front 값이 max-1 과 같으면 디큐한 후 front 값이 max 값과 같아져 실제 배열에는 없는 cque[max]를 가리키게 된다. 따라서 front == max의 경우 front 를 0으로 변경해야 한다.
• 반환값 : 디큐한 값

 

 

- peek() : 원형 큐의 프런트 값, 원형 큐에서 다음에 꺼낼 데이터

public int peek() throws EmptyQueueException {
	if(num <= 0) {
		throw new EmptyQueueException();
	}
	return cque[front];
}

• 원형 큐가 비어있으면 미리 작성한 EmptyQueueException 을 throw
• cque[front]의 값을 확인만 하고 데이터를 변경하지 않으므로 front, rear, num 값은 변하지 않음
• 반환값 : 원형 큐의 프런트 값

 

 

- indexOf() : 원형 큐 데이터 탐색

public int indexOf(int x) {
	for(int i = 0; i < num; i++) {
		int idx = (i + front) % max;
		if(cque[idx] == x) {
			return idx;
		}
	}
	return -1;
}

• 매개변수 : 검색할 데이터
• 원형 큐에 x와 같은 값의 데이터가 포함되어있는지 탐색
• 프런트에서 리어 방향으로 선형 탐색 수행 ( 프런트와 리어의 배열 인덱스가 이어지지 않기 때문에 idx = (i + front) % max )
• 반환값 : 존재하면 찾은 데이터의 idx, 존재하지 않으면 -1

 

 

 

- dump() : 원형 큐 안의 모든 데이터 출력

public void dump() {
	if(num <= 0) {
		System.out.println("원형 큐가 비어있습니다");
	} else {
		for(int i = 0; i < num; i++) {
			System.out.println(cque[(i + front) % max] + " ");
		}
		System.out.println();
	}
}

• 원형 큐에 인큐된 num개의 데이터를 프런트에서 리어 순으로 모두 출력
• 원형 큐가 비어있으면 "원형 큐가 비어있습니다" 출력

 

 

- 기타 메소드

public void clear() {
	num = front = rear = 0;
}

public int capacity() {
	return max;
}

public int size() {
	return num;
}

public boolean isEmpty() {
	return num <= 0;
}

public boolean isFull() {
	return num >= max;
}

• clear() : 현재 원형 큐의 모든 요소를 삭제. 원형 큐의 배열 요소 값을 변경할 필요 없이 num, front, rear 값만 0으로 변경해주면 됨
• capacity() : 원형 큐의 용량 max값 반환
• size() : 원형 큐의 현재 데이터 수 num을 반환
• isEmpty() : 원형 큐가 비어있는지 확인. 비어있다면 true, 아니면 false
• isFull() : 원형 큐가 가득 찼는지 확인. 가득 찼으면 true, 아니면 false