[자료구조]Queue

Queue란?

자료구조 Queue는 Stack와 다르게, 먼저 들어간 데이터(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out) 을 특징으로 가지고 있습니다. 티켓을 사려고 줄을 서서 기다리는 모습과 흡사한 이 자료구조는 입력과 출력의 방향이 고정되어 있으며, 두 곳으로 접근이 가능합니다. Queue에 데이터를 넣는 것을 'enqueue', 데이터를 꺼내는 것을 'dequeue'라고 합니다.

자료구조 Queue는 데이터(data)가 입력된 순서대로 처리할 때 주로 사용합니다.

Queue의 특징

1. FIFO (First In First Out)

먼저 들어간 데이터가 제일 처음에 나오는 선입선출의 구조를 가지고 있습니다.

2. 데이터는 하나씩 넣고 뺄 수 있습니다.

Queue 자료구조는 데이터가 아무리 많이 있어도 하나씩 데이터를 넣고, 뺍니다. 한꺼번에 여러 개를 넣거나 뺄 수 없습니다.

3. 두 개의 입출력 방향을 가지고 있습니다.

Queue 자료구조는 데이터의 입력, 출력 방향이 다릅니다. 만약 입출력 방향이 같다면 Queue 자료구조라고 볼 수 없습니다.

실사용 예제

프린터에서 인쇄물을 출력할 때나, 컴퓨터에서 데이터를 주고 받을 때 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용합니다.

프린터와 같은 장치들은 CPU보다 처리하는 속도가 느리기 때문에 CPU는 처리해야할 데이터를 작업 Queue에 저장하고 다른 작업을 수행합니다.

Queue 구현

배열을 Queue를 구현할 수도 있지만 배열의 경우 먼저 들어온 요소를 제거할 때 인덱스 값들이 재배정되면서 성능 저하가 발생합니다. 그렇기 때문에 데이터가 많은 경우에는 클래스를 사용해서 구현하는 것이 좋습니다.

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return this.rear - this.front;
  }

  enqueue(el) {
    this.storage[this.rear] = el;
    this.rear += 1;
  }

  dnqueue() {
    if (this.size() === 0) {
      return;
    }

    let result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;

    return result;
  }
}

const queue = new Queue();

queue.enqueue(1); 
queue.enqueue(2); 
console.log(queue); // Queue { storage: { '0': 1, '1': 2 }, front: 0, rear: 2 }