자료 구조 (Data Structure) - stack 정리, 자바스크립트(JavaScript)로 구현하기

스택 (Stack)

 

앞서 정리한대로 자료구조란 자료를 저장하는 방법이라고 볼 수 있으며, 오늘은 자료 구조 중 스택 (Stack)에 대해 설명할 것이다.

 

스택은 간단하게 말하면 후입 선출 개념이다. (LIFO: last in, first out)

 

스택을 우리말로 번역하자면, '더미'이다. 

더미? 더미인데 그래서?라고 생각 할 수 있는데 이 더미를 쉽게 접시 더미로 생각을 해보자

 

접시를 하나씩 쌓아 올린다고 가정했을 때,  접시가 두 개, 세 개 ~ 점점 쌓일 것이다.

그 접시 더미에서 갑자기 처음에 쌓은 접시를 빼고 싶다면? 그냥 뺄 수는 없고 위에서 부터 하나씩 빼서 접시를 꺼내야 할 것이다.

 

물론.. 그냥 위에 있던 접시 한바가지를 그냥 손으로 잡고 들 수도 있지만!! 그냥 이 자료구조 stack에서는 마지막에 들어온 접시부터 빼야한다고 생각했으면 좋겠다.

 

stack (LIFO: last in, first out).

 

stack complexity

 

장점 

데이터의 삽입과 삭제가 빠르다.

 

단점

중간에 원하는 데이터를 넣을 수 없다.

 

javaScript를 통해 구현할 기능 

push(element) - 요소를 스택의 최상단에 추가한다.

pop() - 스택의 최상단에서 요소를 제거하고 반환한다.

size() -  스택의 현재 요소 개수를 반환한다.

 

상기 기능 중 push와 pop은 array method와 동일하게 구현했다.

 

stack JavaScript 구현

class Stack {
  constructor() {
  // data가 담길 곳
    this.storage = {};
  // data의 추가 횟수를 카운팅한다
    this.top = 0;
  }

  size() {
    return Object.keys(this.storage).length;
  }

  push(element) {
    this.storage[this.top] = element;
    this.top++;
  }

  pop() {
    let lastEle = this.storage[this.top - 1];

    delete this.storage[this.top - 1];
    this.top = this.top - 1;
    
    return lastEle;
  }
}