[TIL]Stack, Queue, Tree, Graph

김용진·2021년 10월 7일

Graph queue stack tree

Achievement Goals

자료구조가 무엇인지 설명할 수 있다.
Stack, Queue, Tree, Graph 자료구조에 대해 이해할 수 있다.
- 알고리즘 문제에서 Stack, Queue 자료구조를 배열로 대체하여 흉내낼 수 있다.
- 각 자료구조의 개념과 구조를 파악하고 목적을 이해할 수 있다.
- 알고리즘 문제의 각 상황에 맞는 자료구조를 떠올릴 수 있다.
트리 및 그래프의 탐색 기법에 대해 이해할 수 있다.
- Binary Search Tree를 이해할 수 있다.
- BFS와 DFS의 개념을 이해하고 알고리즘 문제에서 사용할 수 있다.
자료구조를 활용하여 알고리즘 문제에 접근할 수 있다.

Stack

데이터를 순서대로 쌓는 자료구조
먼저 들어온 자료는 가장 나중에 나올 수 있다.
ex)브라우저 뒤로가기,앞으로 가기

coplit 브라우저 뒤로 가기 앞으로 가기

function browserStack(actions, start) {
  let prev=[] //이전 페이지 스택(뒤로가기)
  let next=[] //다음 페이지 스택(앞으로가기)
  let page=start //현재 페이지
  for(let i of actions){
    if(i===-1&&prev.length!==0){ //뒤로가기
      next.push(page)
      page=prev.pop()
    }else if(i===1&&next.length!==0){ //앞으로가기
      prev.push(page)
      page=next.pop()
    }else{ //새로운 페이지
      prev.push(page)
      next=[]
      page=i
    }
  }return([prev,page,next])
}

Queue

데이터를 줄 세우는 자료구조
먼저 들어온 자료부터 처리
ex)프린트 인쇄 작업 , Buffer

coplit 프린터

function queuePrinter(bufferSize, capacities, documents) {
  let count=0
  let queue=[] //인쇄 목록 공간
  let total = 0 //인쇄 목록에 들어있는 문서의 총 용량
  //목록 크기(칸)만큼 0을 queue에 넣어둔다.
  for(let i=0;i<bufferSize;i++){
    queue.push(0)
  }
  //첫번째문서를 인쇄 목록에 넣는 코드
  let curDocument=documents.shift()//문서하나를 빼서 현재 문서로 넣는다.
  queue.unshift(curDocument)//현재 문서를 인쇄 목록에 넣는다.
  queue.pop()//인쇄 목록 끝을 출력 빼낸다.
  total=curDocument
  count++
  //total에 아무것도 안남을때까지 반복
  while(total>0){
    total-=queue.pop()//인쇄 목록 끝 출력
    curDocument=documents.shift()
    //인쇄목록에 들어있는 문서의 총 용량이 최대용량보다 작으면 새문서를 인쇄목록에 넣는다.
    if(total+curDocument<=capacities){
      queue.unshift(curDocument)
      total+=curDocument
    //용량이 부족한 경우 0값을 인쇄목록에 넣는다.
    }else{
      documents.unshift(curDocument)//다시 문서에 현재문서를 넣는다.
      queue.unshift(0)
    }
    count++
  }
  return count
}