[자료구조] 큐 Queue 개념 | js 구현

Queue의 특징

1. FIFO (First In First Out)

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

 

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

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

 

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

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

 

js 코드 구현

class Queue {
  //가장 앞에 있는 요소를 front,
  //가장 뒤에 있는 요소를 rear 라고 했을 때
  //queue constructor 생성
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }
  // queue의 사이즈를 구합니다.
  // queue는 추가될 때, rear의 값이 커지고 삭제 될 때, front가 변경이 때문에, 각 값을 알아야 size를 구할 수 있습니다.
  size() {
    return this.rear - this.front;
  }
  // queue에 element를 추가합니다.
  // 새롭게 추가될 요소의 인덱스를 나타내는 this.rear를 키로, 요소를 값으로 하여 storage에 할당합니다. this.rear은 다음 인덱스를 가리키게 하여 새로운 요소에 대비합니다.
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
  // queue에서 element를 제거 한 뒤 해당 element를 반환합니다.
  // 만약 size가 0이라면 아무 일도 일어나지 않습니다.
  // this.front+1로 가장 앞에 있는 요소를 다시 설정한 후 변수에 저장하고, 큐에서 삭제합니다.
  dequeue() {
    if (this.size() === 0) {
      return;
    }
    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;
    return result;
  }
}