자료구조와 알고리즘, Queue

 

큐(Queue)는 자료 구조의 한 형태로, 선입선출(FIFO, First In First Out) 원칙을 따릅니다. 즉, 먼저 삽입된 데이터가 먼저 삭제됩니다. 큐는 일상 생활의 줄 서기와 유사합니다. 예를 들어, 사람들이 줄을 서서 대기하는 경우, 줄의 맨 앞에 있는 사람이 가장 먼저 서비스받고 줄에서 나가며, 새로운 사람은 줄의 맨 뒤에 서게 됩니다.

큐의 기본 연산

1. enqueue: 큐의 맨 뒤에 요소를 추가합니다.
2. dequeue: 큐의 맨 앞에서 요소를 제거하고 반환합니다.
3. peek/front: 큐의 맨 앞 요소를 반환하지만, 제거하지는 않습니다.
4. isEmpty: 큐가 비어 있는지 확인합니다.
5. size: 큐의 요소 개수를 반환합니다.

큐의 활용 사례

• 운영 체제: 작업 스케줄링 및 프로세스 관리에서 사용됩니다.
• 프린터 관리: 인쇄 대기열에서 사용됩니다.
• 네트워크: 데이터 패킷의 전송 순서 관리를 위해 사용됩니다.
• 콜 센터 대기열: 고객 서비스에서 콜 대기열 관리에 사용됩니다.

큐의 구현 방법

큐는 배열이나 링크드 리스트를 사용하여 구현할 수 있습니다. 배열을 사용한 구현은 고정된 크기를 가지며, 링크드 리스트를 사용한 구현은 동적 크기를 가집니다.

배열 기반 구현

배열을 사용한 큐는 정적 크기를 가지며, 요소를 추가하거나 제거할 때마다 배열을 이동시키는 방식입니다.

class ArrayQueue {
  constructor() {
    this.queue = [];
  }

  enqueue(value) {
    this.queue.push(value);
  }

  dequeue() {
    return this.queue.shift();
  }

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

  isEmpty() {
    return this.queue.length === 0;
  }

  size() {
    return this.queue.length;
  }
}

링크드 리스트 기반 구현

링크드 리스트를 사용한 큐는 동적 크기를 가지며, 요소를 추가하거나 제거할 때 포인터를 이동시키는 방식입니다.

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

class LinkedListQueue {
  constructor() {
    this.first = null; // 큐의 맨 앞 요소
    this.last = null;  // 큐의 맨 뒤 요소
    this.size = 0;     // 큐의 크기
  }

  enqueue(value) {
    const newNode = new Node(value);
    if (!this.first) {
      this.first = newNode;
      this.last = newNode;
    } else {
      this.last.next = newNode;
      this.last = newNode;
    }
    this.size++;
    return this;
  }

  dequeue() {
    if (!this.first) return null;
    const removedNode = this.first;
    if (this.first === this.last) {
      this.last = null;
    }
    this.first = this.first.next;
    this.size--;
    return removedNode.value;
  }

  peek() {
    if (!this.first) return null;
    return this.first.value;
  }

  isEmpty() {
    return this.size === 0;
  }

  getSize() {
    return this.size;
  }
}

// 사용 예시
const queue = new LinkedListQueue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);

console.log(queue.peek());    // 10
console.log(queue.dequeue()); // 10
console.log(queue.getSize()); // 2
console.log(queue.isEmpty()); // false
console.log(queue.dequeue()); // 20
console.log(queue.dequeue()); // 30
console.log(queue.isEmpty()); // true

이렇게 구현된 큐는 링크드 리스트를 사용하여 동적 크기를 가지며, 요소의 추가와 제거가 O(1) 시간 복잡도로 이루어집니다. 이는 큐의 효율적인 동작을 보장합니다.