[자료구조] JS로 구현하는 큐 (Queue)

Intro

미루고 미루던 자바스크립트로 큐를 구현해야하는 순간이 오고야 말았다. 알고리즘 문제를 풀다 보면 큐(Queue) 자료구조를 이용해서 문제를 해결하는 경우를 종종 만날 수 있다. 대표적으로 BFS 알고리즘을 적용할 때 또는 우선순위 큐 등이 있다.

다른 언어의 경우는 보통 내장 라이브러리에 큐를 제공하고 있다. 대표적으로 JAVA의 경우에는 java.util.Queue를 임포트하여 사용할 수 있고 파이썬의 경우 collections에서 deque를 임포트 해 큐처럼 사용할 수 있다. 그러나 자바스크립트는 당연히 큐와 관련된 객체가 내장되어 있지 않다. 따라서 큐를 이용하기 위해서는 직접 자료구조를 작성해야 할 필요가 있다.

앞서서 힙(Heap) 구조 역시 자바스크립트의 ES6에 도입된 클래스(class)를 이용하여 구현한 적 있는데 이와 유사하게 큐 역시 클래스를 사용하여 구현해보자.

자바스크립트는 프로토타입 기반 언어이고 클래스가 정식 문법에 도입되기 전에는 프로토타입 체인으로도 추가 기능을 구현하곤 했지만, 여기서는 클래스를 이용해서 구현해보자.

굳이 구현이 필요한가?

사실 자바스크립트에서 Queue를 독립적으로 자체 제공하지는 않지만 배열(Array)를 이용하여 큐의 기능을 흉내낼 수 있다. 자바스크립트의 배열 내장 메서드 중에는 shift() 라는 메서드가 있는데, 이는 배열의 가장 앞에 있는 원소부터 하나씩 제거하는 기능을 수행한다. 즉 배열의 pop() 메서드의 역방향이라고 볼 수 있다.

큐의 순서는 FIFO(First In First Out) 원칙을 고수하기 때문에 사실 shift() 메서드를 이용하면 해당 원칙을 준수하며 데이터 삽입/제거가 가능하다. 그러나 해당 방식은 근본적인 문제가 있다.

바로 배열을 활용해서 FIFO 원칙을 적용한다는 점인데, 이 부분에서 원래 큐 자료구조의 시간복잡도와 상당한 차이가 발생하게 된다. 배열을 활용한 큐의 구조에서 상당한 시간이 소요되는 이유는 shift() 메서드를 통해 원소를 앞에서 부터 하나씩 제거할 때, 나머지 배열 원소에 대한 재정렬이 이루어져야 하기 때문이다.

shift() 메서드의 내부 로직은 다음과 같다.

• 배열의 첫 번째 원소 arr[0]에 접근하여 해당 값을 반환하고 배열에서 제거
• 기존 배열에서 첫 번째 원소 arr[0]의 값은 사라졌지만 공간은 차지하고 있음
• shift() 메서드는 계속해서 arr[0]에 접근할 예정
• 따라서 나머지 배열의 원소들을 앞으로 한 칸씩 당겨주는 과정 필요

즉 마지막의 과정에 대한 연산이 추가적으로 요구되기 때문에, 이에 대한 추가적인 시간이 더 소요되는 것이다. 밑에서 살펴보겠지만 기본적으로 큐 자료구조에서는 연결 리스트를 사용하여 첫 번째 원소에 접근하는 시간을 O(1)로 해결할 수 있는 반면, 배열을 이용한 경우에는 배열 전체를 한 번 순회하면서 위치 재조정을 하는 시간까지 추가로 필요하기 때문에 다른 언어에서의 큐 자료구조보다 더 많은 시간이 소요된다.

보통 큐를 활용해서 알고리즘 문제를 풀어야 하는 경우 배열을 이용하더라도 대부분 통과하는 경우가 많다. 문제에서 주어진 제한 시간이 아주 빡빡하지 않고, 데이터의 양 역시 아주 큰 값이 아니라면 별 문제가 없을 수도 있다. 그러나 시간 복잡도를 매우 세세하게 관리해야 하는 경우라던가, 데이터의 양이 매우 큰 경우에는 이 같은 방식으로는 통과할 수 없는 경우가 종종 있다. 따라서 이런 경우에 직접 구현한 큐를 이용하여 더 빠른 시간 복잡도로 문제에 접근한다면 통과할 수 있는 확률이 올라갈 것이다.

큐(Queue)란?

큐는 사실 스택(Stack)을 배울 때 함께 언급될 정도로 매우 유명하면서 또 기초적인 자료구조이기 때문에 대표적인 특성 몇 개만 파악하도록 하자.

