큐 - 구현

큐(Queue) 구현: 양방향 연결 리스트를 활용한 순차적 데이터 처리

큐는 FIFO(First In First Out) 방식으로 데이터를 관리하는 선형 자료구조입니다. 데이터의 삽입(enqueue)은 한쪽 끝에서 이루어지고, 데이터의 삭제(dequeue)는 반대쪽 끝에서 이루어집니다. 이번 섹션에서는 양방향 연결 리스트를 활용하여 큐를 구현하는 방법을 살펴보겠습니다.

1. 양방향 연결 리스트의 수정

양방향 연결 리스트는 각 노드가 다음 노드 뿐만 아니라 이전 노드를 가리키는 포인터도 가지고 있습니다. 이를 통해 노드의 추가 및 삭제가 더욱 유연하고 효율적으로 이루어질 수 있습니다.

// DoublyLinkedList.mjs

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("== printAll() == : ", 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) {
      /**
       * head에 삽입하는 경우
       */

      newNode.next = this.head;

      if (this.head != null) {
        this.head.prev = newNode;
      }

      this.head = newNode;
    } else if (index == this.count) {
      /**
       * tail에 삽입하는 경우
       */
      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) {
        /**
         * 데이터가 1개 남은경우
         */

        this.head = null;
        this.tail = null;
      } else {
        /**
         * 데이터가 2개 이상인 경우
         */

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

2. 큐의 추상 자료형 구현

큐는 다음과 같은 기능을 가지고 있습니다:

• enqueue(data): 큐의 끝에 데이터를 추가합니다.
• dequeue(): 큐의 시작에서 데이터를 제거하고 반환합니다.
• front(): 큐의 시작에 있는 데이터를 조회합니다.
• isEmpty(): 큐가 비어 있는지 확인합니다.

// Queue.mjs

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

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

  enqueue(data) {
    this.list.insertAt(this.list.count, data); // 끝에 데이터 삽입
  }

  dequeue() {
    if (this.isEmpty()) {
      return null;
    }
    const data = this.list.deleteAt(0).data; // 시작에서 데이터 제거
    return data;
  }

  front() {
    return this.list.head ? this.list.head.data : null;
  }

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

export { Queue };

3. 큐의 사용

큐의 기능을 테스트하기 위해 다음과 같은 테스트 코드를 작성할 수 있습니다.

// test_queue.mjs

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

const queue = new Queue();

console.log("큐에 데이터 추가:");
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.enqueue(4);

console.log("큐의 시작 데이터 확인 (front):");
console.log(queue.front()); // 출력: 1

console.log("큐에서 데이터 제거 (dequeue):");
while (!queue.isEmpty()) {
  console.log(queue.dequeue()); // 출력: 1, 2, 3, 4
}

console.log("큐가 비어있는지 확인 (isEmpty):");
console.log(queue.isEmpty()); // 출력: true

큐는 데이터를 관리하는 데 매우 유용한 자료구조로, 특히 순차적으로 데이터를 처리해야 하는 경우에 사용됩니다. 큐는 네트워크 요청 대기열, 프린터 작업 대기열, CPU 작업 스케줄링 등 다양한 상황에서 활용될 수 있습니다. 양방향 연결 리스트를 기반으로 구현된 큐는 데이터의 동적인 추가 및 제거에 용이하며, 데이터 처리 과정에서 발생할 수 있는 다양한 시나리오를 효율적으로 처리할 수 있습니다.