What's Queue?

줄을 서서 기다리다, 대기 행렬 이라는 뜻을 가진 큐는,
줄을 서서 차례대로 통과하는 모습과 흡사하다.

즉 Stack과 반대로, 먼저 들어간 데이터가 먼저 나오는 FIFO, LILO 특징이다.
따라서 데이터를 입력된 순서대로 처리할 때 주로 사용한다.
데이터 삭제 시, 재정렬이 필요없다.

톨게이트를 Queue 자료구조, 자동차는 데이터로 비유할 수 있다.

[Queue] 구현

class Queue {
  constructor() {
    this.storage = {}; // 큐의 저장소 생성!
    this.first = 0;    // 큐의 가장 앞 포인터: 추출되는 데이터 확인
    this.last = 0;     // 큐의 가장 뒤 포인터: 추가되는 데이터 확인
  }

  size() {
    return this.last - this.first;
    // 추가, 추출한 데이터를 세준 카운트들로 큐가 보유한 데이터 수를 알 수 있겠지!
  }
	
// 큐에 데이터 추가: 스텍과 동일하게 push
  enqueue(element) {
    this.storage[this.last] = element;
    this.last++;
    // 데이터를 추가하고 다음 요소 대비 인덱스 올리기!
  }
  
// 데이터 추출: 스텍과 반대로 shift
  dequeue() {
    // 예외 케이스: 빈 큐일 때 아무것도 하지마!
    if (!this.size()) {
      return; 
    }

    const firstEl = this.storage[this.first];
    delete this.storage[this.first];
    this.first++;
    // 맨 앞의 데이터를 제거하면 그 다음 인덱스가 첫 번째 요소!

    return firstEl;
  }
}

[Queue 활용]1

문제
마트에서 장을 보고 박스를 포장하는 데 폭이 좁아, 한 줄로 들어온 순서대로 나가야 합니다.
앞사람 포장이 끝나면, 포장을 마친 뒷사람들과 함께 한 번에 나가게 됩니다.
박스 배열이 주어질 때, 통틀어 최대 몇 명이 한번에 나가는지 함수를 구현해 주세요.

// 배열의 길이가 인원, 최대 몇 명이 한꺼번에 나갈까?
function paveBox(boxes) {
  
  let count = 1; 
  // 인원을 세 줄 카운트 설정! 초기값 1 -> 기준이 되는 맨 앞사람은 무조건 나갈 수 있으니까!
  let exitNum = []; // 한번에 나갈 수 있는 최대인원을 요소로 가진 배열
  
// 배열을 훑으면서 탈출 기준인 첫 요소와 비교하자!
  boxes.reduce((pre, cur) => {
  
    if(pre >= cur) { 
      count++;  // 초기값 >= 비교할 값 탈출 인원에 탑승!
      return pre; // 탈출 기준은 그대로!
    } 
    else { // 초기값 < 비교할 값 
      exitNum.push(count); // 직전까지 세어 준 탈출 가능 인원을 요소로 추가!
      count = 1; // 탈출가능 인원수 초기화하기!
      return cur; // 탈출 기준을 비교한 값으로 변경하고 다시 반복!
    }
  })
  exitNum.push(count);
  // 💡만약 마지막 요소가 탈출 기준 값보다 크지 않으면 else로 떨어지지 못해
  // 마지막 탈출 가능 인원 count를 못한다. 
  // 따라서 그 마지막 인원을 세주기 위한 코드!!
  // 💡💡[...boxes, undefined] 전개구문으로 임의의 요소를 만들어 
  // else 문으로 떨어뜨리는 방법도 있다!
 return Math.max(...exitNum)  
}

TIL Point

• reduce() 메소드
  배열.reduce((누적값, 현잿값, 인덱스, 요소) => { return 결과 }, 초깃값);
  reduce는 그저 셈을 하는 메소드가 아닌
  loop를 통해 단일 값을 반환하는 메소드라는 것!
  ❗️반복되는 모든 것에는 reduce를 쓸 수 있다!!

reduce를 통한 map 구현

result = oneTwoThree.reduce((acc, cur) => {
  acc.push(cur % 2 ? '홀수' : '짝수');
  return acc;
}, []);
result; // ['홀수', '짝수', '홀수']

