[JavaScript] Array vs Queue vs Deque

Array 이대로 알고리즘에 활용해도 될까?

자바스크립트를 사용한 알고리즘 풀이에서 Queue를 구현하기보다는 Array를 사용하곤 했다.

자바스크립트에서 Array는 기본 배열 메서드(push, pop, unshift, shift)를 통해 Queue를 구현하지 않아도 FIFO로 사용이 가능하기 때문에, 간단히 풀이할 때는 array를 활용하곤 했으나, 시간복잡도 측면에서 좋지 않을 것이라 생각이 들었다.

📌 자료구조의 가장 앞 데이터 삭제하기(Dequeue)

다시 생각해보더라도 array에서 push와 pop의 경우는 시간복잡도가 O(1)으로, 배열의 마지막에 데이터를 추가하거나 빼기만 하면 되기 때문에 간단하다. 하지만 queue의 속성인 FIFO를 활용하기 위해 가장 앞에 있는 데이터를 제거할 때 array는 shift 메서드를 사용하면 시간 복잡도가 O(n)이 된다. array 내에 데이터가 어마어마할 경우 시간이 무한이 증대되는 것이다.

 

우선 class를 활용하여 queue를 만들어보자.

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
    this.size = 0;
  }

  add(value) {
    this.storage[this.rear] = value;
    this.rear++;
    this.size++;
  }

  popleft() {
    let tmp;
    if (this.front === this.rear) {
      tmp = this.storage[this.front];
      delete this.storage[this.front];
      this.front = 0;
      this.rear = 0;
      this.size--;
    } else {
      tmp = this.storage[this.front];
      delete this.storage[this.front];
      this.front++;
      this.size--;
    }
    return tmp;
  }
}

object에 각각의 데이터를 저장하며 새로운 데이터가 입력될 때마다 rear를 증가시켜 key, value 형태로 유지시켰다. 

그리고 popleft를 통해 데이터를 제거할 경우 front를 증가시켜 다음 데이터를 가리키도록 하였다.

 

이제 가장 먼저 들어온 데이터를 제거해보도록 하자.

 

테스트를 위한 방법은 다음과 같다.

1. loop 변수에 100,000(십만)이라는 수를 할당하고, 반복문을 통해 데이터를 array와 queue에 데이터를 추가한다.

2. array의 shift, queue의 popleft 메서드를 사용하여 데이터를 제거한다.

3. 이 과정의 시간을 측정한다.

function arrayTest() {
  const q = [];
  for (let i = 0; i <= loop; i++) {
    q.push(i);
  }
  for (let i = 0; i <= loop; i++) {
    q.shift();
  }
}

function queueTest() {
  const q = new Queue();

  for (let i = 0; i <= loop; i++) {
    q.add(i);
  }
  for (let i = 0; i <= loop; i++) {
    q.popleft();
  }
}

console.time("Array Time Measure");
arrayTest();
console.timeEnd("Array Time Measure");

console.time("Queue Time Measure");
queueTest();
console.timeEnd("Queue Time Measure");

결과는 다음과 같다.

array와 queue 모두 데이터를 추가하는 것은 O(1)의 시간복잡도를 가지기 때문에 큰 차이가 발생하지 않는다.

하지만 데이터를 제거하는 과정에서 앞서 array는 O(n)을, queue는 O(1)의 시간 복잡도를 가지기 때문에 100,000개의 데이터를 삭제하는 과정에서 100배의 시간 차이가 발생하게 되었다.

FIFO 자료구조를 활용하기 위해서는 반드시 queue를 구현해서 사용해야하는 이유이다.

📌 데이터를 자료구조의 맨 앞에 추가하고 앞의 데이터를 삭제한다면?

데이터를 앞에 추가하고, 앞에 데이터를 삭제하는 방법 또한 자바스크립트에서는 array로 활용이 가능하다. unshift 메서드로 데이터를 추가하고, shift를 통해 데이터를 제거하면 된다. 하지만 이때 데이터를 추가하는 과정에서 O(n)의 시간복잡도를, 데이터를 삭제하는 과정에서 역시 O(n)의 시간복잡도를 가지기 때문에 매우 비효율적이다. 

 

