[TIL 4]큐 in JS

큐(Queue)

FIFO 구조이다. first in first out!
js에서 배열로 큐를 구현하게 되면 동적으로 할당이 자동으로 이루어지기 때문에, c나 c++ 처럼 배열이 꽉 차거나 그런 문제점은 없지만 시작 index가 무한정 늘어나버릴 수 있다는 단점이 있다.

그리고 js에서 큐를 지원하지 않기 때문에(왜때문에ㅠㅠ) 구현해서 써야 한다..
구현이 어렵지는 않기 때문에 귀찮지만 괜찮다!..

그리고 배열에서 맨 앞 원소를 제거하는 shift 쓰지말라고 한다!
=> 로직 자체가 O(n)이 걸리기 때문에 성능에서 큐의 성능이 나오지 않는다.😢

js로 queue 구현하기

배열로 queue 구현

class Queue{
    constructor(){
        this.queue = [];
        this.front = 0;
        this.rear = 0;

    }   
   enqueue(value){
        this.queue[this.rear++] = value;
   }

   dequeue(){
        const value = this.queue[this.front];
        delete this.queue[this.front];
        this.front += 1;
        return value;
   }

   peek(){
        return this.queue[this.front];
   }

   size(){
        return this.rear - this.front;
   }
   empty(){
       return this.front === this.back;
   }
}

//사용해보기

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
console.log(queue.dequeue()); // 1
queue.enqueue(8);
console.log(queue.size()); // 3
console.log(queue.peek()); // 2
console.log(queue.dequeue()); // 2
console.log(queue.dequeue()); // 4

요러케 queue를 구현해봤다. 생각보다 코드가 다행히 간단하다😊

연결리스트로 queue 구현

연결리스트로도 queue를 구현할 수 있다.

//linkedList queue

class Node{
    constructor(value){
        this.value = value;
        this.next = null;
    }
}

class LinkedListQueue{
    constructor(){
        this.front = null;
        this.rear = null;
        this.length = 0;
    }

    enqueue(value){
        const newNode = new Node(value);
        if(this.empty()){
            this.front = this.rear = newNode;
        }else{
            this.rear.next = newNode;
            this.rear = newNode;
        }
        this.length += 1;
    }

    dequeue(){
        const delValue = this.front.value;
        this.front = this.front.next;
        this.length -= 1;
        return delValue;
    }
    peek(){
        return this.front.value;
    }
    empty(){
        return this.front === null;
    }
    size(){
        return this.length;
    }
}

//사용해보기
const queue = new LinkedListQueue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
console.log(queue.dequeue());
queue.enqueue(8);
console.log(queue.peek());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.empty());

원형 큐

원형 큐는 앞에 말했던 큐의 단점을 보완하기 위해 고안했다.
배열의 한정된 메모리를 효율적으로 쓰기 위해 한정된 크기의 배열에서 처음과 끝이 맏닿아 있는 구조를 가지고 계속 빙글빙글 도는? 그런 구조라고 할 수 있다.

자바스크립트에서는 쓸 일이 많지 않긴 하지만,(배열이 동적으로 늘어나기 때문에) 한번 구현해보면 좋을 것 같아 구현해보았다.

//Circular Queue

class CircularQueue{
    constructor(maxSize){
        this.maxSize = maxSize;
        this.queue = [];
        this.front = 0;
        this.rear = 0;
        this.size = 0;
    }

    enqueue(value) {
        if(this.isFull()){
            console.log("Queue is full");
            return;
        }
        this.queue[this.rear] = value;
        this.rear = (this.rear + 1) % this.maxSize;
        this.size += 1;
    }

    dequeue(){
        const delValue = this.queue[this.front];
        this.front = (this.front + 1) % this.maxSize;
        this.size -= 1;
        return delValue;
    }

    isFull(){
        return this.size === this.maxSize;
    }
    peek(){
        return this.queue[this.front];
    }
}

// 사용해보기

const queue = new CircularQueue(4);
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(4);
queue.enqueue(8);
queue.enqueue(16);
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.size);
console.log(queue.peek());
queue.enqueue(16);
queue.enqueue(32);
console.log(queue.isFull());

문제 풀어보기(프로그래머스)

프로그래머스의 레벨2 "프린터" 이다.

https://programmers.co.kr/learn/courses/30/lessons/42587

내가 풀어본 해답 코드
class Queue{
    constructor(){
        this.queue = [];
        this.front = 0;
        this.back = 0;
    }
    
    enqueue(document){
        this.queue[this.back++] = document;
    }
    
    dequeue(){
        const document = this.queue[this.front];
        delete this.queue[this.front];
        this.front += 1;
        return document;
    }
    check(document){
        for(let i = this.front; i < this.back; i++){
            //console.log(this.queue[i]);
            if(this.queue[i].priority > document.priority) return true;
        }
        return false;
    }
    
}

function solution(priorities, location) {
    
    const queue = new Queue();
    for(let i =0; i < priorities.length; i++){
        queue.enqueue(
            { index : i, priority : priorities[i] }
        );
    }
    
    
    let answer = 1;
    while(queue.queue.length > 0){
        const document = queue.dequeue();    
        if(!queue.check(document)){
            if(document.index === location)
                break;
            else answer++;
        } else{
            queue.enqueue(document); 
        }
    }

    return answer;
}

tmi...
코드에 색 넣는 법을 알았다!!! 백틱 뒤에 언어 이름만 써주면 끝!!