[자료구조] Queue

Queue의 정의

큐(Queue)는 줄을 서서 기다리다, 대기행렬이라는 뜻을 가지고 있으며 데이터를 일시적으로 저장하기 위한 자료구조 중 하나입니다. 먼저 들어온 데이터가 먼저 처리되는 "FIFO(First In First Out)" 방식으로 동작합니다.

큐는 크게 두 가지 요소로 구성됩니다. 하나는 front, 또 다른 하나는 rear입니다. front는 큐의 맨 앞을 가리키며, rear는 큐의 맨 뒤를 가리킵니다.  큐에서는 데이터 삽입하는 enqueue(인큐)와 데이터를 삭제하는 dequeue(디큐) 두 가지 기본 연산을 지원합니다. 새로운 데이터는 큐의 맨 뒤(rear)에 삽입되며, 기존 데이터는 큐의 맨 앞(front)에서 제거됩니다. 이때 front와 rear가 가리키는 위치는 계속해서 바뀌게 됩니다.

큐는 주로 대기열을 관리하거나 운영체제에서 프로세스를 관리하는 등 다양한 분야에서 사용됩니다. 예를 들어, 프린터에서 출력할 문서를 대기열에 저장하거나, 네트워크 패킷을 처리할 때 패킷을 큐에 저장하는 등의 경우에 사용됩니다.

프린터에서 출력할 문서를 대기열에 저장

큐는 선형 자료구조 중 하나로, 배열이나 연결 리스트로 구현될 수 있습니다. 배열로 구현하는 경우 큐의 크기를 미리 정해야 하지만, 연결 리스트로 구현하는 경우 크기를 동적으로 조절할 수 있습니다.

큐의 삽입과 삭제 연산은 O(1)의 시간 복잡도를 가지므로, 데이터의 삽입과 삭제가 빈번한 경우에 유용하게 사용됩니다.

---

Queue 구현

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;
  }
}