ZeroCho Blog

안녕하세요. 이번 시간에는 큐에 대해 알아보겠습니다.

큐는 실생활에서 줄이라고 생각하시면 됩니다. 우리가 순서를 기다릴 때 줄을 서죠? 새로 온 사람은 줄 맨 뒤에 서고, 제일 앞 사람은 필요한 행동을 한 후 빠집니다. 이렇게 뒤에서 들어가고(enqueue) 앞에서 빠지는(dequeue) 구조입니다. 자바스크립트의 배열로 따지면 push(enqueue)와 shift(dequeue) 메소드만 있는 거라고 생각하시면 됩니다. 거기에 추가로 제일 앞의 데이터를 알 수 있는 front 메서드가 있습니다.

이제 코드로 큐를 만들어볼까요?

class Queue {
  count = 0;
  head = null;
  rear = null;
    
  enqueue(data) {
    const node = new Node(data);
    if (!this.head) {
      this.head = node;
    } else {
      this.rear.next = node;
    }
    this.rear = node;
    return ++this.count;
  };
    
  dequeue() {
    if (!this.head) { // stack underflow 방지
      return false;
    }
    const data = this.head.data;
    this.head = this.head.next;
    // this.head 메모리 클린
    --this.count;
    return data;
  };
    
  front() {
    return this.head?.data;
  }
}

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

const queue = new Queue();
queue.enqueue(1); // 1
queue.enqueue(3); // 2
queue.enqueue(5); // 3
queue.dequeue(); // 1
queue.front(); // 3

스택에는 제일 위를 가리키는 top만 있었다면 큐에는 맨 처음을 가리키는 head와 맨 끝을 가리키는 rear 두 개가 있습니다.

큐의 시간 복잡도, 공간 복잡도도 스택과 같습니다. 추가, 제거, 제일 앞 데이터 조회 모두 O(1)입니다. 공간 복잡도는 O(n)이고요.

특수한 큐도 있습니다. 순환 큐가 그 중 하나인데요. front와 rear가 연결되어 있습니다. 예를 들면 1, 2, 3의 데이터가 들어있는 큐가 있을 때 원래라면 3에서 끝나지만, 순환 큐는 rear인 3에서 다시 front인 1로 넘어갑니다. 코딩은 그냥 this.rear.next = this.front를 추가해주면 구현할 수 있습니다. 순환 큐가 사용되는 이유는 메모리 관리가 쉽기 때문인데 자바스크립트에서는 메모리를 알아서 정리해주기 때문에 그 효용성이 조금 떨어집니다. 

또 다른 큐로는 우선순위 큐가 있습니다. enqueue, dequeue는 같지만, enqueue할 때 제일 뒤에 넣는 게 아니라 우선순위 순서를 따져서 데이터를 넣습니다. 어떤 데이터가 우선순위가 높은지는 프로그래머가 직접 정해주면 됩니다. 문제는 우선순위 큐는 위와 같이 큐로 구현하면 데이터를 삽입하기 힘들다는 단점이 있습니다. 그래서 주로 힙이라는 자료구조를 사용해서 구하는데요. 힙을 알기 위해서는 또 트리를 알아야합니다.

다음 시간에는 트리(tree)에 대해 알아보겠습니다!