자료구조 큐(queue) 구현하기 (JS)

REASON·2022년 10월 13일

queue 자료구조 큐

자료구조

목록 보기

14/15

큐는 선입선출 (FIFO : First In First Out) 방식으로 먼저 넣은 데이터가 먼저 나오는 자료구조이다.

큐에 원소 추가, 제거 O(1)
큐의 맨 앞, 맨 뒤 원소 확인 O(1) 만큼의 시간 복잡도를 가진다.

자바스크립트로 queue 구현하기

자바스크립트 배열 내장 메서드 없이 구현해보았는데 배열 내장 메서드를 활용해서 구현하면 조금 더 쉽게 구현할 수 있다.

function Queue() {
  this.q = [];
  this.head = 0;
  this.tail = 0;
}

큐 생성자 함수를 만들어주었다.
배열만으로도 충분했을 수도 있지만 현재 앞과 뒤 위치 인덱스를 포함한 head와 tail도 작성해주었다.

push

Queue.prototype.push = function (num) {
  this.q[this.tail++] = num;
};

큐에 push하는 경우 가장 맨 뒤에 요소가 추가되어야 한다.
배열 내장 메서드 push를 사용하면 귀찮은 코드를 조금 더 줄일 수는 있을 것이다.
일단 이번엔 내장 메서드 없이 구현해보았기 때문에 후위 연산자를 통해 tail 값을 조절해주었다.

pop

Queue.prototype.pop = function(){
  if(this.head === this.tail) return `삭제할 원소가 존재하지 않습니다.`;
  return this.q[this.head++];
}

head와 tail 값이 같은 경우 삭제할 원소가 존재하지 않는다로 판단하였다.
마찬가지로 배열 내장 메서드로만 구현했으면 배열이 빈 배열인지로 확인할 수 있었을 것 같다는 생각.
pop하는 경우 헤드의 위치를 한칸 앞으로 옮겨버리면 된다.

size

현재 큐의 사이즈를 반환하도록 하는 메서드이다.

Queue.prototype.size = function(){
  return this.tail - this.head;
}

tail에서 head를 빼면 현재 큐의 크기를 알 수 있다.

isEmpty

현재 큐가 비어있는지 T/F로 확인할 수 있는 메서드이다.

Queue.prototype.isEmpty = function () {
  if (this.head === this.tail) return true;
  return false;
};

마찬가지로 head와 tail의 크기가 같을 때 비어있다고 판단.

front

큐의 맨 앞 요소의 값을 반환하는 메서드

Queue.prototype.front = function () {
  if (this.head === this.tail) return `원소가 존재하지 않습니다.`;
  return this.q[this.head];
};

back

큐의 맨 뒤 요소를 반환하는 메서드

Queue.prototype.back = function () {
  if (this.head === this.tail) return `원소가 존재하지 않습니다.`;
  return this.q[this.tail - 1];
};

구현한 큐 테스트 해보기

let q = new Queue();
q.push(1);
q.push(2);
q.push(3);
q.push(4);
q.push(5);
q.push(6);
// console.log(q);
console.log(q.pop()); // 1
console.log(q.pop()); // 2
console.log(q.pop()); // 3
console.log(q.pop()); // 4
console.log(q.size()); // 2
console.log(q.isEmpty()); // false
console.log(q.front()); // 5
console.log(q.back()); // 6