4. 큐(Queue)

큐의 개념

먼저 들어간 데이터가 먼저 나오는 구조로 Stack와 반대 특성

맨 먼저 들어간 데이터를 삭제하기 위해서 가장 앞(head) 노드부터 순서대로 타고 가야하는 단점(느려짐 O(n)의 성능)이 생기는데 이를 보완하기 위해 tail 이라는 변수를 설정해 준다.

tail이라는 변수를 설정한다고 해서 성능이 보완되지는 않는다. tail이 가리키된 Node를 삭제 하더라도 삭제된 Node 앞의 Node를 다시 tail로 설정해줘야 하기 때문 우리가 만든 연결 리스트는 다음 Node만 가리키는 단방향 연결 리스트이기 때문에 tail로 이전 Node를 참조할 수 없다.

현재 노드가 이전 노드를 가리킬 수 있는 이중 연결 리스트로의 수정이 필요하다.

이중 연결 리스트로의 수정으로 각 노드가 이전 노드로 가리킬 수 있는 양방향 연결 리스트로 수정해준다.

양방향 연결 리스트로 수정

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 deleteNode = 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 deleteNode;
        } else if (index == this.count - 1) {
            let deleteNode = this.tail;
            this.tail.prev.next = null;
            this.tail = this.tail.prev;
            this.count--;
            return deleteNode;
        } else {
            for (let i = 0; i < index - 1; i++) {
                currentNode = currentNode.next;
            }
            let deleteNode = currentNode.next;
            currentNode.next = currentNode.next.next;
            currentNode.next.prev = currentNode;
            this.count--;
            return deleteNode;
        }
    }
    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 };

Queue 의 추상 자료형을 코드로 구현

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 };

Queue에 데이터를 입력하고 삭제해보았다

import { Queue } from './Queue.mjs';
let queue = new Queue();

console.log('=====enqueue() 세번 호출=====');
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

console.log(queue.front());

console.log('=====dequeue() 네번 호출=====');
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());
console.log(queue.dequeue());

console.log(`isEmpty: ${queue.isEmpty()}`);

λ node test_Queue.mjs 
=====enqueue() 세번 호출=====
<ref *1> Node {
  data: 1,
  next: null,
  prev: <ref *2> Node {
    data: 2,
    next: [Circular *1],
    prev: Node { data: 3, next: [Circular *2], prev: null }
  }
}
=====dequeue() 네번 호출=====
Node {
  data: 1,
  next: null,
  prev: <ref *1> Node {
    data: 2,
    next: null,
    prev: Node { data: 3, next: [Circular *1], prev: null }
  }
}
Node {
  data: 2,
  next: null,
  prev: Node { data: 3, next: null, prev: null }
}
Node { data: 3, next: null, prev: null }
null
isEmpty: true