Javascript로 큐 Queue 구현하기

서론

큐는 선입선출인 자료구조로 원소를 넣고(enqueue) 빼는(dequeue) 동작을 O(1)의 시간복잡도로 수행할 수 있습니다.

javascript의 Array 자료구조를 사용하면 큐에 원소를 넣고 빼는 동작을 수행할 수 있습니다.

push 메서드를 통해 원소를 맨 뒤에 넣을 수 있고

shift 메서드를 통해 맨 앞의 원소를 뺄 수 있습니다.

하지만 shift 메서드는 O(1)의 시간복잡도로 수행되지 않습니다. (이유를 자세히 찾아보지는 않았지만 맨 앞의 원소를 뺀 후에 나머지 원소들을 한칸씩 땡겨오는 작업이 필요해서 라고 추측됩니다.)

그래서 큐가 필요한 알고리즘 문제를 풀 때 Array를 사용하면 시간초과가 나거나 오래걸리는 것을 볼 수 있습니다.

 

배열에 10만개의 원소를 넣고 빼는 간단한 테스트를 통해 Array의 성능을 알아보겠습니다.

let start;
let end;
const TEST_SIZE = 100000;
const array = [];

start = new Date();
for (let num = 1; num <= TEST_SIZE; num++) {
  array.push(num);
}
end = new Date();
console.log(`enqueue 소요 시간 : ${end - start}ms`);

start = new Date();
for (let num = 1; num <= TEST_SIZE; num++) {
  array.shift();
}
end = new Date();
console.log(`dequeue 소요 시간 : ${end - start}ms`);

// 결과
// enqueue 소요 시간 : 10ms
// dequeue 소요 시간 : 781ms

결과를 확인해보면 dequeue연산이 O(1)의 시간복잡도로 수행되지 않는것을 볼 수 있습니다.

큐의 맨 뒤에 원소를 넣는 enqueue,

큐의 맨 앞 원소를 빼고 반환하는 dequeue,

큐가 비어있는지 확인하는 isEmpty,

큐의 원소를 빼지 않고 맨 앞 원소를 반환하는 peek

연산을 가진 큐를 구현해 보겠습니다.

 

본론

array를 사용해서 구현하는 방법과 연결리스트의 형태로 구현하는 방법중에 연결리스트의 형태로 구현해봤습니다.

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

function Queue() {
  this.front = null;
  this.back = null;
  this.size = 0;

  this.enqueue = function (value) {
    const node = new Node(value);
    if (this.size === 0) {
      this.front = node;
      this.back = node;
    } else {
      this.back.next = node;
      this.back = node;
    }
    this.size++;
  };

  this.dequeue = function () {
    if (this.size === 0) {
      throw new Error("큐가 비었소");
    }
    const value = this.front.value;
    this.front = this.front.next;
    this.size--;
    if (this.size === 0) this.back = null;
    return value;
  };

  this.isEmpty = function () {
    return this.size === 0;
  };

  this.peek = function () {
    if (this.size === 0) return null;
    return this.front.value;
  };
}

 

결론

이제 10만개의 원소를 넣고 빼는 테스트를 통해 직접 구현한 큐의 성능을 확인해 보겠습니다.

let start;
let end;
const TEST_SIZE = 100000;
const array = [];
const queue = new Queue();

console.log("일반 array");
start = new Date();
for (let num = 1; num <= TEST_SIZE; num++) {
  array.push(num);
}
end = new Date();
console.log(`enqueue : ${end - start}ms`);

start = new Date();
for (let num = 1; num <= TEST_SIZE; num++) {
  array.shift();
}
end = new Date();
console.log(`dequeue : ${end - start}ms`);
console.log("--------------------");

console.log("Queue");
start = new Date();
for (let num = 1; num <= TEST_SIZE; num++) {
  queue.enqueue(num);
}
end = new Date();
console.log(`enqueue : ${end - start}ms`);

start = new Date();
for (let num = 1; num <= TEST_SIZE; num++) {
  queue.dequeue();
}
end = new Date();
console.log(`dequeue : ${end - start}ms`);

// 결과
// 일반 array
// enqueue : 3ms
// dequeue : 781ms
// --------------------
// Queue
// enqueue : 6ms
// dequeue : 3ms

직접 만든 큐에서 enqueue와 dequeue 연산이 O(1)에 수행되는 것을 확인할 수 있습니다.😄