[자료구조] Stack의 기초

자료구조의 개념

여러 데이터들의 묶음을 저장하고 효율적으로 사용하는 방법
*특정한 상황에 놓인 문제를 해결하는 데에 특화

  • 데이터 : 문자, 숫자, 소리, 그림, 영상 등 실생활을 구성하고 있는 모든 값
    *데이터는 분석하고 정리하여 활용해야만 의미를 가질 수 있으며, 사용 목적에 따라 형태를 구분하고 분류하여 사용

Stack

1. 개념

  • 데이터를 순서대로 쌓는 구조
  • 특징 : 입력과 출력이 하나의 방향으로 이루어지는 제한적 접근
    *LIFO(Last In First Out) 혹은 FILO(First In Last Out)
  • 재귀 함수와 짝궁

2. 구조

const stack = []

stack.push(1) // [1]
stack.push(2) // [1, 2]
stack.push(3) // [1, 2, 3]
stack.push(4) // [1, 2, 3, 4]
stack.push(5) // [1, 2, 3, 4, 5]

// LIFO(Last In First Out)
stack.pop() // [1, 2, 3, 4]
stack.pop() // [1, 2, 3]
stack.pop() // [1, 2]
stack.pop() // [1]
// FILO(First In Last Out)

3. browserStack 예제

  1. 새로운 페이지로 접속할 때
    : 현재 페이지를 Prev Stack에 보관
  2. 뒤로 가기 버튼을 눌러 이전 페이지로 돌아갈 때
    : 현재 페이지를 Next Stack에 보관하고, Prev Stack에 가장 나중에 보관된 페이지를 현재 페이지로 가져옴
  3. 앞으로 가기 버튼을 눌러 앞서 방문한 페이지로 이동할 때
    :Next Stack의 가장 마지막으로 보관된 페이지를 가져옴
  4. 마지막
    :현재 페이지를 Prev Stack에 보관
function browserStack(actions, start) {
  // 출력 예시 : [[prev],current,[next]]
  // -1 : 뒤로 가기
  // 1 : 앞으로 가기

  let prev = []
  let current = start
  let next = []
  // 출력에 필요한 변수들 생성
  // current : 시작값 할당

  // 각 변수에 저장해 기억해 두기위한 재귀함수 생성
  let memo = (actions) => {
    let [head, ...tail] = actions

    for (let i = 0; i < actions.length; i++) {
      if(typeof head === 'string') { 
        //새로운 페이지 접속
        prev.push(current) 
        current = head
        next = []
      } else if(head === -1) {
        // 뒤로가기
        next.push(current)
        if(prev.length !== 0) {
          current = prev.pop()
        }
      } else if(head === 1) {
        // 앞으로 가기
        prev.push(current)
        current = next.pop()
      }
      return memo(actions.slice(1)) 
    }
  }

  // 재귀함수 실행
  memo(actions)

  return [prev, current, next]
}

좋은 웹페이지 즐겨찾기