앞서 이야기 한 바와 같이 큐는 FIFO 원칙하에 운용되는 자료구조이다. 즉 가장 먼저 들어온 데이터가 가장 먼저 빠져나가야 하는 구조이며, 이는 스택과 상반되는 순서를 가진다.

일상에서는 큐의 순서를 조금 더 많이 접할 수 있다. 사실 일상에서 접하는 선착순과 관련된 모든 분야가 큐의 자료 흐름과 동일한 순서를 가진다고 볼 수 있다. 가장 먼저 도착한 사람이 가장 먼저 서비스를 받는 것은 선착순이라는 개념 하에 지극히 당연한 논리이기 때문이다.

따라서 사실 FIFO 순서만 지키면 큐의 역할을 수행할 수 있다. 때문에 위에서 살펴본 바와 같이 배열을 이용해서 큐의 기능을 할 수 있었다. 이때 문제가 된 것은 시간 복잡도와 관련된 점이었고, 따라서 우리는 이 순서를 지킴과 동시에 배열보다 더 빠른 접근이 가능하도록 구현하는 것이 필요하다.

어떤 요소에 접근할 때 O(1)의 시간이 소요되는 방법은 여러가지가 있다. 앞서 살펴본 배열에서 첫 번째 원소 arr[0]에 접근하는 것 자체도 사실은 O(1)의 시간이 요구된다. 그러나 이때는 나머지 배열 원소에 대한 위치 조정이 추가적으로 요구되었기 때문에 적합하지 않다.

자바스크립트에서 객체(Object)는 key-value의 구조로 사용할 수 있으며, key 값을 통해 O(1) 시간으로 접근할 수 있다. 즉 일종의 해시(Hash)로 활용이 가능한데 이를 통해 큐를 구현해보자.

큐에서 핵심이 되는 포인터는 두 개가 있다. 바로 front와 rear라는 용어로 많이 소개가 되곤 하는데, 이는 각각 큐에서 가장 처음의 원소를 가리키고 있는 포인터 front, 그리고 가장 마지막 원소를 가리키고 있는 포인터 rear 라고 볼 수 있다. 이 둘을 이용한다면 큐에 어떤 값을 삽입/제거 했을 때 나머지 요소들에 대한 추가적인 작업이 필요하지 않다.

그 원리는 매우 간단하다. front 는 항상 큐에서 가장 처음의 원소의 값(또는 위치)를 가리키고 있다. 이 값은 오직 큐에서 값을 하나 꺼내올 때 변동될 것이다. 큐에서 값을 하나 꺼내오면 첫 번째 원소가 제거되고, 그 다음에 위치한 원소가 첫 번째 원소가 된다는 점을 기억하자. 때문에 이 경우 front의 위치는 기존 위치 + 1로 이동하게 될 것이다.

rear는 항상 마지막 원소의 값(또는 위치)를 가리키고 있다. 따라서 큐에 어떤 데이터가 삽입되면 항상 rear의 위치는 기존 위치 + 1로 이동하게 될 것 이다. 이처럼 두 개의 포인터로 큐의 처음과 끝을 관리하게 되면 우리는 항상 O(1)의 시간 안에 큐의 첫 원소를 가져올 수 있을 것이다. 각각 큐의 기능을 하나씩 세부적으로 살펴보도록 하자.

사실 투 포인터를 사용한다면 위처럼 꼭 객체(Object)가 아니라 배열(Array)을 사용해서도 O(1)의 접근 시간을 보장할 수 있다. 다만 이 경우엔 배열의 첫 번째 원소를 제거하더라도 이미 선언된 공간은 undefined라는 값이 차지하고 있기 때문에 별도의 과정 없이는 공간 최적화가 이루어지지 않을 수 있다.

큐 초기화

클래스를 이용하여 큐를 구현하기로 했기 때문에 ES6에서 도입된 class를 사용하도록 하자. 먼저 constructor 메서드를 통해 초기 큐의 구조와 값을 선언할 수 있다. 앞서 우리는 객체(Object)에 값을 저장하고, 두 개의 포인터 front와 rear를 사용하기로 했으므로 이들에 대한 값을 초기화 해주도록 하자.

이때 두개의 포인터 초기값은 동일하게 지정하자. 아직 데이터가 들어오지 않았기 때문에 모두 같은 위치를 바라보고 있는 것이다. 그리고 배열의 인덱스처럼 포인터의 위치는 0부터 시작한다고 가정하자.

class Queue {
  constructor() {
    this.storage = {};	// 값을 저장할 객체
    this.front = 0;	// 첫 원소를 가리킬 포인터
    this.rear = 0;	// 마지막 원소를 가리킬 포인터
  }
  
