Queue in Javascript

• 큐는 FIFO(First In First Out)의 특징을 가지는 자료구조이다.
• 자바스크립트에서 큐를 만든다면, 가장 쉬운 방법은 다음과 같이 .shift()를 사용하는 방법이다.

const queue = [];

// 큐에 삽입
queue.push(2);
queue.push(3);
queue.push(4);

console.log(queue); // [ 2, 3, 4 ]

// 큐에서 하나씩 꺼내기
const one = queue.shift();
const two = queue.shift();
const three = queue.shift();

console.log(one, two, three); // 2, 3, 4

• 하지만, 자바스크립트를 사용할 수 있는 많은 코딩테스트에서 shift()를 사용하면, 효율적인 알고리즘을 작성하는 데 문제가 있을 수 있다.
• 자바스크립트에서 가장 첫번째 배열의 0번째 인덱스의 원소를 삭제하는 shift()가 효율적으로 작동하지 않기 때문이다.
• 따라서, 자바스크립트에서 효율적으로 큐를 사용하기 위해서 다음과 같은 방법들로 큐를 사용할 수 있다.

const queue = [];
let queueIdx = 0;
// 큐의 가장 첫 번째 원소를 가리키는 인덱스

// 큐에 삽입하기
for(let i = -10; i < 0; i += 2){
    queue.push(i);
}

// 큐에서 모두 내보내기
while(queue.length !== queueIdx){
    console.log(queue[queueIdx++]);
}
// -10 -8 -6 -4 -2

• 큐 배열에 데이터가 무한히 쌓이는 것을 원하지 않는다면, 큐 배열을 동적으로 만들지 않고 정적으로 만들 수도 있다.

const QUEUE_SIZE = 4; // 우리가 사용할 큐 사이즈를 미리 정해 놓는다.
const REAL_QUEUE_SIZE = QUEUE_SIZE + 1; // 빈 상태와 포화 상태의 구별을 위해서 배열 한 칸을 더 사용한다.
const queue = new Array(REAL_QUEUE_SIZE);
let front = 0, rear = 0;

const isEmpty = () => {
    // front 와 rear가 같은 상태는 빈 상태로 본다.
    return front === rear ? true : false;
}

const queueSize = () => {
    // 큐의 사이즈를 반환한다.
    return Math.abs(rear - front);
}

const pushQueue = (ele) => {
    if((rear + 1) % REAL_QUEUE_SIZE === front){ // rear보다 front가 1 더 큰 상태는 포화 상태
        // 큐가 가득 참
        console.log("OVERFLOW");
    } else {
        // 삽입이 가능하다.
        queue[rear] = ele;
        rear = (rear + 1) % REAL_QUEUE_SIZE;
    }
}

const shiftQueue = () => {
    if(isEmpty()){
        // 삭제할 큐의 원소가 없다.
        console.log("UNDERFLOW");
        return "ERROR";
    } else {
        const data = queue[front];
        front = (front + 1) % REAL_QUEUE_SIZE;
        return data;
    }
}

pushQueue(1);
pushQueue(2);
console.log(shiftQueue()); // 1
pushQueue(3);
pushQueue(4);
pushQueue(5);
pushQueue(6); // OVERFLOW, 사용되는 큐의 크기는 4

while(!isEmpty()){
    console.log("출력 : " + shiftQueue());
}

/*
    출력되는 결과는 다음과 같다.

    1
    OVERFLOW
    출력 : 2
    출력 : 3
    출력 : 4
    출력 : 5
*/