[자료구조] 큐(Queue)

🤔 큐(Queue)?

배열과 함께 가장 쉬운 자료구조중 하나이다. 큐(Queue)는 컴퓨터에서 가장 핵심적인 소프트웨어 중에 하나인 운영체제에서도 많이 쓰인다. 인터넷에서 네트워크 기능에서도 많이 사용된다.

큐(Queue)의 구조와 용어는?

큐(Queue)는 가장 먼저 넣은 데이터를 가장 먼저 꺼낼 수 있는 구조이다(FIFO). 마치 줄을 서는 행위와 유사하다. 예를 들어 음식점에서 가장 먼저 줄을 선 사람이 제일 먼저 음식점에 입장하는 것과 동일하다.

선형 큐(Linear Queue)
선형 큐(Linear Queue)는 가장 기본적인 형태의 큐(Queue)이다. 특수한 형태의 큐(Queue)도 존재한다.

FIFO (First-In, First-Out)
선입선출 방식을 말한다. 가끔 LILO(Last-in, Last-Out)으로 불리기도 한다. 스택(Stack)과 꺼내는 순서가 반대이다.

데이터가 들어오는 위치는 Back 혹은 Rear라고 하고, 데이터가 나가는 위치는 Front라고 한다. 입력 동작은 Enqueue, 출력 동작은 Dequeue라고 한다.

큐(Queue)는 어디에서 많이 쓰일까?

멀티태스킹을 위한 프로세스 스케쥴링 방식을 구현하기 위해 많이 사용된다(운영체제). 프로세스 스케쥴링 방식을 함께 이해하는 것이 좋다.

Javascript에서의 큐(Queue)?

Javascript에서 큐(Queue)를 Class로 구현하면 다음과 같다.

class Queue {
  #array; // private
  
  constructor(array = []) {
    if (!Array.isArray(array)) {
      throw new TypeError(`${array} is not an array.`);
    }
    this.#array = array;
  }

  enqueue(value) {
    return this.#array.push(value);
  }
  dequeue() {
    return this.#array.shift();
  }
  entries() {
    return [...this.#array];
  }
}

const queue = new Queue([1, 2]);
console.log(queue.entries()); // [1, 2]

queue.enqueue(3);
console.log(queue.entries()); // [1, 2, 3]

queue.dequeue();
console.log(queue.entries()); // [2, 3]

다양한 형태의 큐(Queue)?

• 원형 큐(Circular Queue)는 선형 큐(Linear Queue)의 단점을 보완한 방식의 새로운 큐(queue)이다.
• 우선순위 큐(Priority Queue)는 데이터마다 우선순위를 넣어서 우선순위가 높은 순으로 데이터를 출력하게 된다(Heap).

💡 정리

큐(Queue)와 같이 대표적인 자료구조나 알고리즘에 대해서는 대부분의 프로그래밍 언어에서 관련 라이브러리나 함수를 제공하는 경우가 많다. 그러나 직접 큐의 방식을 이해하고 이를 함수나 조건문, 반복문, 리스트 데이터 파일을 이용해서 직접 구현해보면서 프로그래밍 스킬을 익히는 것이 중요하다.

📝 참고

Velog - [자료구조] 스택(Stack)
Poiemaweb - 배열
visualgo
이미지출처 - Wikipedia