[ 자료구조 ] Queue

📌 Queue ( 큐 )

큐(Queue)는 '줄을 서서 기다리다, 대기행렬' 이라는 뜻을 가지고 있다.

실생활에서의 큐를 찾아보자면 가장 쉽게 대기줄을 생각할 수 있다. 대기줄에서 가장 중요한 것은 '순서'이다.

톨게이트에 진입하는 차량을 생각해보면 도착한 순서대로 톨게이트를 나가는 모습이 바로 큐이다.

이 때 톨게이트 자체가 큐를 의미하고, 각 차량들이 데이터를 의미한다.

Queue의 구조

자료구조 Queue는 실생활 예시만 봐도 Stack과 반대되는 개념인 것을 알 수 있을 것이다.

한 곳으로만 데이터 입출력이 이루어지는 것이 Stack이었다면, Queue는 두 개의 방향으로 입출력이 '순서대로' 이루어진다.

먼저 들어간 데이터(data)가 먼저 나오는 FIFO(First In First Out) 혹은 LILO(Last In Last Out)의 특징.
입력의 방향과 출력의 방향이 각각 고정되어 있으며, 데이터를 입력할 시에는 큐의 끝에서(tail), 데이터를 출력할 때는 큐의 맨 앞에서(head) 진행.
Queue에 데이터를 넣는 것을 'enqueue', 데이터를 꺼내는 것을 'dequeue'.

Queue의 특징

#01. FIFO (First In First Out)

먼저 들어간 데이터가 제일 처음에 나오는 선입선출의 구조로 되어 있다.

위의 사진을 설명해보면, 1,2,3,4 순서대로 데이터가 입력되면 출력되는 순서 또한 1,2,3,4로 동일하다. 즉 입력 순서와 출력 순서가 동일한 특징을 갖고 있다.

#02. 두 개의 입출력 방향

Queue 자료구조는 데이터의 입력, 출력 방향이 다르다. 데이터를 입력할 때는 큐의 맨 끝(tail)으로만 입력이 가능하며 데이터를 출력할 때는 큐의 맨 앞(head)으로만 출력이 가능합니다. 즉, 큐는 데이터를 입력하는 곳과 출력하는 곳이 각각 정해져 있으며 이렇게 총 2개의 입출력 방향을 가지고 있습니다. 만약 입출력 방향이 같다면 Queue 자료구조라고 볼 수 없습니다.

#03. 데이터는 하나씩

앞서 말했듯, Queue 자료구조는 데이터를 넣을 때는 큐의 맨 뒷 부분에서 뺄 때는 큐의 맨 앞부분에서 처리를 진행한다. 각 처리 시마다 한 개의 데이터를 넣거나 뺄 수 있다. 즉, 큐에 한 개 씩 여러 번 데이터를 넣어 큐 내부에 데이터가 여러 개 쌓여 있다고 하더라도, 데이터를 뺄 때는 큐의 맨 앞에서 한 번에 한 개의 데이터만을 뺄 수 있다. 이는 stack과 동일한 특징이다.

Queue의 실사용 예제

자료구조 Queue는 컴퓨터에서도 광범위하게 활용됩니다. 컴퓨터와 연결된 프린터에서 여러 문서를 순서대로 인쇄하는 데에 큐를 찾을 수 있다.

우리가 문서를 작성하고 출력 버튼을 누르면 해당 문서는 인쇄 작업 (임시 기억 장치의) Queue에 입력.
프린터는 인쇄 작업 Queue에 들어온 문서를 들어온 순서대로 인쇄(출력).

만약 Queue에 들어온 순서대로 출력하지 않는다면, 인쇄 결과물이 뒤죽박죽일 것이다.

위 예시처럼 컴퓨터 장치들 사이에서 데이터(data)를 주고받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이을 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용합니다. 이것을 통틀어 버퍼(buffer)라고 합니다. 아래 이미지는 버퍼링(buffering)의 개념을 보여주고 있다.

Queue 구현

- 클래스를 이용한 Queue 구현

class Queue {
  constructor() {
    this.storage = {};
    this.front = 0;
    this.rear = 0;
  }

  size() {
    return this.rear - this.front
  }
	
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
	
  dequeue() {
    if (this.size() <= 0) {
      return;
    }

    const result = this.storage[this.front];
    delete this.storage[this.front];
    this.front += 1;

    return result;
  }
}

- Array를 이용한 Queue 구현

const queue = [];

queue.push(1); // [1]
queue.push(2); // [1, 2]
queue.push(3); // [1, 2, 3]
queue.push(4); // [1, 2, 3, 4]
queue.push(5); // [1, 2, 3, 4, 5]

console.log(queue); // [1, 2, 3, 4, 5]

queue.shift(); // [2, 3, 4, 5]
queue.shift(); // [3, 4, 5]

console.log(queue); // [3, 4, 5]

'CS > 자료구조' 카테고리의 다른 글

[자료구조] Tree (0)	2023.03.23
[자료구조] Stack (0)	2023.03.18