Queue

1. 개념

• 줄을 서서 기다리는 구조
• Stack과 반대되는 개념으로 먼저 들어간 데이터가 먼저 나옴
  *FIFO(First In First Out) 혹은 LILO(Last In Last Out)
• 컴퓨터 장치들 사이에서 데이터(data)를 주고 받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해 임시 기억 장치의 자료구조로 Queue를 사용
  *이 과정을 버퍼(buffer)라고 함
• while 반복문과 짝궁

2. 구조

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]

// FIFO(First In First Out)
queue.shift() // [2, 3, 4, 5]
queue.shift() // [3, 4, 5]
queue.shift() // [4, 5]
queue.shift() // [5]
// LILO(Last In Last Out)

3. paveBox 예제

1) 처음 풀이

function paveBox(boxes) {

  let result = []
  // 몇명의 사람이 박스 포장을 끝내고 한번에 나갈 수 있는지 기록

  // head보다 많은 박스를 포장해야 하는 사람을 만나면 배열 분리
  let splitArr = (boxes) => {
    let [head, ...tail] = boxes
    
    // head보다 작거나 같은 박스를 포장해 head와 함께 나갈 수 있는 사람들 기록
    let newArr = []

    for(let i = 0; i < tail.length; i++) { 

      if(head < tail[i]) {
        // head보다 많은 박스를 포장해야 할 사람을 만났을 경우
        result.push(newArr.length + 1)
        return splitArr(tail.slice(i)) 
      } else if(head >= tail[i]) {
        // head보다 작거나 같은 박스를 포장할 사람을 만났을 경우
        newArr.push(tail[i])
        if(newArr.length === tail.length) {
          // head보다 많은 박스를 포장해야 할 사람 없이 끝나는 경우
          return result.push(newArr.length + 1)
        }
      }
    }
  }

  // 재귀함수 실행
  splitArr(boxes)

  return Math.max(...result)
  // 최대 몇명이 함께 나갈 수 있는지 리턴
}

2) 다른 풀이

function paveBox(boxes) {
    let answer = []
    
    // boxes 배열이 0보다 클 때까지 반복합니다.
    while(boxes.length > 0){
      // 첫번째 사람보다 많은 상자를 포장해야 하는 사람의 인덱스를 찾음
      // 없으면 -1 반환
      let findIdx = boxes.findIndex(el => boxes[0] < el);
      
      if(finishIndex === -1){
          // 만약 찾지 못했다면 answer에 boxes 배열의 길이를 넣은 후 while문을 끝냄
          answer.push(boxes.length)
          break

      } else {
          // 만약 찾았다면, 해당 인덱스를 answer에 넣고, boxes에서 그만큼 제외
          answer.push(findIdx);
          boxes.splice(0, findIdx);
      }
    }

4. queuePrinter 예제

1. 프린터에 비해 속도가 빠른 CPU
   : 빠른 속도로 인쇄에 필요한 데이터(data)를 만들어 인쇄 작업 (임시 기억 장치의) Queue에 저장하고 다른 작업을 수행
2. 프린터
   : 인쇄 작업 Queue에서 데이터(data)를 받아 Queue에 들어온 문서를 순서대로 인쇄

function queuePrinter(bufferSize, capacities, documents) {
  // bufferSize : 작업 공간의 크기
  // capacities : 작업 공간의 용량
  // documents : 인쇄할 문서

  let workSpace = []

  let currentDocument = documents.shift()
  workSpace.push(currentDocument)
  // workSpace에 처음 인쇄할 문서를 넣어줌

  let timer = 1
  // 타이머 : 1초에서 시작

  let workSpaceVolume = currentDocument

  // 남은 작업 공간에 0을 채워줌
  for(let i = 0; i < bufferSize - 1; i++) {
    workSpace.push(0)
  }

  while(workSpaceVolume > 0) {
    workSpaceVolume = workSpaceVolume - workSpace.pop() 
    currentDocument = documents.shift()
    
    if(workSpaceVolume + currentDocument <= capacities) {
      // 작업 공간에 문서 추가로 넣어줌
      workSpace.unshift(currentDocument)
      workSpaceVolume = workSpaceVolume + currentDocument
    } else {
      // 용량이 넘쳐 문서를 추가할 수 없을 때
      workSpace.unshift(0)
      documents.unshift(currentDocument)
    }

    timer++
  }
  
  return timer
}