reduce를 통한 filter 구현

result = oneTwoThree.reduce((acc, cur) => {
  if (cur % 2) acc.push(cur);
  return acc;
}, []);
result; // [1, 3]

TIL Point

• Math.max(num)
  입력값으로 받은 숫자 중 가장 큰 숫자를 반환하는 함수
• spread구문
  배열 리터럴로 기존 배열을 가진 새로운 배열을 생성할 시,
  push, splice, concat 등을 사용해야 하던 것이 훨씬 간편해졌다.
  함수 호출 시 인자로 전개구문을 사용하면 reduce로 배열을 벗기는 작업을 안해도 된다!

// 배열의 최댓값 구하기
let arr = [1,2,3];
let max = arr.reduce(function(a, b) {
    return Math.max(a, b); // Math.max(...arr);
}); 

• dummydata 활용
  일례로, 요소를 1번부터 오름차순으로 N만큼 넣어야 되는 로직이 있다고 했을 때,
  요소를 빼내는 건 인덱스이기 때문에 0과 1의 차이가 굉장히 헷갈릴 수 있는데,
  그럴 때 0번째 요소엔 더미데이터를 넣어 index와 요소를 맞추는 것에 써먹을 수 있다!
  더미데이터는 0뿐만 아니라,
  false, true, '가' 등 로직에 방해가 되지 않는다면 무엇이든 넣을 수 있다.

[Queue 활용]2

프린트의 인쇄 과정이 큐의 대표적인 예.

문제
프린터의 인쇄 작업 목록의 크기와 최대 용량을 가정하고 다른 용량의 문서를 차례대로 인쇄하여 모든 문서가 인쇄되는데 최소 몇 초가 걸리는지 테스트하려 한다.

프린터 인쇄 작업 목록의 제한사항

• 인쇄 작업 목록은 칸으로 이루어져 있다.
• 각 칸에는 한 개의 문서만 위치할 수 있다.
• 문서는 1초에 한 칸만 이동할 수 있다.
• 인쇄할 문서의 크기가 나열된 배열 documents가 주어지며
  인쇄 작업 목록의 크기는 bufferSize이고
  최대 용량 capacities 만큼 문서를 담을 수 있다.
• 문서 하나의 크기는 capacities를 초과하지 않는다.

 // 모든 문서가 인쇄되는데 최소 몇 초가 걸릴까?
function queuePrinter(bufferSize, capacities, documents) {
 
  let time = 0; // 소요 시간: 이 문제의 결과값
  let printStage = Array(bufferSize).fill(0);
  // bufferSize만큼 출력 대기 자리 만들기 [0, 0, ...]
  // 문서의 크기가 요소로 들어갈거니 덧셈을 방해하지 않는 0을 임시 요소로 칸을 생성!
  
  while(documents.length) { // 프린트할 문서가 있을 때까지 반복!
  
    printStage.shift(); 
    // 목록의 첫 문서 출력. 빈 배열일 때(프린트 시작 시) shift를 해도 에러 나지 않는다. 
    
    let totalsize = printStage.reduce((pre, cur) => pre + cur, 0)
    // 대기 중인 목록의 크기의 합
          
    if (totalsize + documents[0] <= capacities) {  
    //  현재 대기 목록의 크기와 추가할 문서의 크기의 합 <= 최대 수용 용량
      printStage.push(documents.shift()); // 목록에 추가 해!
    } else { 
      printStage.push(0); // 아니야? 출력 대기 마지막 자리 빈공간으로 둬! 
    }
    time++;   
  }
  return time + bufferSize; 
  // printStage에 문서를 다 넣은 time + 출력 대기 목록에 있는 갯수
}

TIL Point

• Array(arrayLength) 생성자 함수
  arrayLength만큼 요소가 비어진 배열을 생성
• fill()

arr.fill(value[, start[, end]])

배열의 시작 인덱스부터 끝 인덱스의 이전까지 정적인 값 하나로 채운다.

let printStage = []; // 프린트 순서
  for (let i = 0; i < bufferSize; i++) {
	printStage.push(0); }
// Array(bufferSize).fill(0); 3줄을 한번에...!

• Queue와 While문은 환상의 짝꿍