28일차, Stack Queue

2021. 08. 26 목요일

1. Today's Key points!🔑

• stack
• queue
• ???

2. 정리해보자!🧹

자료구조에 대해 학습했다. 어떤 자료구조가 있는지를 알고 이것을 사용해서 알고리즘 문제에 접근할 수 있어야 한다.

자주 등장하는 네 가지 자료구조중 오늘은 2가지 stack과 queue에 대해 알게 되었다.

Stack이나 Queue라는 단어가 생소했다. 근데 이미 대표적인 자료구조 중에 배열이라는 자료구조를 자주 써 왔다. 스택이나 큐도 별반 다르지 않다.

우선 Stack이란? 데이터를 순서대로 쌓는 자료구조이다. 예를 들어보자면, 막혀있는 도로에 차가 들어오는 것으로 예를 들 수 있다. 막혀있는 도로에 자동차가 들어왔는데, 나가려면 뒤에 들어온차가 먼저 빠져야 앞에있던 차가 나갈 수 있다. 이것이 Stack자료 구조의 특징이다. 컴퓨터에서 사용하는 예로 들자면, 브라우저의 뒤로가기 앞으로가기 기능이 있다. 현재 페이지에서 새로운 페이지로 접속할 때, 현재 페이지가 Prev Stack에 보관된다. 그리고 뒤로 가기 버튼을 누르면 이전 페이지가 나오고 현재 페이지는 Next Stack에 보관된다. 이때, 이전 페이지가 나올때 가장 나중에 보관된 페이지가 나오게 된다. 반대로 앞으로 가기를 하면 Next Stack의 가장 마지막에 보관된 페이지를 가져온다. 이렇게 자료구조 Stack을 이용하면, 뒤로 가기와 앞으로 가기 버튼을 구현할 수 있다. 그리고 이건 번외적인 팁인데 Stack은 재귀함수와 단짝이다.

Queue란? 데이터가 들어간 순서대로 나오는 자료구조이다. 예를 들면, 톨게이트를 예로 들수 있다. 맨앞차가 요금처리를 하고 맨앞차가 먼저 지나간다. 말 그대로 먼저온 순서가 먼저 나갈 수 있다는 것이다. 컴퓨터에서 사용하는 예로 들자면, 인쇄가 있다. 우리가 문저를 작성하고 풀력 버튼을 누르면 해당 문서는 인쇄 작업 Queue에 들어간다. 그리고 프린터는 인쇄작업 Queue에 들어온 문서를 순서대로 인쇄한다. 이처럼 컴퓨터 장치를 사이에서 데이터를 주고 받을 때, 각 장치 사이에 존재하는 속도의 차이나 시간 차이를 극복하기 위해서 임시 기억 장치의 자료구조로 Queue를 사용한다. 그리고 이건 번외적인 팁인데 Queue는 while문과 단짝이다. 

???그리고 자료구조.. 너무 어렵다. 갑자기 생소한 개념을 들어서 머리에 잘 안들어오는 것도 있고, 갑자기 난이도가 확 올라간 느낌이 들었다. 그래서 하루늦게 TIL을 올리게 되었다. 아마 29일차도 제시간에 올리긴 힘들듯 하다 ㅠㅠ. 재귀함수 어렵다고 머리싸매고 있을 때가 아니었다. 한번에 이해 못하더라도 계속 보면서 익숙해지면 자연스럽게 습득될거라 믿고 일단 달려보자.

3. 코플릿 복기!🧐

위의 예시에 나온것 처럼 브라우저 뒤로가기 앞으로가기 기능과 프린터 인쇄처리를 구현해 보았다.

👉🏻브라우저 뒤로가기

