[자바스크립트] Queue 큐 클래스

Queue 클래스 구현

큐( Queue)란?

큐는 한쪽 방향으로 데이터가 삽입되고 반대 방향으로 데이터가 삭제되는 구조입니다.

이와 같은 큐는 가장 먼저 삽입된 데이터가 가장 먼저 삭제되므로 선입 선출(FIFO : First-In First-Out) 구조라고도 합니다.

[이미지 출처 : https://blog.naver.com/hw6544/220854733268]

자바스크립트로 다음과 같은 기능을 가지는 큐를 구현해 보겠습니다.

변수	설명
dataStore	실제 값이 저장되는 배열

함수	설명
enqueue(element)	큐의 끝부분에 요소를 추가
dequeue()	큐의 앞부분의 요소를 꺼내기
back()	큐의 끝부분 요소를 반환
front()	큐의 앞부분 요소를 반환
empty()	큐가 비어있는지를 boolean 으로 반환
toString()	큐의 모든 요소를 문자열로 출력

큐 구현 코드입니다.

// 큐 생성자 함수
function Queue() {
    this.dataStore = [];
    this.enqueue = enqueue;
    this.dequeue = dequeue;
    this.front = front;
    this.back = back;
    this.toString = toString;
    this.empty = empty;
}
 
// 큐의 끝부분에 요소를 추가
function enqueue(element) {
    this.dataStore.push(element);
}
 
// 큐의 앞부분의 요소를 꺼내기
function dequeue() {
    return this.dataStore.shift();
}
 
// 큐의 끝부분 요소 반환
function back() {
    return this.dataStore[this.dataStore.length-1];
}
// 큐의 앞부분 요소 반환
function front() {
    return this.dataStore[0];    
}
 
// 큐의 모든 요소 출력
function toString() {
    return "["+this.dataStore+"]";
}
 
// 큐가 비어있는지 boolean 반환
function empty() {
    return (this.dataStore.length == 0) ? true : false;
}

큐 사용 예제

큐를 이용한 정렬 방법입니다.

(※ 두 자릿수 까지만 정렬 가능한 예제)

// 정렬 예제
var nums = [54,12,5,7,4,1,35,77,46,35,98,45,12,3,55,19,62,68,22,28];
alert(sortNum(nums));
 
// 정렬하는 함수
function sortNum(nums) {
    var resultQueue = new Queue();
    var queues = [];
    for(var i=0;i<10;i++) {
        queues[i] = new Queue();
    }
 
    // 우선 1의 자리로 정렬
    for(var num of nums){
        queues[num%10].enqueue(num);
    }
    nums = [];
    for(var queue of queues){
        while(!queue.empty()){
            nums.push(queue.dequeue());
        }
    }
 
    // 10의 자리로 분류
    for(var num of nums){
        queues[Math.floor(num/10)].enqueue(num);
    }
    nums = [];
    for(var queue of queues){
        while(!queue.empty()){
            nums.push(queue.dequeue());
        }
    }
 
    return nums;
}

자바스크립트 자료구조와 알고리즘 국내도서 저자 : 마이클 맥밀런(Michael McMillan) / 우정은역 출판 : 한빛미디어 2014.08.30 상세보기