큐(Queue)

🤓오늘의 공부 주제: 큐🤓

큐란?
큐(Queue)는 질서 있는 줄을 의미한다.

First In First Out
먼저 들어간 데이터가 먼저 나오는 규칙. 스택과 반대의 특징.
운영체제가 프로세스의 작업 요청을 들어온 순서대로 큐에 넣고 cpu가 순서대로 처리 = fifo 스케줄링

삽입은 가장 앞으로 넣고 제거는 가장 뒤에서부터 하면 됨.
구현상 연결리스트는 단방향 연결리스트이기 때문에 가장 앞에서부터 삽입하는 것은 기존의 연결리스트로 문제가 없지만 가장 뒤에거를 삭제하기 위해서는 앞에서부터 차례로 노드를 하나씩 탐색해야 하기 때문에 o(n)의 문제가 발생. 따라서 성능을 위해서 tail이라는 변수를 하나 더 만듦.

head는 가장 앞 노드. tail은 가장 뒤 노드. 이를 통해 o(1)로 만들 수 있음. 새로 삽입하는 노드를 head로 만들고 tail만 삭제하면 되지만 삭제 후에 다시 가장 끝의 노드를 tail로 지정해줘야함. 이때 역시 다음 노드만 가리키는 단방향 연결리스트 이기 때문에 tail로 이전노드 참조 불가능. 다시 head부터 탐색해서 tail지정하면 이전과 같은 o(n)의 성능. 따라서 현재 노드가 이전 노드도 가리킬 수 있는 이중연결리스트가 필요.

class Node{
    constructor(data, next = null, prev = null){
        this.data = data;
        this.next = next;
        this.prev = prev;
    }
}

class DoublyLinkedList{
    constructor(){
        this.head = null;
        this.tail = null;
        this.count = 0;
    }

    printAll(){
        let currentNode = this.head;
        let text = "[";

        while(currentNode != null){
            text += currentNode.data;
            currentNode = currentNode.next;

            if(currentNode != null){
                text += ", ";
            }
        }

        text += "]";
        console.log(text);
    }

    clear(){
        this.head = null;
        this.count = 0;
    }

    insertAt(index, data){
        if(index > this.count || index < 0){
            throw new Error("범위를 넘어갔습니다.");
        }

        let newNode = new Node(data);

        if(index == 0){
            newNode.next = this.head;
            if(this.head != null){
                this.head.prev = newNode;
            }
            this.head = newNode;
        }else if(index == this.count){
            newNode.next = null;
            newNode.prev = this.tail;
            this.tail.next = newNode;
        }else {
            let currentNode = this.head;

            for(let i = 0; i < index - 1; i++){
                currentNode = currentNode.next;
            }
            newNode.next = currentNode.next;
            newNode.prev = currentNode;
            currentNode.next = newNode;
            newNode.next.prev = newNode;
        }

        if(newNode.next == null){
            this.tail = newNode;
        }
        this.count++;
    }

    insertLast(data){
        this.insertAt(this.count, data);
    }

    deleteAt(index){
        if(index >= this.count || index < 0){
            throw new Error("제거할 수 없습니다.");
        }

        let currentNode = this.head;

        if(index == 0){
            let deletedNode = this.head;
            if(this.head.next == null){
                this.head = null;
                this.tail = null;
            } else {
                this.head = this.head.next;
                this.head.prev = null;
            }
            this.count--;
            return deletedNode;
        } else if(index == this.count - 1){
            let deletedNode = this.tail;
            this.tail.prev.next = null;
            this.tail = this.tail.prev;
            this.count--;
            return deletedNode;
        } else {
            for(let i = 0; i < index - 1; i++){
                currentNode = currentNode.next;
            }

            let deletedNode = currentNode.next;
            currentNode.next = currentNode.next.next;
            currentNode.next.prev = currentNode;
            this.count--;
            return deletedNode;
        }
    }

    deleteLast(){
        return this.deleteAt(this.count - 1);
    }

    getNodeAt(index){
        if(index >= this.count || index < 0){
            throw new Error("범위를 넘어갔습니다.");
        }

        let currentNode = this.head;
        for(let i = 0; i < index; i++){
            currentNode = currentNode.next;
        }

        return currentNode;
    }
}

export { Node, DoublyLinkedList};

import { DoublyLinkedList } from "./DoublyLinkedList.mjs";

class Queue{
    constructor(){
        this.list = new DoublyLinkedList();
    }

    enqueue(data){
        this.list.insertAt(0, data);
    }

    dequeue(){
        try{
            return this.list.deleteLast();
        } catch(e){
            return null;
        }
    }

    front(){
        return this.list.tail;
    }

    isEmpty(){
        return (this.list.count == 0);
    }
}

export {Queue};