(Algorithm/Javascript) stack이란? 자바스크립트로 stack구현하기

stack 자료구조란?

stack은 자료구조 중 하나이다. 

 

stack은 데이터가 나중에 들어온 것이 먼저 나가는 구조를 가지고 있다.  (LIFO-Last In, First Out - 후입선출)

 

바구니에 담긴 cd를 생각하면 편하다. 바구니의 바닥은 막혀있기에

 

가장 아래에 있는 cd를 꺼내기 위해서는 순서대로 위에서부터 cd를 꺼내야 한다.

 

 

 

 

stack 사용처

stack은 undo 기능(사용자 명령을 저장했다가 가장 최근에 한 명령부터 되돌림) 등에 사용된다.

 

자바스크립트 엔진의 호출스텍 역시 stack 구조이다.

 

따라서 최대 호출 스택 크기를 초과하면 stack overflow 에러가 발생할 수 있다.

 

 

 

stack 구현

자바스크립트는 별도의 스택 자료구조를 제공하지 않는다.

 

대신, 자바스크립트의 배열을 사용하여 스택을 구현할 수 있다.

 

배열 메서드인 push와 pop을 이용하면 더 쉽게 구현할 수 있으나, 하단 코드에서는 직접 구현했다.

 

구현한 stack 메서드는 아래와 같다. 

 

• top(): 스택의 가장 윗 데이터를 반환한다. 스택이 비었다면 return "EMPTY"
• pop(): 스택의 가장 윗 데이터를 반환한 뒤, 삭제한다. 스택이 비었다면 return "EMPTY"
• push(): 스택의 가장 위에 요소를 추가한다. 스택이 가득 찼다면 return "OVERFLOW"
• empty(): 스택이 비었다면 true을 반환하고, 그렇지 않다면 false을 반환한다

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

  push(item) {
    if (this.stack.length === this.stackMaxSize) return "OVERFLOW";
    this.stack[this.stack.length] = item;
  }

  pop() {
    if (this.stack.length === 0) return "EMPTY";
    const popItem = this.stack[this.stack.length - 1];
    this.stack.length -= 1;
    return popItem;
  }

  top() {
    if (this.stack.length === 0) return "EMPTY";
    return this.stack[this.stack.length - 1];
  }

  empty() {
    return this.stack.length === 0;
  }
}

const stack = new Stack(5);

console.log(stack.empty()); //true
console.log(stack.pop()); //"EMPTY"
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
console.log(stack.push(6)); //"OVERFLOW"
console.log(stack.top()); //5
console.log(stack.empty()); //false
console.log(stack.pop()); //5
console.log(stack.stack); //[ 1, 2, 3, 4 ]