[자바스크립트] 큐(Queue) 자료구조 예시를 통해 쉽게 이해하기

[자바스크립트] 큐(Queue) 자료구조 예시를 통해 쉽게 이해하기

큐(Queue) 자료구조란?

큐(Queue)는 가장 먼저 들어온 데이터가 가장 먼저 나가는(선입선출, FIFO(First In First Out)) 자료구조입니다. 일상생활에서도 쉽게 접할 수 있는데요. 영화관에서 영화를 보러 들어가기 위해 대기하거나, 비행기를 탑승하기 위해 대기를 할 때 먼저 줄을 선 사람이 먼저 들어가는 경우가 바로 큐 자료구조와 같습니다.

큐(Queue) 자료구조 그림 예시

코드 구현 예시

굉장히 단순하게 구현할 경우 자바스크립트 배열 자료구조를 활용해서 쉽게 구현할 수 있습니다.

배열 활용 예시

배열의 push, pop, unshift, shift 메서드를 사용할 때 시간복잡도는 O(1)이지만, 데이터를 할당/제거 후 배열을 재구성해야되기 때문에 O(N) 복사 비용이 발생합니다. 그렇기 때문에 배열을 통해 구현할 경우 원래 큐에서 기대하게 되는 시간복잡도로 삽입/삭제를 처리할 수 없습니다.

// 배열로 구현한 예시
class Queue {
  constructor() {
    this.items = []
  }

  add(value) {
    this.items.unshift(value);
  }

  remove() {
    return this.items.pop();
  }
}

const queue = new Queue();

queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
queue.add(5);
// [ 5, 4, 3, 2, 1 ]

queue.remove();
// [ 5, 4, 3, 2 ]

연결리스트 활용 예시

해당 예시는 단일 연결리스트로 구현한 사례이기 때문에 추가(O(n)), 삭제(O(1)) 시간복잡도로 동작하지만, 양방향 연결리스트로 구현할 경우 추가, 삭제 모두 O(1) 시간복잡도로 구현할 수 있습니다.

참조: 연결리스트 구현하는 방법

const LinkedList = require('../LinkedList');

// 연결리스트로 구현한 예시
class Queue {
  constructor() {
    this.list = new LinkedList();
  }

  add(value) {
    this.list.addLast(value);
  }

  remove() {
    return this.list.removeFirst();
  }
}

const queue = new Queue();

queue.add(1);
queue.add(2);
queue.add(3);
queue.add(4);
queue.add(5);

queue.remove(); // LinkedList { root: Node { value: 2, next: Node { value: 3, next: [Node] } }, size: 0 }