  // ...
}

크기 구하기

다른 언어에서 임포트 하여 사용하는 큐의 경우, 언어마다 그리고 임포트 하는 클래스마다 세부적으로 제공하는 기능이 조금씩 다를 수 있다. 큐를 구현하는 방법은 여러가지이며, 또 큐 자체도 여러가지 종류로 구분되기 때문이다.

하지만 기본적으로 현재 큐의 크기를 구할 수 있는 메서드는 모두 제공하는 편이다. 따라서 우리도 큐에 담긴 현재 크기를 리턴하는 메서드를 구현해보자.

우리는 큐에 담을 데이터를 객체를 사용한다고 했기 때문에 배열처럼 단순히 arr.length를 통해서는 그 값을 구하기 어렵다. 물론 객체를 배열로 바꾸는 객체 메서드 Object.keys/values/entries() 등을 이용하여 변환 후 length 프로퍼티를 통해 크기를 구할 수도 있다. 하지만 배열로 변환하는 과정은 O(N)의 시간복잡도가 소요되는 과정이다.

우리는 투 포인터를 사용하기 때문에 이를 이용해서 더 빠르게 큐의 크기를 구해줄 수 있다. 앞서 언급했듯이 각각의 포인터는 큐의 첫 원소의 위치와 마지막 원소의 위치를 가리키고 있다.

이때의 큐에 담겨있는 데이터의 개수는 총 10개가 되는 것을 알 수 있다. 이 10이라는 값은 rear - front + 1을 만족하는 것을 알 수 있다. 1을 더해주는 이유는 front가 0부터 시작한다고 앞서 정의했기 때문이다. 마지막 위치에서 첫 번째 위치를 빼주는 이유는 front의 값은 항상 큐에 제거 연산이 일어날 때 마다 위치가 변동되기 때문이다. 즉 아래와 같은 상황에서도 남아있는 데이터의 수를 계산해주기 위해서이다.

마지막으로 한 가지만 더 주의하도록 하자. 이처럼 큐에 데이터를 하나씩 계속 추출하다보면 front와 rear가 가리키는 지점이 같아지는 순간이 오게 된다. 이 때는 큐에 존재하는 데이터가 딱 1개인 상황인 경우를 말한다. 여기서 한 번 더 큐의 원소를 가져오게 되면 남아있는 데이터가 아무것도 없는 상황이 만들어진다.

front와 rear는 위의 경우처럼 서로 값이 같아지는 순간 데이터가 1개만 남아있다는 것을 의미할 수도 있으며, 반대로 아무 데이터가 없다는 것을 의미하기도 한다. 왜냐하면 위에서 초기 큐를 초기화 할 때 두 개의 포인터를 각각 0으로 같은 값을 가지도록 초기화 했기 때문이다.

아래에서 살펴보겠지만 큐에서 데이터를 하나 가져오고 나서 delete를 이용해 큐에서 해당 값을 제거해준다. 즉 위 상황에서 두 포인터가 같은 지점을 바라보고 있는 상황은 데이터가 딱 1개 남았을 경우인데, 여기서 데이터를 하나 꺼내오게 되면 front의 값은 1만큼 증가해 rear를 추월하게 되고 동시에 해당 값을 delete하여 제거한다. 즉 아직 rear의 위치는 변하지 않았다. 때문에 this.storage[rear]를 접근했을 때 undefined가 나온다면 이는 값이 들어있지 않은 상황이기 때문에 큐에 아무런 데이터가 없다는 것을 의미한다.

초기에 큐를 초기화 했을 때 역시 storage에는 아무런 데이터가 없기 때문에 this.storage[rear]는 undefined를 만족한다. 따라서 단순히 rear가 가리키는 위치에 데이터가 없다면 우리는 큐에 아무런 데이터가 없다는 것으로 간주할 수 있다.

class Queue {
  consturctor() { ... }
  
