what's stack?

'쌓다, 쌓이다, 포개지다'의 의미인 스텍은,
위로 쌓아 놓은 접시처럼 데이터(data)를 순서대로 쌓는 자료구조이다.

이 스텍의 특징은 막힌 통과 같은 구조에 데이터를 저장했기 때문에
한 방향으로만 데이터에 접근할 수 있다는 것.
즉, 가장 안쪽 데이터는 FILO, LIFO의 특징 상 가장 마지막으로 접근할 수 있다.

특징

• 구현이 단순하여 쉽고 데이터의 저장 및 검색 속도가 빠르다.
• 저장할 수 있는 데이터의 limit을 미리 정해야한다.
  즉, 저장공간의 낭비가 발생한다.
• 프로세스 실행구조의 기본으로 사용되는 자료구조

[Stack] 구현

class Stack {
  constructor() {
    this.storage = {}; // 스텍 저장소 생성!
    this.count = 0; // 스텍에 쌓이는 데이터를 세 줄 카운트 셋팅
  }
  
// 스텍에 보유한 데이터 수를 확인하는 메소드
  size() { 
    return this.count;
  }

// 스택에 데이터를 추가하는 메소드
  push(element) {
    this.storage[this.count] = element; 
    // 저장소는 객체. key는 count고 value는 element. 
    // {this.count: element} 즉, arr[this.count] = element
    this.count++; 
    // 현재 count에 데이터를 추가했으니 다음 count로 element 맞을 준비!
  }
  
// 스텍에 데이터를 제거하는 메소드
// 가장 나중에 추가된 데이터가 가장 먼저 추출 LIFO 
  pop() {
    // 예외 case 작성: 빈 스텍에 메소드를 적용할 시 에러가 나지 않도록!
    if (!this.size()) { // 저장된 데이터가 없으면 아무 것도 하지마!
      return; 
    } // size() 대신 count를 넣어도 된다. 요소가 있다면 count는 무조건 1 이상이니!
   
    const lastEl = this.storage[this.count - 1]; 
    // 왜 this.top - 1이 마지막 인덱스를 나타낼까?
    // push()하고 새로운 요소 맞으려 + 1 한 것이 현재 this.count니까!
    
    delete this.storage[this.count - 1]; 
    this.count--; 
    // 마지막 요소를 삭제하고 인덱스도 하나 빼줘야 스텍 업데이트 완료!
    
    return lastEl;
  }
}

Stack 활용

브라우저의 뒤로 가기, 앞으로 가기 기능을 구현할 때 자료구조 Stack 활용!

문제
인터넷 브라우저에 행동한 순서가 들어있는 배열 actions와 시작 페이지 start가 주어질 때 마지막에 접속해 있는 페이지와 방문했던 페이지들이 담긴 스택을 반환하라.

조건

• 새로운 페이지로 접속할 경우
  prev 스택에 원래 있던 페이지를 넣고 next 스택을 비운다.
• 뒤로 가기 버튼을 누를 경우
  원래 있던 페이지를 next 스택에 넣고
  prev 스택의 top에 있는 페이지로 이동한 뒤
  prev 스택의 값을 pop한다.
• 앞으로 가기 버튼을 누를 경우
  원래 있던 페이지를 prev 스택에 넣고
  next 스택의 top에 있는 페이지로 이동한 뒤
  next 스택의 값을 pop한다.
• 뒤로 가기, 앞으로 가기 버튼이 비활성화일 경우
  (클릭이 되지 않을 경우)에는 스택에 push 하지 않는다.

주의사항

• 새로운 페이지 접속은 알파벳 대문자로 표기
• 뒤로 가기 버튼을 누른 행동은 -1로 표기
• 앞으로 가기 버튼을 누른 행동은 1로 표기
• 다음 방문할 페이지는 항상 현재 페이지와 다른 페이지로 접속
• 방문한 페이지의 개수는 100개 이하
• 반환되는 출력값 배열의 첫 번째 요소 prev 스택, 세 번째 요소 next 스택은 배열.
  스택을 사용자 정의한다면 출력에서는 배열로 변환해야 한다.

function browserStack(actions, start) {
// action에 따른 데이터를 쌓기 위한 스텍 저장소를 생성하자
  let prevStack = [];
  let nextStack = [];
// 현재 페이지가 계속 변경되니 새로운 변수에 할당하자
  let currentPage = start;

// action에 따라 데이터를 옮기기 위해 배열을 훑자
  for (let action of actions) {
    // 뒤로가기 눌렀을 때 솔루션
    // 💡 핵심는 이전 페이지(prevStack)에 데이터가 있어야 한다는 것!
    if(action === -1 && prevStack.length) {
      nextStack.push(currentPage);
      // 현재 페이지는 다음 페이지에 넣어주고
      currentPage = prevStack.pop();
      // 이전 페이지의 가장 최근 것을 현재 페이지로 재할당!
    }
    // 앞으로 가기 솔루션
    else if (action === 1 && nextStack.length) {
      prevStack.push(currentPage);
      currentPage = nextStack.pop();
    }
    else { // 새로운 페이지에 접속했을 때! 
      prevStack.push(currentPage);
      currentPage = action;
      nextStack = [];
    }
  }
    return [prevStack, currentPage, nextStack];
}