JS로 queue 구현하기

Queue란❓

🤔 굳이 구현해야 할까?

• 사실 자바스크립트에서 Queue를 독립적으로 자체 제공하지는 않지만 배열(Array)를 이용하여 큐의 기능을 흉내낼 수 있다.

• 자바스크립트의 배열 내장 메서드 중에는 shift() 라는 메서드가 있는데, 이는 배열의 가장 앞에 있는 원소부터 하나씩 제거하는 기능을 수행한다. 즉 배열의 pop() 메서드의 역방향이라고 볼 수 있다.

• 그러나 해당 방식은 근본적인 문제가 있다.

• 바로 배열을 활용해서 FIFO 원칙을 적용한다는 점인데, 이 부분에서 원래 큐 자료구조의 시간복잡도와 상당한 차이가 발생하게 된다.

• 배열을 활용한 큐의 구조에서 상당한 시간이 소요되는 이유는 shift() 메서드를 통해 원소를 앞에서 부터 하나씩 제거할 때, 나머지 배열 원소에 대한 재정렬이 이루어져야 하기 때문이다.

• 따라서 시간 복잡도를 매우 세세하게 관리해야 하는 경우에 직접 구현한 큐를 이용하여 더 빠른 시간 복잡도로 문제에 접근한다면 통과할 수도 있다.

💡 구현

export default class MyQueue {
    constructor() {
        this.input = [];
        this.output = [];
        this.size = 0;
    }
    enque(val) {
        this.input.push(val);
        this.size++;
    }
    deque() {
        if (this.output.length === 0) {
            this.output = this.input.reverse();
            this.input = [];
        }
        this.size--;
        return this.output.pop();
    }
}

🍒 구현 포인트

FIFO를 위한 작업

• output이 항상 비워져 있어야 한다. 따라서 if문으로 조건을 걸어 output의 길이가 0이라면 로직을 수행한다.

• reverse()를 이용하여 input의 순서를 뒤집는다.