  // 크기 구하기
  size() {
    // rear가 가리키는 값이 없을 때가 아무 데이터가 없는 경우이다
    if (this.storage[rear] === undefined) {
      return 0;
    } else {
      // 그 외의 경우는 앞서 구한 공식으로 크기를 구할 수 있다
      return this.rear - this.front + 1;
    }
  }

데이터 추가

큐에 데이터가 삽입되는 경우를 생각해보자. 위에서 언급한 바와 같이 이때는 rear 포인터의 위치만 조정될 것이다. 데이터가 하나씩 들어올 때마다 rear 포인터는 당연히 이전위치 + 1이 되고 해당 위치에 들어온 데이터를 저장하게 될 것이다.

이때 데이터가 아무 것도 없을때를 주의하도록 하자. 데이터가 아무것도 없는 경우는 크게 두 가지 상황이 존재한다.

1. 큐를 처음 초기화 했을 경우 (두 포인터 모두 0)
2. 위에서와 같이 중간에 데이터를 모두 꺼내는 경우
   • 이땐 front + 1 === rear를 만족

데이터가 아무 것도 없을 때의 경우가 다음과 같이 크게 두 가지로 나뉜다. 각각의 경우를 고려해서 rear의 위치를 알맞게 재조정해주면 될 것이다. 그런데 이렇게 분기가 나뉘는 처리는 사실 좋은 접근 방법이 아니다. 해당 사례에서는 단순히 2가지 분기점밖에 없지만, 만약 해당 클래스를 확장해야 하는 경우 계속해서 분기점이 추가될 수 있다. 따라서 우리는 이를 하나의 경우로 통합해서 처리해주도록 하자.

바로 2번째 경우는 고려해주지 않는 방법이 있을 수 있다. 즉 두 포인터가 모두 0이 되는 상황으로 통일시켜 생각하도록 하자. 이는 데이터 추가에서 이루어지는 작업은 아니기 때문에 밑에서 조금 더 자세히 설명을 하겠지만, 만약 데이터를 꺼냈을 때 front와 rear가 같은 위치를 바라보고 있다면 이들의 값을 0으로 다시 초기화시켜 줄 수 있다. 이 시점은 결국 아무런 데이터가 없는 상황과 일치하기 때문이다. 즉 아무런 데이터가 없는 상황을 두 포인터가 모두 0을 바라보도록 재조정을 해줄 것이다.

따라서 큐에 아무런 데이터가 존재하지 않는 경우에는 자연스레 0번 위치에 데이터를 삽입하도록 하자. 이때 front와 rear의 위치는 아무런 변화가 없다는 것에 주의해야 한다. 아무런 데이터가 없을 때는 0번 위치에 데이터가 들어가게 될 것이고, 1개의 데이터만 있는 경우이기 때문에 front와 rear의 위치값은 동일하며 이는 곧 0번이기 때문이다.

따라서 다음과 같이 구현해주도록 하자.

class Queue {
  constructor() { ... }
  
  size() { ... }
  
  add(value) {
    // 큐에 데이터가 아무것도 없는 경우
    if (this.size() === 0) {
      // 0번 위치에 값을 넣고 포인터는 건드리지 않는다
      // 이때 ['0']으로 키를 설정한 이유는
      // 자바스크립트 객체 Object는 키 값으로 오직
      // 문자열과 Symbol만 허용하기 때문
      this.storage['0'] = value;
    } else {
      // 그 외의 경우에는 간단하게
      // rear 위치를 1만큼 늘리고 해당 위치에 값 삽입
      this.rear += 1;
      this.storage[this.rear] = value;
    }
  }

데이터 추출

다음으로 데이터를 꺼내는 경우를 생각해보자. 역시 위에서 언급한 바와 같이 front의 위치가 재조정될 것 이다. 그리고 위치를 재조정하기 전에 기존 위치에 담긴 값을 제거해주는 과정 역시 필요할 것이다.

그리고 삽입에서 살펴보았듯이 큐에 데이터가 존재하지 않게 되는 시점을 고려해주어야 한다. 이 시점은 큐에 데이터가 딱 1개 존재하고 있을때 데이터를 꺼내오는 경우이다. 그리고 우리는 앞서 큐에 데이터가 딱 1개 존재하는 경우는 front와 rear의 값이 동일한 경우라는 점을 살펴보았다.

따라서 두 포인터의 값이 동일한 경우엔 이를 다시 초기화시켜 두 포인터의 값을 0으로 유지시켜 주도록 하자. 이 과정을 통해 우리는 데이터를 삽입하는 과정에서, 큐에 아무런 데이터가 없을 경우 무조건 0번 위치부터 데이터 삽입을 할 수 있도록 분기점을 통일시켜 줄 수 있다.

이때 사실 큐를 처음 초기화 하는 과정에서도 두 포인터의 값이 0으로 동일한 것을 알 수 있는데, 이 경우엔 데이터가 1개만 존재하는 것이 아니라 아무것도 존재하지 않는 경우기 때문에 위와 상충되는 것을 알 수 있다.

그렇지만 자바스크립트의 동적 언어 특성으로 존재하지 않는 값에 접근을 하더라도 undefined를 반환할 뿐 에러는 발생하지 않기 때문에 이에 대한 예외 처리를 해주지 않아도 상관없다.

큐에서 데이터를 추출하는 메서드의 용어는 다양화 되어 있는데 보통 삽입/추출에 enqueue/dequeue 라는 용어를 사용하기도 하고 단순히 add, insert/popleft 라는 용어를 사용하기도 한다. popleft는 기존 배열 내장 메서드 pop()이 우측에서 부터 데이터를 추출하기 때문에 그에 상반된 개념으로 popleft라고 호칭하는 것이다. 자바스크립트 역시 배열에 pop이라는 메서드 용어를 사용하므로 여기선 popleft 라는 이름으로 메서드를 정의했다. 이 부분은 본인에게 더 편한 용어가 있다면 어떠한 것으로 바꾸더라도 상관없다.

class Queue {
  constructor() { ... }
  
