# Stack

👉Goal

자료구조 동작 원리를 이해, 장단점 파악

자료구조란?

다양하고 수 많은 데이터들을 어떻게 효율적으로 관리 할 것인지 표현하는 것. ex) 도서관에서의 책 분류

자료구조는 크게 두가지로 분류

선형 구조(1대1 자료간 관계) - Array, Stack, Queue, Dequeue, List

비선형 구조(1대N 또는 N대M의 자료간의 관계) - Tree, Graph, Binary Tree, Heap

👉Stack(스택)

Stack은 후입선출(Last In First Out: LIFO)의 자료구조

먼저 입력된 값이 제일 마지막에 출력 가능한 자료구조

스택이 실행될 때 추상적 이미지

< 만약 Stack에 모든 원소를 집어넣었다가 출력하면 출력된 리스트는 처음 리스트의 역순이 된다. >

Stack의 경우 Array 메서드의 Push, Pop을 생각하면 쉽다.

Stack을 쌓는것은 Push / Stack에서 빼내는 것은 Pop

Stack 구현시 필요 변수

MAX_SIZE : Stack의 사이즈, Array : 데이터를 담을 배열, top : Stack의 포인터, 초기값 = -1

top은 현재 stack안에 쌓여진 데이터 중에 가장 마지막 데이터 위치를 뜻한다. 만약 Stack 안에 아무것도 없을 시를 생각해서 top의 초기값을 -1로 설정하고, 하나의 데이터가 Stack안에 쌓인다면 stack의 index = 0 이므로 top의 값도 0으로 설정 될 수 있도록 한다.

Stack 오류

stack overflow / stack underflow

주어진 stack메모리보다 데이터를 더 넣었거나, stack이 메모리가 비어있는데 거기서 데이터를 꺼내려고 할 때 발생하는 대표적인 에러 ex) 재귀함수 무한 호출시

장점: 간단하게 구현 가능 단점 : 스택의 크기가 불확실 할때에는 확장시 확장연산이 오래 걸린다.

👉Stack(Pseudo Code)

var stackArr = [];			// 빈배열 생성
var element1 = 'air';		// 추가할 요소1
var element2 = 'fire';		// 추가할 요소2
stackArr.push(element1);	// 배열에 요소1 추가
stackArr.push(element2);	// 배열에 요소2 추가
console.log(stackArr);		//	['air','fire'];
stackArr.pop();				// 요소 2번째 제거

👉Stack(functional)

const Stack = function() {
  const someInstance = {};

  // Use an object with numeric keys to store values
  const storage = {};
  var count = 0;

  // Implement the methods below
  someInstance.push = function(value) {
    storage[count] = value;
    count++;
  };

  someInstance.pop = function() {
    if (count > 0) {
      var popValue = storage[count - 1];
      delete storage[count - 1];
      count--;
      return popValue;
    }
  };

  someInstance.size = function() {
    return count;
  };

  return someInstance;
};