[JS] 선형 자료구조 큐(Queue) 구현하기

큐(Queue)란?

가장 먼저 들어간 데이터가 먼저 나오는 FIFO(First In First Out) 기반의 선형 자료구조이다.

---

구현 메서드(method)

데이터 전체 획득

Queue.getBuffer()

비어 있는지 확인

Queue.isEmpty()

데이터 추가/삭제

Queue.enqueue()/Queue.dequeue()

첫 번째 데이터 조회

Queue.front()

사이즈 확인

Queue.size()

전체 삭제

Queue.clear()

---

 

 

큐(Queue)는 먼저 온 사람이 먼저 나가는 줄 서기와 같다고 볼 수 있다

이메일이나 메시지, 쇼핑몰 주문, 콜센터 전화 등 일상에서 많이 찾아볼 수 있다

---

큐 구현 - getBuffer(), isEmpty()

// 생성자 함수
function Queue(array) {
  this.array = array ? array : [];
}

// getBuffer() 구현 함수
Queue.prototype.getBuffer = function () {
  return this.array.slice();
};

// isEmpty() 구현 함수
Queue.prototype.isEmpty = function () {
  return this.array.length === 0;
};

let queue = new Queue([1, 2, 3]);
console.log(queue); // Queue { array: [ 1, 2, 3 ] }

let data = queue.getBuffer();
console.log(data); // [ 1, 2, 3 ]
console.log(data === queue.array); // false

console.log(queue.isEmpty()); // false

큐 구현 - enqueue(), dequeue()

// enqueue() 구현 함수
Queue.prototype.enqueue = function (element) {
  return this.array.push(element);
};

// dequeue() 구현 함수
Queue.prototype.dequeue = function () {
  return this.array.shift();
};

let queue = new Queue([1, 2]);
console.log(queue); // Queue { array: [ 1, 2 ] }

queue.enqueue(3);
queue.enqueue(4);
console.log(queue); // Queue { array: [ 1, 2, 3, 4 ] }

queue.dequeue();
console.log(queue); // Queue { array: [ 2, 3, 4 ] }
queue.dequeue();
console.log(queue); // Queue { array: [ 3, 4 ] }

큐 구현 - front(), size(), clear()

// front() 구현 함수
Queue.prototype.front = function () {
  return this.array.length === 0 ? undefined : this.array[0];
};

// size() 구현 함수
Queue.prototype.size = function () {
  return this.array.length;
};

// clear() 구현 함수
Queue.prototype.clear = function () {
  this.array = [];
};

let queue = new Queue([1, 2, 3, 4]);

queue.dequeue();
console.log(queue); // Queue { array: [ 2, 3, 4 ] }
console.log(queue.front()); // 2

console.log(queue.size()); // 3
queue.clear();
console.log(queue); // Queue { array: [] }
console.log(queue.size()); // 0

 

큐 최적화

- enqueue/dequeue 방식을 push/shift에서 index로 변경 shift : O(n), index : O(1)

// 생성자 함수
function Queue(array) {
  this.array = array ? array : [];
  this.head = 0;
  this.tail = array ? array.length : 0;
}

// enqueue()
Queue.prototype.enqueue = function (element) {
  // return this.array.push(element);
  return (this.array[this.tail++] = element);
};

// dequeue()
Queue.prototype.dequeue = function () {
  // return this.array.shift();
  if (this.tail === this.head) return undefined;

  let element = this.array[this.head];
  delete this.array[this.head++];
  return element;
};

let queue = new Queue([1, 2, 3]);

queue.dequeue();
console.log(queue); // Queue { array: [ <1 empty item>, 2, 3 ], head: 1, tail: 3 }

 

성능 측정(Benchmark)

- queue_1 : push/shift, queue_2 : index 성능 비교

function Queue_1(array) {
  this.array = array ? array : [];
}

Queue_1.prototype.enqueue = function (element) {
  return this.array.push(element);
};

Queue_1.prototype.dequeue = function () {
  return this.array.shift();
};

function Queue_2(array) {
  this.array = array ? array : [];
  this.tail = array ? array.length : 0;
  this.head = 0;
}

Queue_2.prototype.enqueue = function (element) {
  return (this.array[this.tail++] = element);
};

Queue_2.prototype.dequeue = function () {
  if (this.tail === this.head) return undefined;

  let element = this.array[this.head];
  delete this.array[this.head++];
  return element;
};

let queue_1 = new Queue_1();
let queue_2 = new Queue_2();
const count = 100000;

function benchmark(queue, enqueue) {
  let start = Date.now();
  for (let i = 0; i < count; i++) {
    enqueue ? queue.enqueue() : queue.dequeue();
  }
  return Date.now() - start;
}

console.log("enqueue queue_1: " + benchmark(queue_1, 1) + "ms"); // enqueue queue_1: 4ms
console.log("enqueue queue_2: " + benchmark(queue_2, 1) + "ms"); // enqueue queue_2: 4ms

console.log("dequeue queue_1: " + benchmark(queue_1, 0) + "ms"); // dequeue queue_1: 5358ms
console.log("enqueue queue_2: " + benchmark(queue_2, 0) + "ms"); // enqueue queue_2: 9ms