TIL [자료 구조 - Queue]

dlrbwls0302·2021년 1월 19일
0

Queue의 개념

Queue는 추상적인 데이터 구조로 Stack과 다소 비슷한 면이 있다. 하지만 Stack과 다른 점은 Queue의 양쪽이 뚫려있다는 점이다. 한 쪽 방향은 항상 데이터를 추가하는 용도로 쓰이고 다른 쪽 방향은 항상 데이터가 제거되는 용도로 쓰일 뿐이다. 따라서 Queue는 FIFO(First In First Out)의 구조를 가지고 있다.

실생활에서는 번호표를 뽑고 은행에서 기다리는 고객들이나 놀이 공원에서 줄을 서서 자신의 차례를 기다리는 손님들이라고 보면 된다. 먼저 온 사람들이 먼저 서비스를 받지 못한다면 불만을 표하는 것처럼 우리도 Queue에서 데이터의 처리를 먼저 추가된 순서로 해야만 한다.

그림에서도 볼 수 있듯이 추가는 뒤(rear)에서 하고 삭제는 앞(front)에서 하게된다.


Queue 구현

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0; // rear는 마지막 값의 다음의 인덱스를 가리킨다. 
  }

  size() {
    return this.rear-this.front; // 삭제될 시 rear는 그대로있고 front부터 사라지기 때문에 rear-front라고 해야한다.
  }

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

  dequeue() { // dequeue는 첫 아이템을 빼는것과 동시에 그 아이템을 리턴한다.
    if (this.front === this.rear) return undefined;
    let result = this.storage[this.front];
    delete this.storage[this.front]; // 키 값은 0, 1, ... , n
    this.front += 1;
    return result;
  }
}
profile
오늘의 공부가 쌓여서 내일의 나를 만들어낸다.

관심 있을 만한 포스트

0개의 댓글