목차

• Stack이란
• Stack은 언제 사용할까?
• Stack의 시간복잡도
• JS로 Stack 구현하기

Stack이란

• 스택의 가장 큰 특징은 후입선출('LIFO') 또는 선입후출('FILO') 입니다.
  즉 가장 최근에 들어온 데이터가 가장 먼저 나간다는 의미입니다.

• 데이터(Data)가 삽입과 삭제가 한곳에서만 이루어지는것이 특징입니다.

• 아래의 그림에서 pop 즉 값을 꺼낼경우 가장 마지막에 들어간 값인 5가 나온다

Stack은 언제 사용할까?

• 마지막 값을 수정 하는경우 사용한다.
• 뒤로가기 가장 마지막에 들어온 페이지를 되돌리는 경우
• 되돌리기 가장 마지막에 작성한 글을 되돌리는 경우
• 프링글스 꺼내먹기 가장 마지막에 담은 프링글스 과자를 제일 먼저 꺼내먹는 경우

Stack의 시간복잡도

• Data를 삽입하는 경우 O(1)
• Data를 삭제하는 경우 O(1)
• Data를 찾는 경우 최악의 경우 O(n)

JS로 Stack 구현하기

• Stack의 ADT : ADT란 추상 자료형이라고도 하며, 데이터를 구체적으로 구현하는 방식은 생략하고 데이터의 추상적인 형태와 데이터를 이루는 방법만을 정해놓은 것입니다.

  ADT	설명
  push	Stack에 값을 맨위(맨뒤)에 추가
  pop	Stack의 맨위(맨뒤)에 있는 요소 삭제
  peek	Stack의 맨위(맨뒤)에 있는 요소 확인
  clear	Stack의 모든 요소 삭제
  empty	Stack의 값이 있는지 없는지 확인

  class Stack {
    constructor() {
      this.arr = [];
    }

    push(value) {
      this.arr.push(value);
    }

    pop() {
      if (this.arr.length <= 0) return null;
      return this.arr.pop();
    }

    peek() {
      return this.arr[this.arr.length - 1];
    }

    clear() {
      return (this.arr = []);
    }

    empty() {
      return this.arr.length > 0 ? false : true;
    }
  }

  const stack = new Stack();
  stack.push(1);
  console.log(stack.pop()); // 1

  stack.push(2);
  console.log(stack.peek()); // 2

  stack.push(3);
  stack.push(4);
  stack.push(5);
  stack.clear();
  console.log(stack.pop()); // null

  stack.push(3);
  console.log(stack.empty()); // false
  stack.clear();
  console.log(stack.empty()); //true