큐 Queue

큐에 대해 알아보자.

---

큐 Queue

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

---

큐의 추상 자료형 ADT

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

---

구현 코드

class Queue {
  constructor() {
    this._arr = [];
  }

  enqueue(item) {
    this._arr.push(item);
  }

  dequeue() {
    return this._arr.shift();
  }

  peek() {
    return this._arr[0];
  }

  size() {
    return this._arr.length;
  }

  isEmpty() {
    return this._arr.length == 0;
  }
}

---

enqueue

큐에 자료를 추가하는 것으로 Javascript의 배열이 기본 지원하는 push 메서드를 사용합니다.

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

console.log(queue); // {_arr : [1, 2, 3]}

---

dequeue

큐에서 자료를 추출하는 것으로 Javascript의 배열이 기본 지원하는 shift 메서드를 사용합니다.

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

console.log(queue); // {_arr : [1, 2, 3]}

queue.dequeue(); // 1
queue.dequeue(); // 2
queue.dequeue(); // 3

console.log(queue); // {_arr : []}

• 시간복잡도 : O(n)

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

  시간복잡도를 O(1)로 줄이기위해서는 연결리스트로 구현하는 방법이 있습니다.

---

peek

처음에 추가된 항목을 큐 자료구조에서 제거하지않고 확인하는 것을 의미합니다.

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

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

---

size

큐 자료구조에서 스택 안에 있는 요소들의 갯수를 반환합니다.

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

queue.size(); // 3

---

isEmpty

큐 자료구조에서 스택 안에 요소가 있는 지 확인합니다.

queue.isEmpty(); // true

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