JavaScript Queue 구현

JavaScript로 Queue를 사용하기 위해 찾아다녔는데, Array의 Shift를 이용해 Array를 Queue처럼 사용할 수 있다는 사실을 알았다. Push와 Shift로 쉽게 큐를 만들어서 쓸 수도 있었지만, 시간복잡도가 내가 생각하는 Queue와 동일한지 살짝 의심이 되었다. 

일반적으로 Queue는 Push와 Pop을 할 때 시간복잡도가 O(1)이 걸리게 된다. 보통 Linked List로 구현하기에 당연한 결과이다. 하지만, JavaScript로 push와 shift 연산이 동일하게 시간이 걸리는지 비교해보니 shift가 더 오래걸리는 것으로 확인이 되었다. 뭔가 수상하다...?

    let start = new Date();
    let maxNum = 100000;
    let arr = [];
    for (let i = 0; i < maxNum; i++) {
        arr.push(1);
    }
    let end = new Date();
    console.log(`push ${maxNum} elements ${end - start}ms`);

    start = new Date();
    for (let i = 0; i < maxNum; i++) {
        arr.shift();
    }
    end = new Date();
    console.log(`shift ${maxNum} elements ${end - start}ms`);

chrome에서 실행한 100,000개의 숫자를 push와 shift한 결과

찾아보니, JavaScript는 Array가 C나 Java에서와 같은 연속된 메모리가 할당되어 구현된 자료구조가 아니라, Hash Table로 구현되어 있다는 것을 알게 되었다. 정말로 Hash Table로 동작하였다고 하더라도, 실행결과가 이상했다. 아무래도 브라우저 자체적으로 최적화를 하여, 발생한 문제인 듯했다.

내가 원했던 Queue는 원소를 추가하고 빼는 작업을 진행할 때, 시간복잡도가 O(1)인 것을 원했다. 그래서 Linked List로 Queue를 구현해서 문제를 풀어보고자 했다.

Queue는 head와 tail에 각각 처음과 마지막 원소를 저장하도록 한다. enqueue를 하면 tail의 next에 새로운 원소를 붙여주고, 새로운 원소를 tail로 세팅해준다. dequeu를 하면 head의 next를 head로 설정해주고, 원래의 head값을 리턴해준다. 

NodeQueue라는 클래스를 만들어 각각의 요소를 담는데 사용하였고, Queue라는 클래스가 NodeQueue를 Linked List의 형태로 이어붙여서 데이터를 관리하도록 하였다. 각각의 아래는 구현한 코드이다.

class NodeQueue{
    constructor(value){
        this.next = null;
        this.value = value;
    }
}
class Queue{
    constructor (){
        this.head = null;
        this.tail = null;
        this.size = 0;
    }
    enqueue(value){
        let nodeQueue = new NodeQueue(value);
        if(this.size == 0){
            this.head = nodeQueue;
        }else{
            this.tail.next = nodeQueue;
        }
        this.tail = nodeQueue;
        this.size++;
    }
    dequeue(){
        if(this.size== 0){
            return null;
        }
        let value = this.head.value;
        this.head = this.head.next;
        this.size--;
        if(this.size == 0){
            this.tail = null;
        }
        return value;
    }
    isEmpty(){
        return this.size == 0;
    }
}

이제 내가 구현한 Queue의 performance를 측정해보자. 

    start = new Date();
    let q = new Queue();
    for (let i = 0; i < maxNum; i++) {
        q.enqueue(1);
    }
    end = new Date();
    console.log(`enqueue ${maxNum} elements ${end - start}ms`);

    start = new Date();
    for (let i = 0; i < maxNum; i++) {
        q.dequeue();
    }
    end = new Date();
    console.log(`dequeue ${maxNum} elements ${end - start}ms`);

enqueue와 dequeue를 실행한 시간

확실히, enqueue와 dequeue의 시간차이가 거의 나지 않았고, 내가 원했던대로 O(1)의 시간에 구현된 것을 확인할 수 있었다. enqueue의 시간 dequeue보다 조금 더 긴 것은 아무래도 객체를 새로 할당하는데 시간이 소요되었기 때문일 것이다. 

백준 10845번 큐 문제를 이렇게 구현한 Queue로 해결해보았고, 문제없이 통과되었다.

www.acmicpc.net/problem/10845

10845번: 큐

github에 백준 문제를 통과하는 코드를 올려놓았다.

github.com/JH-Ha/Algorithm/blob/master/baekjoon/10845/ans.js

JH-Ha/Algorithm

수의 크기가 크지 않을 때는 Array의 shift를 써서 구현해도 상관없을 것 같다. 알고리즘 문제를 효율적으로 푸는 것에 민감해져있어서 그런지 직접 Queue를 구현하였는데, 백준 10845번 문제는 shift를 사용한 Queue도 통과되었다. 그래서 자료의 크기에 따라서 적절히 구현 방법을 선택하여 문제를 풀면 될 것이라 생각한다.