[4주차] Stack

+++🍒JS리스트 구현시 아래 메소드만 사용하게 제한할 것🍒+++

(Stack) push, pop
(Queue) push, shift

---

1. Stack 개념

참고 - 박재현님 / Stack(feat. Array)

위 글을 참고하여 요약 정리하였습니다 :)

---

• LIFO(후입선출)
• 프링글스 🥔
• 시간복잡도 O(1)

근데 simple LL로도 충분

• ❓왜 심플LL로 충분??
• 데이터 입출구 같음 => next node랑 link만 조작하면 됨

스택의 최상단은 Top이라는 인덱스를 통해서 유지 및 관리

📍Top 위치는 명확하게 규정되어야 함

• ex. 스택 최상단일 수도, 다음 데이터가 들어올 최상단 위치를 가리킬 수도...내맘대루 (그래도 가능한 최상단이 좋겠지)

📍스택이 완전히 비어있을 때 Top은 0이 아닌 -1을 가리켜야 함

• 배열 인덱스는 0부터 시작, Top이 0이라는건 스택에 “하나”의 자료가 있다는 뜻이기 때문
• 그래서 스택을 초기화 할때는 Top이 -1이 되도록 설정

1️⃣ Push (데이터 추가)

배열 마지막 인덱스는 “배열길이 - 1”이므로, 현재 스택의 Top의 값을 항상 확인하고 푸시 동작을 해야함

StackOverflow 주의!!

+++🍒 기본적으로 함수, 특히 재귀함수 🍒 +++
함수 실행 -> 스택구조
함수 실행종료 -> 스택 빠져나옴
따라서 무한재귀함수에서 StackOverflow 현상 발생
브라우저 함수통 용량 초과시 Max full SO size exceeded

2️⃣ Pop (데이터 꺼내오기)

Stack[Top]값을 반환하고 Top의 값을 1 감소시켜주면 됨
StackUnderflow 주의!! (스택 텅텅)
= 비어 있는 스택에서 데이터 원소를 꺼내려 할 때 발생

---

2. Stack 구현하기

class Stack로 감싸 push(), pop(), top() 메소드만 쓸 수 있게 한다
= stack에는 push(), pop(), top()만 존재

// 이런 거 없다 

arr.unshift
arr.slice
arr.unshift
arr.splice

top() = 최상단 데이터 확인 index
+++🍒참고🍒+++ 최하단 데이터 index 0

class Stack {
    arr = [];

    push(value) {
        return this.arr.push(value);
    }

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

    top() {
        return this.arr.at(-1); // 최신 문법
        // this.arr[this.arr.length -1] 옛날 방식
    }

    get length() {
        return this.arr.length;
    }
}

pop()은 배열 길이를 반환한다

+++🍒참고🍒+++
pop()과 top()을 빠르게 하고 싶으면 Tail을 만들면 됨

3. 실행 결과

const stack = new Stack();

console.log(
    stack.push(1), // 1
    stack.push(3), // 2
    stack.push(5), // 3
    stack.push(2), // 4
    stack.push(4), // 5
    stack.length, // 5
    stack.pop(), // 4
    stack.top(), // 2
)