function browserStack(actions, start) { //actions에 어떤 행동을 할지가 배열로 들어오게 된다.
  let prev = []; //이전 페이지를 담을 Stack
  let next = []; //다음 페이지를 담을 Stack
  let now = start; //현재 보이는 페이지
  for(let i = 0; i < actions.length; i++){ // actions 배열에 있는 데이터 하나하나 실행한다는 의미의 for문
    if(actions[i] === -1 && prev.length !== 0){ //뒤로가기가 실행되고, 이전 페이지 Stack이 비어있지 않으면
      let backPage = prev.pop(); //이전 페이지 Stack에서 마지막에 쌓여있는 페이지를 가져와 backPage에 할당
      next.push(now); //다음 페이지 Stack에 현재 페이지를 추가
      now = backPage; // 현재 보이는 페이지 이전 페이지
    }
    else if(actions[i] === 1 && next.length !== 0){ //앞으로 가기가 실행되고, 다음 페이지 Stack이 비어있지 않으면
      let nextPage = next.pop(); // 다음 페이지 Stack에서 마지막에 쌓여있는 페이지를 가져와 nextPage에 할당
      prev.push(now); // 이전 페이지 Stack에 현재 페이지를 추가
      now = nextPage; // 현재 보이는 페이지는 다음 페이지
    }
    else {
      next = []; // 이전 페이지 Stack과 다음 페이지 Stack이 모두 비어있을 때, 즉 막 브라우저를 켰을 때
      prev.push(now); // 이전 페이지 Stack에 현재 페이지를 넣어준다. 즉, 다른 페이지로 들어가게 되면 현재 페이지였던 부분이 이전페이지가 되기때문
      now = actions[i]; // 현재 보이는 페이지. 즉, actions에서 어떤것을 실행한 그 순간
    }
  }
  return [prev, now, next]
}

 

👉🏻인쇄작업

결과로 나와야 하는 값이 인쇄를 완료하는데 걸리는 시간이 결과이다. 인쇄 작업 목록에는 최대 용량만큼 문서를 담을 수 있고, 용량을 초과하게되면 그 문서가 인쇄 작업 목록에 들어가지 못하다가 인쇄가 되면서 인쇄 작업 목록에 용량이 늘어나면 그때 다시 문서가 목록에 들어갈 수 있다. 그리고 문서는 1초에 한 칸만 이동할 수 있다.

function queuePrinter(bufferSize, capacities, documents) {//documents는 각 자료의 용량을 배열로 담아서 온다. 예) [7, 4, 5, 6] ([용량 7짜리 데이터, 용량 4짜리 데이터, 용량 5짜리 데이터, 용량 6짜리 데이터])
// printList가 Queue이다.
  let printList = new Array(bufferSize).fill(0); // 인쇄작업 해야할 목록. 예를 들어, bufferSize가 3이라면 인쇄작업 목록은 3칸이 있는 것. 즉 데이터가 총 3개 들어갈 수 있음
  let printSum = 0 // 인쇄 목록에 들어있는 데이터 총량.
  let time = 0; // 흐른 시간
  
// 1초 후를 기본 셋팅 해준다.
  let now = documents.shift(); // 다큐먼트 배열에 제일 첫번째로 들어갈 자료를 now에 할당
  printList.unshift(now); // 인쇄 목록에 추가.
  printList.pop(); // 인쇄 하나 처리. pop을 해주는 이유 : bufferSize가 고정되야하기 때문.
  printSum = printSum + now; // 현재 인쇄 목록에 now가 들어왔기 때문에 그만큼 용량 추가
  time++; // 1초 증가
  while(printSum){ // 인쇄 목록에 들어이는 데이터 총량이 0이 될때 까지 반복실행
    printSum = printSum - printList.pop(); // 하나 프린트 실행하면 그만큼의 용량이 빠져나간다
    now = documents.shift(); // 다큐먼트에서 대기중이어던 자료 now에 할당
    if(printSum + now <= capacities){ // 이제 now를 printList에 넣어줄건데, 이때 용량이 초과하지 않으면
      printList.unshift(now); // printList에 now를 넣어준다.
      printSum = printSum + now; // 인쇄 목록에 데이터 총량 now만큼 추가.
    }
    else { //용량이 초과하면
      print.unshift(0); //대기하고 있던 자료가 못들어가기 때문에 0을 넣어준다.
      documents.unshift(now); // 인쇄하나 실행
    }
    time++; // 1초 증가
  }
  return time;
}