N

(TIL Day03-4)자료구조- 큐 본문

TIL

(TIL Day03-4)자료구조- 큐

naeunchan 2021. 8. 6. 10:26
728x90
반응형

큐(Queue)

  • First In First Out(FIFO)라는 개념을 가진 선형 자료구조.
  • 먼저 들어간 데이터가 먼저 출력된다.
  • 식당에서 대기번호 표를 받았을 때를 생각하면 쉽게 이해할 수 있다.
  • 큐의 가장 앞에 있는 원소의 인덱스(위치)는 front로 나타내며, 가장 뒤에 있는 원소의 인덱스(위치)는 rear라고 한다.

 

데이터 추가

  • enqueue
  • 큐의 가장 마지막에 데이터를 추가한다.
  • 데이터를 추가할수록 rear 값이 1 증가한다.

 

데이터 삭제

  • dequeue
  • 큐의 맨 앞에 있는 원소(front)가 삭제된다.
  • 데이터 삭제를 하면 front 값이 1 증가한다.

 

코드

JS에서는 큐가 제공되지 않기 때문에 배열 형태로 큐를 구현한다.

class Queue {
  constructor() {
    this.queue = [];
    this.front = 0;
    this.rear = 0;
  }

  enqueue(value) {
    this.queue[this.rear++] = value;
  }

  dequeue() {
    const value = this.queue[this.front];
    delete this.queue[this.front];
    this.front++;
    return value;
  }

  peek() {
    return this.queue[this.front];
  }

  size() {
    return this.rear - this.front;
  }
}
  • peek() 함수는 큐의 가장 앞에 있는 원소 값을 리턴한다.
  • size() 함수는 현재 큐의 크기(원소의 개수)를 나타낸다.
728x90
반응형