자바스크립트에서 큐(Queue) 사용하기

pop()은 O(1), shift()는 O(n)

자바스크립트에서 배열을 사용하다 보면, pop()과 shift() 메서드로 배열의 원소를 제거할 수 있다. 일반적으로 pop()은 배열의 맨 뒤 원소를, shift()는 배열의 맨 앞 원소를 제거하는 메서드로 알려져 있다. 그런데, pop()과 shift()를 구글에서 찾다 보면, 시간복잡도 이야기가 늘 따라붙는다. pop()은 O(1) time에, shift()는 O(n) time에 수행된다는 점이다.

 

기존 구현방식: 배열에 역순으로 값 넣기

배열의 가장 뒤에서 원소를 뽑아내는 것이 효율적이므로, 나는 큐를 사용하는 경우에 역순으로 배열에 집어넣는 선택을 하고 큐를 사용하고 있었다. 이 방법은 큐의 길이를 동적으로 조정해줘야 하는 경우가 아니라면 꽤 간단히 구현하고 사용할 수 있는 방법이었다. 그래서 최초 구현 당시 아무 고민없이 구현하고 사용했다. 1-2-3-4-5 의 순서로 이루어진 데이터를 5-4-3-2-1 순서로 배열에 넣으면 pop() 메서드로 1을 꺼낼 수 있기 때문이다.

하지만 이 방식도 늘 좋은 것은 아니다. 큐의 크기가 변하면 길이를 조정해 주어야 하는 문제가 있고, FIFO 원칙이 직관적으로 드러나지 않아 유지보수에 어려움을 겪을 수 있어 보인다. 향후 개발의 번거로움을 줄이기 위해 새로운 방식을 찾아보기로 했다.

 

대안1: 스택(Stack) 두 개를 사용하여 FIFO 원칙 구현

스택은 push()와 pop()이 O(1) 타임에 동작하기 때문에 이를 두 개 사용하여 효율적인 큐를 만들 수 있다. 첫 번째 스택(stack1)은 원소를 큐에 넣을 때 사용하고, 두 번째 스택(stack2)은 원소를 큐에서 꺼낼 때 사용하는 방법이다. 원소를 큐에서 꺼낼 때, stack2가 비어 있으면, stack1의 모든 원소를 pop()하여 stack2에 push()하고, 그 후 stack2에서 원소를 pop()하여 꺼내는 방식이다. 이렇게 하면 두 스택을 이용해 큐의 앞부분에서 꺼내는 것처럼 동작하게 된다. 그럼 개별 원소 입장에서 생각해보면, stack1.pop() -> stack2.push() -> stack2.pop() 순서로 꺼내지므로 O(3)로 사실상 O(1)같이 동작할 수 있는 것이다.

class Queue {
  constructor() {
    this.stack1 = [];
    this.stack2 = [];
  }

  // 큐에 원소를 추가하는 메서드
  enqueue(value) {
    this.stack1.push(value);
  }

  // 큐에서 원소를 제거하고 반환하는 메서드
  dequeue() {
    if (this.stack2.length === 0) {
      // stack2가 비어 있으면 stack1의 모든 원소를 옮긴다
      while (this.stack1.length > 0) {
        this.stack2.push(this.stack1.pop());
      }
    }
    return this.stack2.pop();
  }

  // 큐가 비어 있는지 확인하는 메서드
  isEmpty() {
    return this.stack1.length === 0 && this.stack2.length === 0;
  }
}

 

대안2: Linked List를 이용한 Queue 클래스 구현

링크드 리스트를 사용하면, 맨 앞에서 원소를 제거하는 dequeue()와 뒤에 원소를 삽입하는 enqueue() 모두 O(1) 시간복잡도를 유지할 수 있다. 성능을 더욱 최적화해야 하는 경우에는 링크드 리스트를 사용하는 것이 좋아 보인다.

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

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
  }

  enqueue(value) {
    const newNode = new Node(value);
    if (!this.rear) {
      this.front = this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }
  }

  dequeue() {
    if (!this.front) return null;
    const value = this.front.value;
    this.front = this.front.next;
    if (!this.front) this.rear = null;
    return value;
  }

  isEmpty() {
    return !this.front;
  }
}

 

Linked List를 이용한 Queue 구현이 O(n) 타임 피하기라는 원래의 목적과, 클래스화를 통한 유지보수 용이성 개선이라는 목적을 모두 달성할 수 있어서 이 방식으로 가기로 마음먹었다. 코드 수정하러 가자.