큐 Queue

큐에 대해 알아보자.

---

큐 Queue

큐는 첫번 째 삽입된 항목만을 제거할 수 있는 FIFO(First In First Out) 원리를 따르는 자료구조입니다.

---

큐의 추상 자료형 ADT

• enqueue : 맨 마지막에 새로운 요소 삽입
• dequeue : 맨 앞에 요소 추출하고 반환
• peek : 맨 앞 요소 확인
• isEmpty : 비어있는지 확인

---

• size : 요소 갯수 반환

---

구현 코드

시간복잡도를 O(1)로 줄이기위해서 head index를 사용합니다.

shift 메서드를 사용해서 구현하는 경우 첫 번째 항목을 제거한 다음 남은 값들의 인덱스를 하나씩 앞으로 당겨주므로 시간복잡도 O(n)을 갖습니다.

class Queue {
  #arr = [];
  #head = 0;

  enqueue(item) {
    this.#arr.push(item);
  }

  dequeue() {
    if (this.isEmpty()) {
      throw new Error("Queue is empty");
    }

    const value = this.#arr[this.#head++];

    if (this.#head * 2 > this.#arr.length) {
      this.#shrink();
    }

    return value;
  }

  #shrink() {
    this.#arr = this.#arr.slice(this.#head);
    this.#head = 0;
  }

  peek() {
    return this.#arr[this.#head];
  }

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

  size() {
    return this.#arr.length - this.#head;
  }
}

---

enqueue

새로운 요소를 추가하는 것으로 Javascript의 배열이 기본 지원하는 push 메서드를 사용합니다.

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

console.log(queue); //  [1, 2, 3]

---

dequeue

맨 앞에 요소를 추출하는 것으로 head index의 값을 추출한 후 head index값을 증가시킵니다.

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

console.log(queue); // [1, 2, 3]

queue.dequeue(); // 1 추출, head : 1
queue.dequeue(); // 2 추출, head : 2
queue.dequeue(); // 3 추출, head : 3

console.log(queue); // [1, 2, 3]

---

peek

맨 앞에 요소를 제거하지않고 확인합니다.

queue.enqueue(1);
queue.enqueue(2);
queue.enqueue(3);

console.log(queue.peek()); // 1

---

isEmpty

큐 안에 요소가 있는 지 확인합니다.

queue.isEmpty(); // true

queue.push(1);
queue.isEmpty(); // false

---

size

큐 안에 있는 요소들의 갯수를 반환합니다.

queue.push(1);
queue.push(2);
queue.push(3);

queue.size(); // 3