큐는 먼저 들어간 데이터가 먼저 나오는 자료구조입니다.

개념

FIFO

First In First Out

스택과 마찬가지로 큐도 삽입하는 연산을 push, 꺼내는 연산을 pop이라고 합니다.

동작 과정

빈 큐를 하나 선언합니다.

2, 5를 삽입해봅시다. FIFO 규칙에 의해서 2는 5보다 뒤에 있게 됩니다.

여기서 pop을 해봅시다. 5가 아닌 2가 먼저 나오는 것을 보실 수 있어요. pop을 한 번 더 진행하면 5가 빠져나옵니다.

다양한 분야에서 사용되는 큐

먼저 들어온 것을 먼저 처리하는 큐의 동작 방식은 프로그래밍에서 굉장히 많이 활용됩니다. 다음과 같은 사례들이 있습니다.

• 작업 대기열 : 네트워크 통신을 할 때 다수의 클라이언트에서 서버에 작업을 요청하면 서버는 요청이 들어온 순서대로 작업을 처리합니다.
• 이벤트 처리 : 어떤 애플리케이션이나 시스템에서 사용자의 이벤트, 예를 들어 키보드 입력이나 마우스 움직임을 처리할 때 큐를 활용할 수 있습니다.

큐의 ADT (Abstract Data Type)

테이블에 정의된 상태, 연산을 기반으로 ADT를 그려보면 다음과 같아요.

INFO

front와 rear가 -1인 것을 주목해주세요. front는 큐의 앞, rear는 큐의 뒤를 뜻하는데요. front를 이용해서 데이터를 빼고 rear를 통해서 데이터를 더하는 구조입니다. 아무런 데이터가 없다면 큐의 앞, 뒤 모두에 데이터가 없다는 것을 표현해줘야 하는데요. 이를 위해 -1을 사용합니다.

큐에 데이터를 추가하는 경우 다음과 같이 표현할 수 있어요.

1. 먼저 큐가 가득 찼는지 확인합니다.
   1. 가득 찼다면 종료
   2. 가득차지 않았다면 rear를 1 높혀주고 rear의 위치에 데이터를 넣습니다.

큐에서 데이터를 제거하면 다음과 같이 표현할 수 있어요

1. 큐가 비었는지 확인합니다.
   1. 비었다면 종료
   2. 비어있지 않다면 front를 1 높혀줘서 isEmpty를 다음에 실행했을 때 true가 되도록 합니다.

front를 이용해서 실제 데이터를 삭제하지 않지만 데이터를 삭제한 것처럼 관리하는 것이죠.

선형 큐의 한계

선형 큐를 이용한 방식은 구조적으로 front의 다음부터 rear까지의 데이터를 관리하는 것을 볼 수 있어요. front와 front 이전 위치의 데이터는 사용할 수 없기 때문에 비효율적입니다.

현재 선형인 구조를 원형으로 만들면 공간을 계속 재활용하게 만들어 이 문제를 해결할 수 있게 됩니다. 원형으로 된 구조의 큐를 원형 큐라고 합니다. 공간을 재활용하여 메모리 공간을 효율적으로 사용할 수 있죠.

JS로 큐 구현

큐를 구현하는 방법에는 3가지가 있습니다.

1. 배열의 push, shift로 큐 흉내내기
2. 배열을 이용하여 큐를 구현하기
3. 연결 리스트를 이용하여 큐를 구현하기

자세히 알아봅시다.

배열의 push, shift로 큐를 흉내

큐의 FIFO의 구조는 흉내낼 수 있지만 배열의 메소드 shift는 O(n)의 시간 복잡도를 가지고 있기 때문에 Queue의 pop의 시간복잡도O(1)보다 느립니다.

shift 시간 복잡도

JS에서 배열은 동적 배열입니다. 메모리 공간 상으로 첫번째 원소를 기준으로 뒤쪽 공간에 다음 원소들을 생성합니다. 이 원리에 의해서 push 메소드를 실행하게 되면 메모리 공간 뒤쪽에 원소를 추가하기만 하기 때문에 O(1)의 시간 복잡도를 갖습니다.

