[Javascript] 자료구조 - 큐(Queue)

큐(Queue) : 먼저 삽입된 데이터가 먼저 추출되는 자료구조 => 탐색 활용빈도에서 많이 사용

 

연결리스트로 큐 구현

• 큐를 연결리스트로 구현하면, 삽입과 삭제에 있어서 O(1)을 보장할 수 있다.
• 연결 리스트로 구현할 때는 머리(head)와 꼬리(tail) 두개의 포인터를 가진다.
• 머리(head) : 남아있는 원소 중 가장 먼저 들어온 데이터를 가리키는 포인터
• 꼬리(tail) : 남아있는 원소 중 가장 마지막에 들어온 데이터를 가리키는 포인터
• 삽일할 때는 꼬리 위치에 데이터 추가
• 삭제할 때는 머리 위치에서 데이터 삭제

 

큐 동작 속도 비교 (배열 vs 연결 리스트)

• 다수의 데이터를 삽입 및 삭제할 때에 대해 수행 시간을 측정
• 단순히 배열 자료형을 이용할 때보다 연결 리스트를 사용할 때 수행 시간 관점에서 효율적
• Javascript에서는 Dictionary 자료형을 이용하여 큐(Queue)를 구현하면 간단하다.

아래 큐 클래스를 사용하여 테스트 해보면 된다.

// 큐 클래스
class Queue {
	constructor() {
    	this.items = {};
        this.headIndex = 0;
        this.tailIndex = 0;
    }
    enqueue(item) {
    	this.items[this.tailIndex] = item;
        this.tailIndex++;
    }
    dequeue() {
    	const item = this.items[this.headIndex];
        delete this.items[this.headIndex];
        this.headIndex++;
        return item;
    }
    peek() {
    	return this.items[this.headIndex];
    }
    getLength() {
    	return this.tailIndex - this.headIndex;
    }
}