[자료구조] Stack in JavaScript

정의(Definition)

Data의 입구와 출구가 하나인 자료구조.

즉, 가장 나중에 들어온 Data가 나올때는 가장 먼저 나오는 LIFO(Last In First Out)의 구조를 가지는 자료구조이다.

Push(넣기) & Pop(꺼내기)이라는 두가지 주요 작업으로 이루어지는 추상적인 데이터 유형이다. Push & Pop은 최근에

추가된 최상단 요소에서 일어난다. 

 

Stack

위키백과의 설명을 보자

스택(stack)은 제한적으로 접근할 수 있는 나열 구조이다. 그 접근 방법은 언제나 목록의 끝에서만 일어난다.
끝먼저내기 목록(Pushdown list)이라고도 한다.
스택은 한 쪽 끝에서만 자료를 넣거나 뺄 수 있는 선형 구조(LIFO - Last In First Out)으로 되어 있다. 자료를 넣는 것을 '밀어넣는다' 하여 푸쉬(push)라고 하고 반대로 넣어둔 자료를 꺼내는 것을 팝(pop)이라고 하는데, 이때 꺼내지는 자료는 가장 최근에 푸쉬한 자료부터 나오게 된다. 이처럼 나중에 넣은 값이 먼저 나오는 것을 LIFO 구조라고 한다.
이를테면, a부터 b와 c를 순서대로 넣은 다음 자료를 하나씩 꺼내면 c부터 b와 a의 순서로 나오게 된다. S를 스택, x를 데이터 요소(element)라고 하자. 그러면 스택에서는 아래와 같은 중요한 연산이 존재하는 것을 알 수 있다.

스택(Stack)은 크기가 고정되거나 크기가 동적으로 변경 될 수 있다. 용량이 제한된 스택(Stack)의 경우 꽉 찬 스택에 요소를 추가하려고하면 스택 오버플로우(Stack Overflow)가 발생하고, 비어있는 스택에서 요소를 제거하려고하면 언더 플로우(Underflow)가 발생한다.

---

연산(Method)

1. push()  최상단에 요소가 추가되고 top값이 1 추가된다.
2. pop()  최상단의 요소가 삭제되고 top값이 1 감소된다.
3. peek()  Stack의 최상단 요소를 반환한다.
4. isEmpty()  Stack이 비어있을 때 true를 반환한다.
   
   

---

구현(Implementation)

JavaScript의 배열 메소드를 이용하면 참 쉽게 구현할 수 있겠지만 하드코딩을 해보도록 하자!

const stack = {};
let top = 0;

//ES6 문법을 써보도록 하자
const push = (value) => {
  top++;
  stack[top] = value;
}
  
const pop = () => {
  if ( top > 0 ) {
    delete stack[top];
    top--;
  } else {
    alert('Stack is Empty')
  }
}

const size = () => {
  console.log(top)
}