프로그래밍 메모장

자바스크립트로 큐를 구현할때 Array 배열의 함수인 shift()를 이용해서 구현하는 경우가 있습니다.

코드 예시

    class Queue1{
        
        constructor(){
            this.arr = [];
        }
        
        isEmpty(){
            return this.arr.length === 0;
        }
        
        enqueue(value){
            this.arr.push(value);
        }
        
        dequeue(){
            
            if(this.isEmpty()){
                return null;
            }
            
            return this.arr.shift();
        }
    }
    
    const length = 100000;
    const que1 = new Queue1();
    const time = new Date();
    
    for(let i=0; i<length; i++){
        que1.enqueue(i);
    }
    
    for(let j=0; j<length; j++){
        que1.dequeue();
    }
    
    console.log(new Date() -time); // 2125ms

큐를 구현할때 해당 방식이 가장 쉽고 간편합니다. 

다만 array의 shift() 함수의 시간 복잡도가 O(n)이라(맨 앞의 값을 pop 시키고 한칸씩 앞으로 당기는 식으로 구현되어 있음)

데이터의 크기가 많아질수록 느려지는 문제가 발생할 수 있습니다.

그래서 다른 방법을 찾아봐야 하는데 대안으로 다음과 같은 방식을 생각해 보았습니다.

1. 배열 + 원형 큐

->  크기 limit 문제

2. stack 2개로 1개의 큐 만들기

스택 두개에서 하나에 데이터를 쭉 쌓고, dequeue 요청이 들어오면 다른 스택에 전부 pop하기(그럼 역순으로 쌓임)

-> pop할때 오버헤드 발생

3. 링크드 리스트 사용

이 중 가장 간편한 방법이자 성능이 좋은 방법이 단방향 링크드 리스트를 이용하는 방법입니다.

코드로 봅시다.

코드 예시

    class Queue2{
        
        constructor(){
            this.head = this.cursor = undefined;
        }
        
        isEmpty(){
            
            if(!this.head){
                return true;
            }
            
            return false;
        }
        
        enqueue(value){
            
            if(!this.head){
                this.head = this.cursor = new Node(value);
                return;
            }
            
            const node = new Node(value);
            this.cursor.next = node;
            this.cursor = node;
        }
        
        dequeue(){
            
            if(this.isEmpty()){
                return null;
            }
            
            const tmp = this.head;
            this.head = this.head.next;
            
            if(tmp === this.cursor){
                this.cursor = this.head;
            }
            
            return tmp.value;
        }
    }
    
    
    
    const length = 100000;
    const que2 = new Queue2();
    const time = new Date();
    
    for(let i=0; i<length; i++){
        que2.enqueue(i);
    }
    
    for(let j=0; j<length; j++){
        que2.dequeue();
    }
    
    console.log(new Date() -time); // 16ms

매우 간단한 단방향 링크드 리스트를 사용한 방식입니다.

코드를 요약하자면 

head 변수가 맨 앞 노드를 가리키고, cursor 변수가 맨 뒤를 가리킵니다. (포인터 느낌?)

push때엔 노드를 맨 뒤에 추가하고 cursor를 해당 노드로 변경,

pop땐 head에서 노드를 하나씩 꺼내고 한칸 뒤로 head 커서를 이동하는식으로 간단히 구현이 되어 있습니다.

해당 방식으로 2초 가량 걸리던 코드가 16ms 정도 걸리는 정도로 성능이 개선되었습니다.

js에는 STL같은 라이브러리가 없으니 직접 큐를 구현할 일이 생길때 쓰면 좋을듯 싶습니다.