데이터를 앞에서 추가하고 삭제하기 위해서는 Deque 구조를 활용해야하므로 코드를 통해 구현부터 해보자.

const Deque = (() => {
  class Deque {
    constructor() {
      this.count = 0;
      this.front = null;
      this.rear = null;
    }

    put_front(value) {
      const node = new Node(value);
      if (!this.front) {
        this.front = node;
        this.rear = node;
      } else {
        const next = this.front;
        this.front = node;
        this.front.next = next;
        next.prev = node;
      }
      return ++this.count;
    }

    get_front() {
      if (!this.front) {
        return false;
      }
      const data = this.front.data;
      this.front.prev = null;
      this.front = this.front.next;
      this.count--;
      return data;
    }

    put_rear(value) {
      const node = new Node(value);
      if (!this.front) {
        this.front = node;
        this.rear = node;
      } else {
        node.prev = this.rear;
        this.rear.next = node;
      }
      this.rear = node;
      return ++this.count;
    }

    get_rear() {
      if (!this.front) {
        return false;
      }
      let temp = this.rear;
      temp.prev.next = null;
      this.rear = temp.prev;
      temp = null;
      this.count--;
    }

    front() {
      return this.head && this.head.data;
    }

    rear() {
      return this.rear && this.rear.data;
    }
  }
  class Node {
    constructor(data) {
      this.data = data;
      this.next = null;
      this.prev = null;
    }
  }
  return Deque;
})();

출처: https://takeu.tistory.com/90

해당 블로그를 통해 코드를 참고하여 deque를 구현하였다.

 

데이터를 추가하기 위해 array의 unshift, deque의 put_front 메서드를 사용하여 데이터 추가만 해보도록 한다.

function arrayUnshiftTest() {
  const q = [];
  for (let i = 0; i <= loop; i++) {
    q.unshift(i);
  }
}

function dequeUnshiftTest() {
  const deque = new Deque();
  for (let i = 0; i <= loop; i++) {
    deque.put_front(i);
  }
}

console.time("Array Unshift Time Measure");
arrayUnshiftTest();
console.timeEnd("Array Unshift Time Measure");

console.time("Deque Unshift Time Measure");
dequeUnshiftTest();
console.timeEnd("Deque Unshift Time Measure");

테스트 시간을 측정해본 결과는 다음과 같다.

100,000개의 데이터를 추가하는 과정에서 이미 100배의 시간차가 발생했다. 추가된 데이터를 제거하는 결과를 보지 않아도 차이가 상당하다. 이제 array의 unshift, deque의 get_front 메서드를 활용하여 데이터를 제거해보도록 한다.

function arrayUnshiftTest() {
  const q = [];
  for (let i = 0; i <= loop; i++) {
    q.unshift(i);
  }
  for (let i = 0; i <= loop; i++) {
    q.shift();
  }
}

function dequeUnshiftTest() {
  const deque = new Deque();
  for (let i = 0; i <= loop; i++) {
    deque.put_front(i);
  }
  for (let i = 0; i <= loop; i++) {
    deque.get_front(i);
  }
}

 

측정 결과는 200배 가까운 시간 차가 발생한 것을 확인했다.

이를 토대로 데이터를 앞에서 추가하고 앞의 데이터를 삭제하는 경우에도 자바스크립트의 array 대신 deque 자료 구조를 활용해야 한다는 것을 알 수 있다.

결론

FIFO 자료구조를 활용하기 위해서는 array 대신 queue를 활용 할 것

앞, 뒤로 데이터가 추가되고 삭제되는 자료구조의 경우에도 array 대신 deque를 활용할 것

(다른 언어에 내장되지 않은 기능이 많아, 알고리즘 풀이에 힘이든건 안 비밀)