원형 큐 (CircularQueue) 구현해보기

원형 큐란?

원형 형태를 가지며, 먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 기반의 선형 자료 구호

원형연결리스트처럼 처음과 끝이 이어져 있는 구조

구현 메서드

• 데이터가 꽉 찼는지 / 비어 있는지 확인: CircularQueue.isFull(), CircularQueue.isEmpty()
• 데이터 추가 / 삭제 / 반환: CircularQueue.enqueue(), CircularQueue.dequeue(), CircularQueue.getBuffer()
• 첫번째 데이터 / 사이즈 / 전체 삭제: CircularQueue.front(), CircularQueue.size(), CircularQueue.clear()

기존 큐와 달리 데이터가 꽉 찼는지 확인하는 메서드가 존재한다. (CircularQueue.isFull())

1. 초기 속성값 설정을 위한 생성자 함수

function CircularQueue(array = [], size = DEFAULT_SIZE) {
    this.array = array;
    this.size = array.length > size ? array.length : size; // CirularQueue의 사이즈
    this.length = array.length; // array의 size
    this.head = 0;
    this.tail = array.length;
}

2. 객체 내 데이터 셋 반환 (CircularQueue.getBuffer())

CircularQueue.prototype.getBuffer = function() {
	return this.array.slice();
}

3. 데이터가 비어있는지 확인 (CircularQueue.isEmpty())

CircularQueue.prototype.isEmpty = function() {
	return this.length === 0;
}

4. 데이터가 꽉 차있는지 확인 (CircularQueue.isFull())

CircularQueue.prototype.isFull = function() {
	return this.size === this.length;
}

5. 데이터 추가 (CircularQueue.enqueue(element))

1. 원형 큐의 크기는 정해져있고, 그 내부를 순회해야한다.
2. 원래 tail은 현재 큐의 length를 가리키고 있고, 새로운 데이터를 추가하면 그 tail이 가리키는 곳에 추가한다.
3. tail은 queue의 크기를 벗어날 필요가 없기 때문에 나머지로 항상 나누어서 저장한다.

CircularQueue.prototype.enqueue = function(element) {
	if (this.isFull()) return false;

	this.array[this.tail] = element;
	this.tail = (this.tail + 1) % this.size;
	this.length++;
	
	return true;
}

6. 데이터 삭제 (CircularQueue.dequeue())

데이터 추가와 비슷하게 head를 기준으로 삭제한다.

CircularQueue.prototype.dequeue = function() {
	if (this.isEmpty()) return undefined;
	
	let element = this.array[this.head];
	delete this.array[this.head];
	this.head = (this.head + 1) % this.size;
	this.length--;
	
	return element;
}

7. 가장 첫 데이터 반환 (CircularQueue.front())

array의 head값을 반환한다.

CircularQueue.prototype.front = function() {
    return this.length === 0 ? undefined : **this.array[this.head]**;
}

8. 큐의 크기 반환 (CircularQueue.dataSize())

CircularQueue.prototype.dataSize = function() {
    return this.length;
}

9. 큐 초기화 (CircularQueue.clear(size))

원형큐의 크기는 그대로 유지한 후 초기화 시킨다.

CircularQueue.prototype.clear = function(size = DEFAULT_SIZE) {
    this.array = [];
    this.size = size;
    this.length = 0;
    this.head = 0;
    this.tail = 0;
};

관련 전체 코드는 Git에 업로드 해두었습니다.
Github_CircularQueue