큐 - 개념

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

큐(Queue)는 First In First Out(FIFO) 규칙을 따르는 선형 자료구조로, 데이터의 삽입은 한쪽 끝에서, 삭제는 반대쪽 끝에서 이루어집니다. 큐의 가장 큰 특징은 가장 먼저 들어온 데이터가 가장 먼저 나간다는 것입니다. 이번 섹션에서는 양방향 연결 리스트를 활용하여 큐를 구현하는 방법을 살펴보겠습니다.

1. 양방향 연결 리스트의 구현

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

// Node.js

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

2. 큐의 추상 자료형 구현

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

• enqueue: 큐의 맨 끝에 데이터를 추가합니다.
• dequeue: 큐의 맨 앞에서 데이터를 꺼냅니다.
• peek: 큐의 맨 앞에 있는 데이터를 확인합니다.
• isEmpty: 큐가 비어 있는지 확인합니다.

// Queue.mjs

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

class Queue {
  constructor() {
    this.list = new LinkedList();
    this.tail = null;
  }

  // 데이터 삽입
  enqueue(data) {
    const newNode = new Node(data);
    if (this.list.isEmpty()) {
      this.list.head = newNode;
    } else {
      this.tail.next = newNode;
      newNode.prev = this.tail;
    }
    this.tail = newNode;
    this.list.count++;
  }

  // 데이터 제거
  dequeue() {
    if (this.list.isEmpty()) {
      return null;
    }
    const data = this.list.head.data;
    this.list.head = this.list.head.next;
    if (this.list.head) {
      this.list.head.prev = null;
    } else {
      this.tail = null;
    }
    this.list.count--;
    return data;
  }

  // 큐의 맨 앞 데이터 확인
  peek() {
    return this.list.isEmpty() ? null : this.list.head.data;
  }

  // 큐가 비어있는지 확인
  isEmpty() {
    return this.list.isEmpty();
  }
}

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("큐의 맨 앞 데이터 확인 (peek):");
console.log(queue.peek()); // 출력: 1

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

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

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