[자료구조] Queue를 활용한 프린터 우선순위 예제

Queue

FIFO (First In First Out) 구조
먼저 들어간 데이터가 먼저 나오는 자료구조!

 

Queue의 메서드

 

enqueue(item)	큐에 데이터 추가 (뒤에서 넣음)
dequeue()	큐에서 데이터 제거 (앞에서 꺼냄)
peek()	가장 앞에 있는 값 확인 (안 꺼냄)
isEmpty()	큐가 비었는지 확인
size()	큐의 크기 확인

Queue도 Stack과 마찬가지로 배열을 통해 JavaScript에서 구현할 수 있다.

const queue = [];

queue.push("A");  // enqueue -> 뒤에서 추가
queue.push("B");

console.log(queue.shift());  // dequeue → A -> 앞에서 제거
console.log(queue);          // ["B"]

Stack은 뒤에서 꺼내야 해서 pop()을 사용했지만, Queue는 앞에서 꺼내야 하기에 shift()를 사용한다.

 

우선순위가 높은 문서 먼저 인쇄하기 예제

다음은 프린터 대기열을 나타낸 배열이다.
문서마다 우선순위가 있고, 우선순위가 높은 문서를 먼저 인쇄해야 한다.

조건
- 매 반복마다 큐의 맨 앞 문서를 꺼냄
- 만약 뒤에 더 높은 우선순위 문서가 있다면, 꺼낸 문서를 다시 큐 뒤로 보냄
- 그렇지 않으면 인쇄함
- 내가 요청한 문서가 몇 번째로 인쇄되는지 반환

const documents = [2, 1, 3, 2];  // 우선순위
const location = 2;  // 내가 요청한 문서 위치 (인덱스)

function getPrintOrder(documents, location) {
  // 여기에 큐 로직을 구현해보세요
}

function getPrintOrder(documents, location) {
  let queue = documents.map((priority, index) => ({ priority, index }));
  // priority와 index를 기억하기 위해 구조 변경
  let printCount = 0;

  while (queue.length) { // location을 만날 때까지 반복
    const current = queue.shift(); // 맨 앞의 priority와 index 꺼냄

    const hasHigherPriority = queue.some(doc => doc.priority > current.priority);
    // 뒤에 current.priority보다 높은 우선순위를 가진 요소가 있는지? (하나라도 있으면 true)

    if (hasHigherPriority) {
      queue.push(current); // 우선순위 낮은 애는 다시 push
    } else {
      printCount++; // 우선순위가 제일 높다면 프린트
      if (current.index === location) { // location을 만나면
        return printCount; // return
      }
    }
  }
}

어렵다;;

우선 내가 출력해야 하는 문서가 인덱스로 주어져 있어서, 각 문서의 index를 기억해야 한다.

따라서 queue의 구조를 바꿔줌.

let queue = documents.map((priority, index) => ({ priority, index }));

--->

const queue = [
  { priority: 2, index: 0 },
  { priority: 1, index: 1 },
  { priority: 3, index: 2 },  // 내가 요청한 문서
  { priority: 2, index: 3 }
];

그리고 some()을 사용해서 현재 우선순위보다 높은 우선순위가 뒤에 있는 경우엔 다시 push로 큐의 뒤에 추가해주면 된다.
가장 우선순위가 높은 애들만 프린트!

location과 같은 index를 만나서 얘가 출력이 되면, 그때 출력 횟수를 return 해주면 된다.

 

으악.
어렵다... 망했다