큐 (Queue)

큐는 데이터가 들어온 순서대로 처리되는 선입선출(FIFO, First-In First-Out) 구조를 가진 선형 자료구조이다.
가장 먼저 들어온 데이터가 가장 먼저 나가는, 마치 은행 창구나 놀이공원에서 줄을 서는 것과 같은 방식이다.

🔗 Queue 개념 설명 영상

큐는 언제 사용할까 ?

스택은 되돌아가기나 실행 취소처럼 역순으로 처리하는 작업에 특화되어 있다면, 큐는 순서가 중요한 작업들을 처리하는 데 사용된다.

• 버퍼 (Buffer)
  데이터 처리 속도 차이를 조절할 때 사용된다.
  예를 들어, 유튜브 동영상을 볼 때 스트리밍 데이터가 CPU 처리 속도보다 빠르게 들어온다.
  이때 큐는 데이터를 임시로 저장해두고, CPU가 처리할 수 있을 때 순서대로 꺼내 쓸 수 있게 하여 영상이 끊기지 않게 한다.
• 너비 우선 탐색 (BFS, Breadth-First Search) 그래프나 트리 구조에서 시작점과 가까운 노드부터 순서대로 탐색할 때 사용된다.
  방문할 노드들을 큐에 넣어두고, 큐에서 꺼내는 순서대로 탐색을 진행하면 너비 우선 탐색이 된다.
• 작업 대기열 프린터 인쇄 목록, 운영체제의 프로세스 스케줄링, 메시지 큐(MQ) 시스템 등 여러 작업 요청을 받은 순서대로 처리해야 할 때 큐가 핵심적인 역할을 수행한다.

큐의 핵심 용어와 구조

큐는 데이터의 삽입과 삭제가 양쪽 끝에서 각각 일어나며, 이때 각 끝을 가리키는 용어가 있다.

• front: 큐의 가장 앞부분, 데이터가 나가는(dequeue) 출구이다.
• rear: 큐의 가장 뒷부분, 데이터가 들어오는(enqueue) 입구이다.

큐는 들어올 때 rear로 들어오지만, 나올 때는 front부터 빠지는 특성을 가진다.
접근 방법은 이처럼 가장 첫 원소와 끝 원소로만 가능하다.

큐의 주요 연산

연산	설명
enqueue()	큐의 rear 부분에 새로운 데이터를 넣습니다.
dequeue()	큐의 front 부분에서 데이터를 뺍니다.
isEmpty()	큐가 비어있는지 확인합니다.
isFull()	(고정 크기 배열 구현 시) 큐가 꽉 차 있는지 확인합니다.
peek() / front()	front에 있는 데이터를 제거하지 않고 확인만 합니다.

자바스크립트로 Queue 구현하기

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

// 연결 리스트 기반 큐 클래스 정의
class Queue {
  constructor() {
    this.head = null; // 큐의 가장 앞 (front)
    this.tail = null; // 큐의 가장 뒤 (rear)
    this.size = 0;
  }

  // 데이터 추가
  enqueue(data) {
    const newNode = new Node(data);
    if (this.isEmpty()) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
  }

  // 데이터 제거
  dequeue() {
    if (this.isEmpty()) {
      return '큐가 비어있습니다.';
    }
    const removedData = this.head.data;
    this.head = this.head.next;
    this.size--;
    if (this.isEmpty()) {
      this.tail = null;
    }
    return removedData;
  }

  // 큐의 가장 앞 데이터 확인
  front() {
    if (this.isEmpty()) {
      return '큐가 비어있습니다.';
    }
    return this.head.data;
  }

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

  // 큐를 보기 쉽게 출력하는 헬퍼 함수
  printQueue() {
    let current = this.head;
    let str = 'FRONT -> ';
    while (current) {
      str += `${current.data} -> `;
      current = current.next;
    }
    str += 'REAR';
    console.log(str);
  }
}

const queue = new Queue();
queue.enqueue(10);
queue.enqueue(20);
queue.enqueue(30);
queue.printQueue(); // FRONT -> 10 -> 20 -> 30 -> REAR

console.log('Dequeue:', queue.dequeue()); // Dequeue: 10
queue.printQueue(); // FRONT -> 20 -> 30 -> REAR

console.log('Front:', queue.front()); // Front: 20