자바스크립트를 예제로 하는 자료구조와 알고리즘 4 - 스택(Stack)

스택은 책을 하나씩 쌓아 올리고 내리는 것과 비슷하다.

스택에 데이터를 넣을 때에는 마지막에 넣었던 데이터 위에 쌓는다.

반대로 데이터를 꺼낼 때에는 가장 위쪽에 있는 마지막에 넣었던 데이터부터 가져온다.

LIFO(Last In First Out)를 기억하자.

마지막에 넣었던 것이 첫 번째로 나가는 구조다.

 

워낙 간단해서 다음 메소드만 구현하면 활용할 수 있고

자바스크립트는 배열의 내장 메소드를 이용하면 쉽다.

 

push는 스택에 데이터를 쌓는 메소드다.

pop은 스택의 가장 위에 있는 데이터를 꺼내서 확인하고 없애는 메소드다.

peek는 pop과 유사하다. 스택의 가장 위에 있는 데이터만 확인할 뿐이지 없애지는 않는다.

isEmpty는 스택이 비었는지 확인한다.

 

위 메소드의 시간 복잡도는 모두 O(1)이다.

 

자바스크립트 코드

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

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

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

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

  isEmpty() {
    if (this.stack.length === 0) return true;
    return false;
  }
}

const stack = new Stack();
stack.push('가');
stack.push('나');
console.log(stack.isEmpty()); // false
console.log(stack.peek()); // '나'
console.log(stack.pop()); // '나'
stack.pop();
console.log(stack.isEmpty()); // true