Stack

데이터를 순서대로 쌓는 자료구조
입력과 출력이 하나의 장소, 스택의 최상단에서만 이루어지는 제한적 접근
후입선출 LIFO(Last In First Out), FILO(First IN Last Out)

• 배열에서 push와 pop만을 사용하는 경우라고 생각해도 될 것 같음

실사용 예

• 브라우저의 뒤로 가기, 앞으로 가기 기능 구현(방문기록)
• 실행 취소(가장 나중에 실행된 것부터 실행이 취소됨)

Stack의 특징

후입선출

먼저 들어간 데이터는 가장 나중에 나오는 구조

const stack = [];
stack.push(1) // [1]
stack.push(2) // [1,2]
stack.pop() // 2 , [1]
stack.push(3)  // [1,3]
stack.pop() // 3, [1]
stack.pop() // 1

스택 구조 내에서 특정 데이터를 조회하는 것은 불가능, 스택의 최상단에만 데이터를 저장하고 꺼낼 수 있음
데이터를 저장하거나 검색할 때 항상 스택의 최상단에서만 행위가 이루어지기 때문에 저장, 검색 프로세스가 매우 빠름

하나의 입출력 방향

스택이 최상단에서만 데이터를 저장하고 출력할 수 있음

데이터는 하나씩 넣고 뺄 수 있음

스택에 하나씩 여러 번 데이터를 넣어 스택 내부에 데이터가 여러 개 쌓여 있어도, 뺄 때는 한 번에 한 개의 데이터만 빼낼 수 있음

Stack 구현

class Stack {
  constructor() {
    this.storage = {}; // 데이터가 저장되는 변수
    this.top = -1; // 스택의 가장 상단을 가리키는 포인터 변수
  }
  // 스택의 크기
  size() {
    return this.top+1;
  }
  push(element) { // stack.push(1)
    this.top += 1; // top : 0
    this.storage[this.top] = element; // [1]
  }
  pop() {
    // 스택이 비어있을 경우 함수 종료
    if (this.size() <= 0) {
      return;
    }
    const result = this.storage[this.top];
    delete this.storage[this.top];
    this.top -= 1;
    return result;
  }
}