  size() { ... }
  
  add(value) { ... }
  
  popleft() {
    let temp;	// 첫 원소 값을 임시로 담을 변수
    // 두 포인터의 값이 같은 경우 (데이터가 1개 남은 경우)
    // 물론 초기 상태에서 아무런 데이터가 없는 상황일 수도 있으나
    // 이때 front의 값을 가져오고 제거하는 과정에서
    // 자바스크립트 특성 상 에러가 발생하지 않고
    // 두 포인터의 값을 계속 0으로 유지시켜 주기 때문에
    // 별도로 이 부분에 대한 처리를 해줄 필요는 없지만
    // 좀 더 호환성 높은 코드를 위해서는 사실 하는 편을 추천
    if (this.front === this.rear) {
      // 현재 front에 담긴 값을 가져오고
      // 항상 이 값을 delete 해주어야 한다
      temp = this.storage[this.front];
      delete this.storage[this.front];
      // 이 부분이 없었다면 이 시점에서 front는
      // rear의 값 보다 1보다 더 큰 역설에 빠지게 되므로
      // 데이터가 없는 경우를 다시 0으로 초기화
      this.front = 0;
      this.rear = 0;
    } else {
      // 현재 front에 담긴 값을 가져오고
      // 항상 이 값을 delete 해주어야 한다
      temp = this.storage[this.front];
      delete this.storage[this.front];
      this.front += 1;
    }
    return temp;
  }
}

전체코드

자바스크립트로 알고리즘을 풀다 보면 이렇게 직접 구현한 큐를 적용해야 하는 경우가 가끔 등장한다. 대표적인 예로 트리 트리오 중간값과 같은 문제가 있다. 물론 어떻게 접근하느냐에 따라 다른 방식으로도 시간 복잡도를 피해가는 방법이 있기는 하다.

사실 위에서 구현한 큐는 가장 대표적이고 단순한 기능만을 구현한 것이다. 다른 언어에서 제공하는 큐 자료구조의 경우는 이 외에도 첫 번째 원소의 값을 제거하지 않고 확인만 하는 peek()과 같은 메서드 역시 추가적으로 제공하고 있다. 이들의 기능만 잘 알고 있다면 위의 구조에서 해당 기능을 추가하는 것은 그리 어렵지 않으리라고 생각된다.

또한 위 구조에서는 어떤 값을 단순히 FIFO 구조로 가져오는것만을 신경쓰고, 이에 대한 것만 시간 복잡도 최적화가 되어있다. 정확히는 원래 배열을 통해 구현한 것에서 나머지 원소에 대한 재정렬을 생략한 것과 다를바가 없다. 연결 리스트의 형태가 아닌, 단순히 객체의 key-value를 통해 데이터의 접근이 이루어지고 있는데, 순차적인 접근을 보장하기 위해 key 값을 0부터 오름차순으로 증가하도록 선언하고 있다. 만약 해당 구조를 확장하면서 이 부분에 대해 신경쓰지 않는다면 FIFO 원칙이 망가질 수 있다.

그렇지만 알고리즘 풀이에서 시간 복잡도를 위해 큐의 기능이 필요한 경우에는 대부분 잘 작동할 것이다. 주석을 제외한 전체코드는 다음과 같다.

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  
  size() {
    if (this.storage[this.rear] === undefined) {
      return 0;
    } else {
      return this.rear - this.rear + 1;
    }
  }
  
  add(value) {
    if (this.size() === 0) {
      this.storage['0'] = value;
    } else {
      this.rear += 1;
      this.storage[this.rear] = value;
    }
  }
  
  popleft() {
    let temp;
    if (this.front === this.rear) {
      temp = this.storage[this.front];
      delete this.storage[this.front];
      this.front = 0;
      this.rear = 0;
    } else {
      temp = this.storage[this.front];
      delete this.storage[this.front];
      this.front += 1;
    }
    return temp;
  }
}