[자료구조 with JS] 큐(Queue)

큐(Queue)

 데이터가 한쪽으로 들어와서 다른 쪽으로 나가는 자료구조. 사람들이 줄을 서서 입장을 기다리는 것을 생각하면 된다. 

큐의 특징

1. First In First Out (FIFO): 먼저 들어온 정보가 먼저 나가는 구조이다.

2. 큐에 입력된 데이터는 그 순서가 계속 유지된다. 즉, 들어온 순서 그대로 나간다.

3. 큐의 삽입과 삭제는 각각 배열의 unshift & pop 또는 shift & push를 사용하여 구현할 수 있다. (두 방법은 줄 서는 방향의 차이이다. unshift & pop은 오른쪽부터 왼쪽으로 줄을 서고 shift & push는 왼쪽부터 오른쪽으로 줄 선다.)

 

 

삽입과 삭제

unshift & pop 사용

class Queue { 

    constructor() { 
    	this.data = []; 
    } 
    
    add(record) { 
    	this.data.unshift(record); 
    } 
    
    remove() { 
    	return this.data.pop(); 
    } 
    
}

• 삽입의 시간복잡도는 O(n): unshift() 메서드가 기존 배열의 항목들을 인덱스 하나씩 밀어내기 때문에 배열의 길이만큼의 시간이 든다.
• 삭제의 시간복잡도는 O(1)

 

shift & push 사용

class Queue { 

    constructor() { 
    	this.data = []; 
    } 
    
    add(record) { 
    	this.data.push(record); 
    } 
    
    remove() { 
    	return this.data.shift(); 
    } 
    
}

• 삽입의 시간복잡도는 O(1)
• 삭제의 시간복잡도는 O(n): shift() 메서드가 인덱스 0의 항목을 제거하고 남은 인덱스를 하나씩 감소시키기 때문에 배열의 전체 항목의 인덱스가 변경돼야 한다.

 

 

들여다보기 (peek)

<문제>

 'peek' 메소드를 Queue 클래스에 만들어라. peek 메서드는 마지막 요소(다음에 큐에서 나올 요소)를 return 해야 하며, 큐에서 그 요소를 삭제해서는 안된다.

 

<Solution>

class Queue {
    // unshift & pop을 활용한 Queue 클래스
    peek() {
    	return this.data[this.data.length - 1];
    }
    
    // shift & push를 활용한 Queue 클래스
    peek() {
    	return this.data[0];
    }
}

 

반응형

 

두 개의 Queue를 엮어 새로운 Queue를 만들기

<문제>

 'weave' 함수를 Queue 클래스에 만들어라. weave는 두 개의 큐를 인자(argument)로 받고, 그 둘을 합쳐 새로운 큐를 만든다. 새로운 큐에는 인자로 받은 두 개의 큐의 데이터가 번갈아가며 들어있어야 한다. 또한 이 함수는 길이가 다른 두 개의 큐를 인자로 받더라도, undefined가 포함되지 않게 새로운 큐를 만들 수 있어야 한다.

 주의: 큐의 배열에 직접 접근하면 안 된다. add, remove, peek 메서드만 이용해야 한다.

 

<Solution>

function weave(sourceOne, sourceTwo) {
    const q = new Queue();
	
    //두 큐 중에 하나라도 데이터가 남아있으면 반복됨
    while (sourceOne.peek() || sourceTwo.peek()) {
        if(sourceOne.peek()) {
            //Queue 클래스의 remove 메서드는 삭제한 데이터를 반환한다.
            //따라서 삭제하는 것과 동시에 q에 추가할 수 있다.
            q.add(sourceOne.remove());
        } else if (sourceTwo.peek()) {
            q.add(sourceTwo.remove());
        }
    }

    return q
}

 

 

참고: ⟨자바스크립트로 하는 자료구조와 알고리즘(배세민 저)⟩, The Coding Interview Bootcamp: Algorithms + Data Structures (Udemy Course)