큐 (Queue) 구현해보기

큐란?

먼저 넣은 데이터가 먼저 나오는 FIFO(First In First Out) 기반의 선형 자료 구조

구현 메서드

• 데이터 전체 획득 / 비어 있는지 확인: Queue.getBuffer(), Queue.isEmpty()
• 데이터 추가 / 삭제: Queue.enqueue(), Queue.dequeue()
• 첫번째 데이터 / 사이즈 / 전체 삭제: Queue.front(), Queue.size(), Queue.clear()

array에 존재하는 메서드들을 이용해서 만들었습니다.

1. Queue 객체 생성

function Queue(array) {
    this.array = array ? array : [];
}

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

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

3. 객체가 비어있는지 여부 확인 (Queue.isEmpty())

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

4. Queue에 데이터를 뒤에서 삽입 (Queue.enqueue())

Queue.prototype.enqueue = function (element) {
    return this.array.push(element);
}

5. Queue에서 데이터를 삭제 (Queue.dequeue())

Queue의 경우 가장 앞에서부터 데이터가 삭제되는 구조이기 때문에, shift()를 사용해서 가장 앞쪽의 데이터를 삭제합니다.

Queue.prototype.dequeue = function() {
    return this.array.shift();
}

6. 가장 첫 데이터를 반환 (Queue.front())

만약 Queue의 길이가 0일 경우, 가장 첫 데이터는 없기 때문에 undefined를 반환해주어야 한다.

그렇지 않을 시 에러가 발생할 수 있기 때문에 주의해야 한다.

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

7. Queue의 크기 반환

Queue.prototype.size = function() {
    return this.array.length;
}

8. Queue 초기화

Queue.prototype.clear = function() {
    return this.array = [];
}

Queue 최적화

enqueue와 dequeue를 array의 push와 shift의 메서드를 사용하는 것보다 직접 index에 접근하는 것이 훨씬 더 속도와 성능 측면에서 우수하다.

1. Queue객체 생성

객체를 생성할 때 head와 tail도 함께 속성으로 넣는다.

function Queue(array) {
    this.array = array ? array : [];
    this.tail = array ? array.length : 0;
    this.head = 0;
}

2. enqueue

현재 tail이 가장 length를 가리키고 있다. (즉, 마지막 요소의 뒤를 가리키고 있다.)

enqueue의 경우 마지막에 데이터를 삽입하는 것이므로, this.array[this.length++] = element가 적합하다.

Queue.prototype.enqueue = function (element) {
    return this.array[this.tail++] = element;
}

3. dequeue

1. 삭제할 가장 맨 앞의 데이터를 element에 저장한다. (리턴값을 저장하기 위한 용도)
2. 가리키고 있는 데이터를 삭제한 후 head를 증가시킨다.

Queue.prototype.dequeue = function () {
	if (this.tail === this.head) {
		return undefined;
	}
	let element = this.array[this.head];
	delete this.array[this.head++];
	return element;
}

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