Queue

입력과 출력이 다른 방향에서 이루어지는 자료구조
입구와 출구가 따로 있는 원통형과 같은 구조
선입선출 FIFO(First In First Out), LILO(Last In Last Out)

실사용 예

• 프린터의 인쇄 대기 목록
• 콜센터 고객 대기시간
• 프로세스 관리
• 캐시 구현

Queue의 특징

선입선출

먼저 들어간 데이터가 제일 처음 나오는 구조

const queue = [];
queue.push(1) // [1]
queue.push(2) // [1,2]
queue.push(3) // [1,2,3]
queue.shift() // 1, [2,3]
queue.push(4) // [2,3,4]
queue.shift() // 2, [3,4]

두 개의 입출력 방향

큐 자료구조는 데이터의 입력 출력 방향이 다름
데이터를 입력할 때는 큐의 맨 끝(tail)으로만 입력 가능,
데이터를 출력할 때는 큐의 맨 앞(head)으로만 출력 가능
입출력 방향이 같다면 큐 자료구조라고 볼 수 없음

데이터는 하나씩 넣고 뺄 수 있음

큐에 하나씩 여러 번 데이터를 넣어 큐 내부에 데이터가 여러 개 쌓여 있어도, 데이터를 뺄 때는 큐의 맨 앞에서 한 번에 한 개의 데이터만 빼낼 수 있음

Queue 구현

class Queue {
  constructor() {
    this.storage = {}; // 데이터가 저장되는 변수
    this.front = 0; // 큐의 가장 앞(데이터 출력이 일어나는 장소)를 가리키는 변수
    this.rear = 0; // 큐의 가장 뒤(데이터 입력이 일어나는 장소)를 가리키는 변수
  }
  size() {
    return this.rear-this.front
  }
  enqueue(element) {
    this.storage[this.rear] = element; // [1] // [1,2]
    this.rear += 1; // 1 // 2
  }
  dequeue() {
    if (this.front === this.rear) {
      return;
    }
    const result = this.storage[this.front]; // 1
    delete this.storage[this.front]; // [2]
    this.front += 1; // 1
    return result;
  }
}