하지만 shift로 메모리 공간의 첫번째 원소를 없애버리게 되면 두번째 원소부터 끝 원소까지 이전 원소로 한 칸씩 이동하는 동작을 하게 됩니다. 이 때문에 O(n)이라는 시간 복잡도를 가지게 됩니다. ( 참고: https://codefug.github.io/posts/2025-05-24 )

// 배열 생성
const queue = [];

queue.push(1);
queue.push(2);
queue.push(3);

const firstItem = queue.shift();
console.log(firstItem); // 1

queue.push(4);
queue.push(5);

firstItem = queue.shift();
console.log(firstItem); // 2

배열을 이용하여 큐 구현

클래스의 프로퍼티로 배열을 넣고 이를 front와 rear로 제어하는 방식으로 큐를 구현할 수 있습니다.

class Queue {
  items = [];
  front = 0;
  rear = 0;

  push(item) {
    this.items.push(item);
    this.rear++;
  }

  pop() {
    return this.items[this.front++];
  }

  isEmpty() {
    return this.front === this.rear;
  }
}

언뜻 보기에는 잘 구현된 큐로 볼 수 있으나 rear와 front가 계속해서 증가하고 배열 메모리도 계속해서 증가하는 문제가 있어요. 완벽한 구현을 위해서는 연결 리스트를 활용해야 합니다.

연결 리스트를 이용하는 방식

JS에서는 연결 리스트를 기본 제공하지 않아요. 그래서 직접 구현해야 합니다. ( 시간 복잡도를 줄이는 멋진 개발자가 되기 위해선 알아야 합니다. )

// 노드 하나를 정의합니다. 연결 리스트는 이 노드를 하나의 값으로 취급하여 연결한 리스트에요.
class Node {
  constructor(data) {
    this.data = data; // 인스턴스의 현재 값
    this.next = null; // 다음 값
  }
}

// Node를 사용할 Queue입니다.
class Queue {
  // head, tail, size를 초기화합니다.
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  // 노드를 추가해줍니다.
  push(item) {
    // newNode를 만들어서 두가지 경우의 수를 처리합니다.
    const newNode = new Node(item);

    // 1. 첫 노드일 경우: head와 tail을 여기에 연결해줍니다.
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
      // 2. 첫 노드가 아닐 경우: tail과 새 노드를 연결해줍니다.
    } else {
      // 현재 tail의 다음값을 newNode로 하고
      this.tail.next = newNode;
      // 현재 tail을 newNode로 바꿔줍니다.
      this.tail = newNode;
    }

    this.size++;
  }

  // 지울 노드를 꺼내고 반환해줍니다.
  pop() {
    // 데이터가 없다면 null을 반환하고 끝냅니다.
    if (!this.head) {
      return null;
    }

    // 데이터가 있다면 반환할 노드를 미리 removeNode에 저장해놓고
    const removeNode = this.head;
    // head를 다음 값으로 이동시킵니다.
    this.head = this.head.next;

    // 만약 다음 값이 null이었다면 데이터가 비었으므로 tail도 초기화시켜줍니다.
    if (!this.head) {
      this.tail = null;
    }

    // 배열의 크기를 줄여주고
    this.size--;

    // 미리 저장했던 removeNode를 꺼내줍니다.
    return removeNode.data;
  }

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

이제 잔여 메모리 공간 문제와 시간 복잡도 문제를 해결한 멋진 개발자가 되었습니다.

참고 문헌

https://product.kyobobook.co.kr/detail/S000213641007

SUMMARY

알고리즘은 꾸준히 공부해주지 않으면 개념들이 유독 빠르게 사라지는 것 같아요. 사라지면 다시 채워넣을 수 있도록 꾸준히 공부해보겠습니다. 잘못된 지식이 있다면 댓글 부탁드려요!

읽어주셔서 감사해요.