JS => 자료구조 (Stack, Queue)

자료구조란?

데이터는 체계적으로 정리하여 저장해두는 게,
데이터를 활용하는 데에 있어 유리하다.

형님 개발자들은 그래서 무수한 상황 속에서 데이터를 효율적으로 다룰 수 있는 방법을 모두 모아,
"자료구조"라는 이름을 붙였다.

그 중,
자주 등장하는 네 가지(Stack, Queue, Tree, Graph)의 자료구조를 간단하게 정리해보겠다.

---

Stack

Stack은 직역 그대로,
데이터를 순서대로 쌓는 자료구조다.

위 그림에서 알 수 있듯이,
가장 먼저 들어간 자동차는 가장 나중에 나올 수 있다.
즉, 가장 나중에 들어간 자동차가 가장 먼저 나올 수 있는 것이다.

Stack의 실사용 예제로,
브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 자료구조 Stack이 활용된다.

브라우저 뒤로, 앞으로 가기 구현

function browserStack(actions, start) {
<br>
  let preArr = []; // 뒤로 가기에 저장하기 위한 빈배열
  let lastArr = []; // 앞으로 가기에 저장하기 위한 빈배열
<br>  
  for(let i = 0; i < actions.length; i++) {  
    if(typeof actions[i] === 'string') { 
      lastArr = []; // 'String'일 때 lastArr 비워줌
      preArr.push(start) // 뒤로 가기 배열에 현재 페이지 넣어줌
      start = actions[i] // 현재 페이지 재할당
    } 
    else if(actions[i] === -1 && preArr.length !== 0) {
      lastArr.push(start)
      start = preArr.pop();
    }
    else if(actions[i] === 1 && lastArr.length !== 0) {
      preArr.push(start);
      start = lastArr.pop();
    }
  }
  return [preArr, start, lastArr]
}

입출력 예시

인자1: actions
String과 Number 타입을 요소로 갖는 브라우저에서 행동한 순서를 차례대로 나열한 배열
<br>
인자2: starts 
String 타입의 시작 페이지를 나타내는 현재 접속해 있는 대문자 알파벳
<br>
let actions = ["B", "C", -1, "D", "A", -1, 1, -1, -1];
let start = "A";
<br>
let output = browserStack(actions, start);
console.log(output); // [["A"], "B", ["A", "D"]]

---

Queue

Queue는 직역하면 줄을 서서 기다리다, 대기 행렬이라는 뜻을 가지고 있다.
Stack과 반대되는 개념으로 먼저 들어간 데이터가 먼저 나오는 특징을 가지고 있다.

위 사진처럼 Queue 자료구조는 톨게이트를 예시로 들 수 있고,
자동차는 데이터로 비유할 수 있다.

Queue의 실사용 예제로,
순서대로 출력되는 프린터로 예시를 들 수 있다.

프린터 구현

function queuePrinter(bufferSize, capacities, documents) {
<br>
  let result = []; // 이동문서칸을 만들어줄 공간
  let totalSize = 0; // result의 현재 총버퍼 공간 용량
  let currentDoc = 0; // 현재 이동한 documents 요소
  let count = 0; // 모두 인쇄되는 데 최소 시간(초)
<br>
  for(let i = 0; i < bufferSize; i++) {
    result.push(0) // [0, 0] // result 공간 안에 버퍼사이즈 만큼 공간 만들어줌
  }
<br>
  currentDoc = documents.shift(); // 현재 이동한 문서
  result.unshift(currentDoc); // 현재 이동한 문서를 공간에 넣어줌
  result.pop(); // [7, 0] // 총 두 칸이기 때문에 한 칸 지워줌
  totalSize += currentDoc; // 현재 공간에 들어가 있는 문서 용량에 더해줌
  count++; // 인쇄목록 공간에 넣어줬으니 1초 증가
<br>
  while(totalSize > 0) { // 인쇄가 다 될 경우까지
    currentDoc = documents.shift(); // 4 할당 // [5, 6] 남음
    totalSize -= result.pop(); // 꽉 찼을 경우 대비 총 두 칸이기 때문에 한 칸 지워줌 
<br>
    if(currentDoc + totalSize <= capacities) { // 총 허용용량 이하라면
      result.unshift(currentDoc); // 인쇄 목록에 추가
      totalSize += currentDoc; // 현재 공간에 들어가 있는 문서 용량에 더해줌
    }
    else {
      documents.unshift(currentDoc); // 문서 목록에 못들어가면 대기중인 문서 다시 원위치
      result.unshift(0); // 인쇄 목록 한 칸 이동하며 빈 공간에 0 할당
    }
    count++; // 1초 증가
  }
  return count;
}

입출력 예시

인자1: bufferSize
Number 타입의 인쇄 작업 목록 크기
<br>
인자2: capacities
Number 타입의 인쇄 작업 목록에 추가될 수 있는 최대 용량
<br>
인자3: documents
Number 타입을 요소로 갖는 문서 크기가 나열된 배열
<br>
let bufferSize = 2;
let capacities = 10;
let documents = [7, 4, 5, 6];
<br>
let output = queuePrinter(bufferSize, capacities, documents);
console.log(output) // 8