[자료구조] 스택 (Stack)

1. 무엇인가
   • 일반 명사 : 무더기, 많음, 쌓다. 채우다. 쌓아올린 더미
   • 고유 명사 : 후입 선출 구조(Last In First Out)로 마지막 삽입된 자료부터 출력 혹은 삭제되는 형태의 자료구조
2. 왜 사용하는가?
   스택의 후입선출(LIFO) 특성이 필요한 곳에 사용한다.
   - 함수의 호출 관리 : 프로그래밍에서 함수를 호출할 때, 각 함수의 반환 주소와 지역 변수를 저장하는데 스택을 사용한다.
   이는 프로그램이 어떤 함수를 언제 끝내고 다음 작업으로 넘어가야 하는지를 정확히 관리할 수 있게 해준다.
   - 역순 문자열 생성 : 문자열을 역순으로 만들 때 스택을 사용할 수 있다. 문자열의 문자를 하나씩 스택에 넣은 다음, 하나씩 꺼내면 원래 문자열의 역순을 얻을 수 있다.
   - 괄호 검사 : 수학적 수식이나 프로그래밍 코드에서 괄호가 올바르게 열리고 닫히는지 확인할 때 스택을 사용할 수 있다. 열린 괄호는 스택에 푸시하고, 닫힌 괄호가 나타나면 스택에서 괄호를 팝하여 짝이 맞는지 확인한다.
   - 뒤로 가기 기능 : 웹 브라우저에서 페이지 방문 기록을 관리하기 위해 스택을 사용할 수 있다. 사용자가 새 페이지로 이동할 때마다 그 주소를 스택에 푸시하고, 뒤로 가기 버튼을 클릭할 때 스택에서 주소를 팝하여 이전 페이지로 돌아간다.
   - 재귀 알고리즘 : 재귀적인 함수나 알고리즘을 구현할 때 스택을 사용하여 각 재귀 호출의 상태를 저장하고, 모든 호출이 완료된 후에 이전 상태로 돌아가기 쉽게 한다.
   
   
3. 장단점
   
   1. 장점
      - 구조가 단순해서 구현이 쉽다.
      - 데이터 저장, 읽기 속도가 빠르다.
   2. 단점 (배열로 스텍 구현 시)
      - 데이터 최대 갯수가 정해져 있다.
      - 저장 공간의 낭비가 발생한다.
4. 어떻게 사용하는가
   
   • 스택의 추상 자료형
     - push() - 데이터 삽입
     - pop() - 데이터 제거
     - top() - 데이터 참조 (스택의 가장 위에 있는 자료를 반환)
     - isEmpty() - 비어있는지 체크
   • 자바스크립트 코드로 스택 만들어보기
     이전 글 [자료구조] - 연결리스트, https://steadyg.tistory.com/34 에서 만들었던, LinkedList를 통해서,
     Stack을 만들어보았다.

import { LinkedList } from './linkedList.mjs';

class Stack{
  constructor(){
    this.list = new LinkedList();
  }

  push(data){
    this.list.insertAt(0, data)
  }

  pop(){
    try {
      this.list.deleteAt(0);
    } catch(e) {
      return null;
    }
  }

  top(){
    return this.list.getNodeAt(0);
  }

  isEmpty(){
    return this.list.count === 0;
  }

}

export { Stack };

참조한 글들
- https://terms.naver.com/entry.naver?docId=2837556&cid=40942&categoryId=32841
- https://jettstream.tistory.com/188
- chatGPT
- 인프런 감자 강좌, https://www.inflearn.com/users/17036/@%EA%B0%90%EC%9E%90