JavaScript 큐(Queue)

큐 (Queue)

 자바스크립트에서 큐는 구현되어 있지 않다... 직접 구현해야 한다. 큐를 구현하는 방법은 2가지가 있는데, 배열을 사용하는 방법과 연결 리스트를 사용하는 방법이 있다.

배열을 사용해서 큐 만들기

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
}

 배열 Queue를 만들고 인덱스를 가리키는 front와 rear는 모두 0으로 초기화 한다.

enqueue(newValue)

Queue.prototype.enqueue = function (newValue) {
  this.queue[this.rear++] = newValue;
}

 queue에 원소를 추가하는 것을 enqueue라고 한다. 배열 Queue에 원소를 추가할 때마다 rear의 값을 증가시킨다. front의 경우 추가할 때 변하지 않는다.

dequeue()

Queue.prototype.dequeue() = function (newValue) {
  const value = this.queue[this.front];
  delete this.queue[this.front];
  this.front += 1;
  return value;
}

 queue에서 원소를 추출하는 것을 dequeue라고 한다. 가장 첫 번째 요소가 반환된다. value는 첫 번째 노드를 삭제하기 전 첫 번째 노드의 값을 저장한다. queue의 첫 번째 원소는 삭제한다. 그리고 front의 값을 1 증가시켜 배열의 queue[front]가 아닌 queue[front + 1]이 front가 된다. 그리고 추출한 값을 리턴한다.

javascript에서 배열의 요소를 삭제할 때 delete 연산자를 사용할 수 있다. 단 배열의 길이는 그대로이며.(삭제 후 이동하지 않는다.) 배열의 요소를 빈 값으로 변경한다. 따라서 출력하면 <1 empty item>이 출력된다.

peek()

Queue.prototype.peek = function () {
  return this.queue[this.front];
};

 peek 함수는 배열의 front에 해당하는 인덱스의 값을 반환한다.

size()

Queue.prototype.size = function () {
 return this.rear - this.front; 
}

 size 함수는 queue의 갯수를 리턴하는데 만약 한번도dequeue되지 않고 3개의 값을 추가했을 경우 queue의 인덱스는 [0][1] [2] 으로 되어 있다 이때 배열의 사이즈는 2-0이기 때문에 2가 되어 올바른 사이즈가 아닌 것처럼 보이지만,
enqueue 함수에서 인덱스가 추가되었을 때 this.rear++로 인해 3개가 추가되고 나서 현재 rear의 값은 3이다.

display()

Queue.prototype.display = function () {
  this.queue.forEach((item, index) => {
    console.log(`[${index}] = ${item}`);
  });
};

queue값을 출력하기 위해 사용한다. 디버그용

완성본

// Queue는 자바스크립트에서 두 가지 방법으로 구현 가능하다.
// 1. 배열을 사용하기 -> 배열의 인덱스가 매우 커질 위험이 있음. 배열의 빈 공간을 관리하려면 선형 시간이 소요된다.
// 2. 연결 리스트 사용하기

// Array 사용

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }
}

Queue.prototype.enqueue = function (newValue) {
  this.queue[this.rear++] = newValue;
};

Queue.prototype.dequeue = function () {
  const value = this.queue[this.front];
  delete this.queue[this.front];
  this.front += 1;
  return value;
};

Queue.prototype.peek = function () {
  return this.queue[this.front];
};

Queue.prototype.size = function () {
  return this.rear - this.front;
};

Queue.prototype.display = function () {
  this.queue.forEach((item, index) => {
    console.log(`[${index}] = ${item}`);
  });
};

const queue = new Queue();

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
queue.dequeue();
console.log(queue.size());
queue.display();

연결 리스트를 사용해서 큐 만들기

연결 리스트를 사용하기 위해서는 Node가 필요하다.

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

class Queue {
  constructor() {
 	this.head = null;
    this.tail = null;
    this.size = 0;
  }
}

연결 리스트를 사용하는 큐는 head, tail 포인터를 갖는다. 모두 null로 초기화 한다.

enqueue(newValue)

Queue.prototype.enqueue = function (newValue) {
  const newNode = new Node(newValue);
  if(this.head === null) {
    this.head = this.tail = newNode;
  } else {
    this.tail.next = newNode;
    this.tail = newNode;
  }
  this.size += 1;
};

 enqueue 를 구현하는 방법은 연결 리스트에서 노드를 추가하는 방법과 동일하다. 첫 번째 노드일 경우 head와 tail 포인터가 모두 새로 생성한 노드를 가리키고 첫 번째 노드가 아닐 경우 현재 tail 노드의 다음 노드로 새로운 노드를 연결시키고 tail을 새로운 노드로 만든다.

dequeue()

Queue.prototype.dequeue = function () {
  const value = this.head.value;
  this.head = this.head.next;
  this.size -= 1;
  return value;
};

 dequeue 를 구현하는 방법은 head가 가리키는 노드를 반환하는 방법으로 구현한다. 현재 head가 가리키는 노드의 값을 value에 저장하고. 헤드는 현재 head의 다음 노드를 가리킨다. 그리고 나서 저장한 value를 리턴한다.

peek()

Queue.prototype.peek = function () {
  return this.head.value;
};

size()

Queue.prototype.getSize = function () {
  return this.size;
};

prototype을 사용하기 때문에 함수 이름을 size로 만들면 안된다. size로 만들 경우 console.log(queue.size())를 출력했을 때 오류가 발생한다. Queue 내부에서 size 프로퍼티를 먼저 찾는데 Queue 내부에 있는 size 프로퍼티는 함수가 아니다.

완성본

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

class Queue {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }
}

Queue.prototype.enqueue = function (newValue) {
  const newNode = new Node(newValue);
  if (this.head === null) {
    this.head = this.tail = newNode;
  } else {
    this.tail.next = newNode;
    this.tail = newNode;
  }
  this.size += 1;
};

Queue.prototype.dequeue = function () {
  const value = this.head.value;
  this.head = this.head.next;
  this.size -= 1;
  return value;
};

Queue.prototype.peek = function () {
  return this.head.value;
};

Queue.prototype.getSize = function () {
  return this.size;
};

const queue = new Queue();
queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);
console.log(queue.dequeue());
queue.enqueue(4);
console.log(queue.getSize());