[알고리즘 자료구조] JavaScript 스택(Stack) 구현해보기

스택(Stack)과 큐(Queue)는 프로그래밍이라는 개념이 탄생할 때 부터 있었던 가장 고전적인 자료구조 중 하나이다.
하지만 이 두 자료는 자바스크립트(JavaScript)에 내장되어 있지 않지만, 배열(Array)과 내장함수들을 사용하여 스택(Stack)과 큐(Queue)를 흉내낼 수는 있다.

대부분의 알고리즘 문제를 풀어야 할 경우 배열을 이용하더라도 통과하는 편이지만, 시간복잡도를 매우 세세하게 관리하거나 데이터의 양이 매우 큰 경우에는 이와 같은 방법으로는 통과할 수 없는 경우가 존재하기도 한다.

스택 (Stack)

• 스택은 자료구조형에 속한다.
• 먼저 들어간 자료가 나중에 나오는 후입선출 자료구조로 LIFO(Last In First Out) 라고도 부른다.
• 데이터를 입력하는 push()와 데이터를 제거하는 pop()등의 작업을 할 수 있다.
• ctrl+Z로 이전 작업을 취소하는 동작 등에서 사용된다.

method

• push : 스택의 맨 위에 아이템을 삽입한다
• pop : 스택 맨 위의 아이템을 제거하고 및 그 아이템을 반환한다
• contains : 해당 아이템이 스택에 존재하는지 확인한다
• size : 현재 스택에 있는 아이템의 총 개수를 반환한다

사용 예시

• 재귀 알고리즘
• 재귀적으로 함수를 호출해야 하는 경우에 임시 데이터를 스택에 넣어준다.
• 재귀함수를 빠져 나와 퇴각 검색(backtrack)을 할 때는 스택에 넣어 두었던 임시 데이터를 빼 줘야 한다.
• 스택은 이런 일련의 행위를 직관적으로 가능하게 해 준다.
• 또한 스택은 재귀 알고리즘을 반복적 형태(iterative)를 통해서 구현할 수 있게 해준다.
• 웹 브라우저 방문기록 (뒤로가기)
• 실행 취소 (undo)
• 역순 문자열 만들기
• 수식의 괄호 검사 (연산자 우선순위 표현을 위한 괄호 검사)Ex) 올바른 괄호 문자열(VPS, Valid Parenthesis String) 판단하기
• 후위 표기법 계산

JavaScript 배열로 스택(Stack) 구현

export default class Stack {
  constructor() {
    // item들을 받을 배열 생성
    this.items = [];
  }

  push(item) {
    this.items.push(item);
  }

  pop() {
    return this.items.pop();
  }

  peek() {
    if (this.items.length === 0) {
      return null;
    }
    // items 배열의 마지막 item만 가져와준다. pop()과 다르게 배열에서 아이템이 빠지는 것이 아닌 유지된 채로 마지막 값만 받아와줌
    return this.items[this.items.length - 1];
  }

  getSize() {
    return this.items.length;
  }

  isEmpty() {
    return this.getSize() === 0;
  }
}