목차

• 큐(Queue)란?
• 큐(Queue)는 언제 사용할까?
• Queue 시간복잡도
• JS로 Queue 구현하기
• Ref

Queue란?

• 큐(Queue)의 가장 큰 특징은 선입선출('FIFO')입니다.
  즉 먼저들어온 값이 먼저 나가는 구조입니다

• Date의 삽입과 삭제가 2곳에서 이루어 진다.
  rear(tail)로 들어와서 front(head)로 나간다.

• 아래의 그림에서 push를 통해 1부터 5의 순서로 값을 추가하며, 값을 꺼낼땐 head에서 꺼낼 수 있다.
  

Queue는 언제 사용할까?

• 선착순 관련해서 모든 경우가 사용된다.
• 은행에서 표를 뽑는 경우
• 달리기 시합에서 등수를 매기는 경우
• 알고리즘에선 우선순위 큐 또는 BFS에서도 사용이 된다.

Queue 시간복잡도

• Data를 삽입하는 경우 O(1)
• Data를 삭제하는 경우 O(1)
• Data를 찾는 경우 최악의 경우 O(n)

JS로 Queue 구현하기

• Queue의 ADT : ADT란 추상 자료형이라고도 하며, 데이터를 구체적으로 구현하는 방식은 생략하고 데이터의 추상적인 형태와 데이터를 이루는 방법만을 정해놓은 것입니다.

  ADT	설명
  enQueue	x를 큐 맨 뒤에 삽입(저장)한다.
  deQueue	큐 맨 앞에서 하나의 요소를 제거하고 반환한다.
  peek	큐의 맨 앞에서 하나의 요소를 확인한다.
  size	큐에 존재하는 요소의 수를 반환한다
  isEmpty	큐가 비어있는지를 확인한다.

배열을 이용한 Queue 구현

• 자바스크립트의 pop(), shift()를 활용하여 큐(Queue)를 구현할 수 있지만, pop, shift를 사용할 경우 삽입과 삭제시 시간복잡도가 O(n)이 된다.
  이유는 삽입과 삭제시 배열의 재정렬이 필요하기 때문이다.
  일반적으로 데이터가 1000건 이하는 shift,pop을 이용한 큐를 사용해도 무방하다고 한다.

  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.getSize() === 0;
    }
  }

배열을 이용하지 않고 큐(Queue)구현하기

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

  enQueue(item) {
    this.arr[this.tail] = item;
    this.tail++;
  }

  deQueue() {
    let removed = this.arr[this.head];
    delete this.arr[this.head];
    this.head++;
    return removed;
  }

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

  getSize() {
    return Object.keys(this.arr).length;
  }

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

const q = new Queue();
q.enQueue(3);                // 3 추가
console.log(q.peek());       // 3

q.enQueue(4);                // 4추가
console.log(q.peek());       // 3   peak는 head값을 확인한다.
q.deQueue();                 // 처음값인 3제거
console.log(q.peek());       // 4

q.enQueue(1);               // 1추가
q.deQueue();                // 처음값인 4제거

console.log(q.isEmpty());   //false
q.deQueue();                // 처음값인 1제거

console.log(q.isEmpty());   //true	

Ref

• 화니의 블로그