🔍 Queue

대기행렬이라는 의미로, 가장 먼저 들어온 데이터가 나갈때까지 다음 데이터는 나갈 수 없는 자료구조이다.

즉, 가장 나중에 들어온 데이터가 나가기 위해서는 이전에 데이터들이 모두 빠져나가기 전까지는 나갈 수 없다.

따라서, Stack과는 반대되는 개념으로, 먼저 들어온 데이터가 먼저 나오고(FIFO), 나중에 들어온 데이터는 나중에 나오게 된다(LILO).

이 때, Queue에 데이터를 넣는 것을 enqueue, 꺼내는 것을 dequeue라고 한다.

Queue의 특징을 정리하자면, 아래와 같다.

• FIFO (First In First Out) = 선입선출

• 데이터가 아무리 많아도 하나씩 넣고 뺄 수 있다. (한꺼번에 여러개 X)

• 두 개의 입출력 방향(입력 따로, 출력 따로)

✔ 기본 코드

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

  // 추가될 때 -> rear의 값이 커지고
  // 삭제 될 때 -> front 변경
  size() {
    return this.rear-this.front;
  }
  
  // queue에 element(데이터)추가
  // key : 새롭게 추가될 element의 index를 나타내는 this.rear
  // value : element
  // key와 value를 storage에 할당하고, this.rear은 다음 인덱스를 가리키게 하여 새로운 element에 대비
  enqueue(element) {
    this.storage[this.rear] = element;
    this.rear += 1;
  }
	

// 가장 나중에 추가된 데이터가 가장 먼저 나와야 한다.
  // queue에서 element를 제거 한 뒤, 해당 element를 return.
  // 만약 size가 0이라면 아무것도 return 하지 않는다.
  // this.front(가장 먼저 추가된 데이터가 있는 index)로 최하단을 설정한 후 변수에 저장하고, queue에서 제거.
  // 하나를 제거했으니 front+1(다음 요소의 index로 접근하기 위함)
  
  dequeue() {
    if (this.size() <= 0) {
      return;
    }

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

    return result;
  }
}

// 입출력
const queue = new Queue();

queue.size(); // 0
for(let i = 1; i < 10; i++) {
  	queue.enqueue(i);
}
queue.dequeue(); // 1
queue.dequeue(); // 2
queue.size(); // 7
queue.enqueue(10);
queue.size(); // 8
queue.dequeue(); // 3
queue.dequeue(); // 4
queue.size(); // 6
...

👀 실사용 예시

✔ Printer

Printer에서 여러 문서를 순서대로 인쇄하려면 아래의 과정을 거친다.

1. 문서 작성 후, 출력 버튼 누르기 -> 해당 문서가 인쇄 작업(임시 기억 장치의) queue로 들어간다.

2. 인쇄 작업 queue에 들어온 문서의 순서대로 인쇄한다.

위와 같이 데이터를 주고받을 때, 각 장치 사이의 속도나 시간의 차이를 극복하고 순서대로 결과물을 출력하기 위해 임시 기억 장치의 자료구조로 Queue를 사용하며, 통틀어 버퍼(buffer) 라고 부른다.

구현 코드

function queuePrinter(bufferSize, capacities, documents) {

  // 필요한 변수들 선언
	// time = 시간이 얼마나 지났는지 기록
  let time = 0
	// queue = 인쇄 대기 목록
  let queue = []
	// total = 대기 목록(queue)에 들어있는 문서의 총 용량
  let total = 0

// go = 1초마다 벌어질 일을 담을 함수
  const go = () => {

		// 1초 지남
    time += 1

		// 대기 목록 맨 앞에 있던 문서를 빼서 printed라는 변수에 담기
    let printed = queue.shift()

		// 프린트할 문서가 있었다면 printed라는 변수에 값이 존재
		// 값 = 인쇄된 문서의 용량
		// 따라서 총 용량 total에서 인쇄된 문서 용량을 빼준다
    if(printed){
      total = total - printed;
    }

		// 대기 목록에 다른 문서를 올릴 수 있는지 확인
		// 총 용량 + 인쇄해야 할 리스트 0번째 문서의 용량은 capacities의 값보다 같거나 작아야 함.
    if (total + documents[0] <= capacities) {
			// 리스트에 있던 문서를 빼서
      let document = documents.shift()
			// 대기 목록 마지막 칸에 문서를 넣어주고
      queue[bufferSize-1] = document
			// 총 용량 + 넣어준 문서 용량
      total += document
    }
  }

	// 문서리스트에 문서가 있거나,
	// 인쇄 대기 목록에 아직 인쇄되지 않은 문서가 남아있을 때
  while (documents.length || queue.length) {
		// 1초마다 벌어질 일을 담을 함수를 실행시켜줌
    go()
  }

	// 더 이상 인쇄할 문서도, 인쇄 대기중인 문서도 없을 때
	// 총 소모시간인 time을 return
  return time
}

// 입출력
let bufferSize = 2;
let capacities = 10;
let documents = [7, 4, 5, 6];

let output = queuePrinter(bufferSize, capacities, documents);
console.log(output) // 8

Reference: 코드스테이츠