---

스택(Stack)

1. 스택이란?

스택(Stack)은 데이터를 쌓아 올린 형태의 선형 자료구조로, LIFO(Last In, First Out) 원칙을 따릅니다. 즉, 가장 마지막에 추가된 데이터가 가장 먼저 제거되는 구조
실생활에서는 접시를 쌓아두는 모습, 프링글스 통에서 감자칩을 꺼내는 모습이 대표적인 예

---

2. 스택의 주요 연산

스택에서는 오직 한 쪽(Top)에서만 데이터의 추가와 삭제가 일어납니다.
주요 연산은 다음과 같습니다.

• Push: 스택의 맨 위(Top)에 요소를 추가
• Pop: 스택의 맨 위(Top) 요소를 제거 및 반환
• Peek(Top): 스택의 맨 위 요소를 제거하지 않고 확인
• isEmpty: 스택이 비어있는지 확인
• Size: 스택에 들어있는 요소의 개수 반환

// Stack() : 생성자 함수로 초기 데이터 설정
function Stack(array) {
  this.array = array ? array : [];
}

// getBuffer() : 객체 내 데이터 셋 반환
Stack.prototype.getBuffer = function () {
  return this.array.slice();
}

// isEmpty() : 객체 내 데이터 존재 여부 파악
Stack.prototype.isEmpty = function () {
  return this.array.length == 0;
};

// push() : 데이터 추가
Stack.prototype.push = function (element) {
  return this.array.push(element);
}

// pop() : 데이터 삭제
Stack.prototype.pop = function () {
  return this.array.pop();
}

// peek() : 가장 끝 데이터 반환
Stack.prototype.peek = function () {
  return this.array[this.array.length - 1];
}

// size() : 스택 내 데이터 개수 확인
Stack.prototype.size = function () {
  return this.array.length;
}

// indexOf() : 데이터 위치 값 조회
Stack.prototype.indexOf = function (element, position = 0) {
  /* case 1 */
  // return this.array.indexOf(element, position);
  /* case 2 */
  for (let i = position; i < this.array.length; i++) {
    if (element == this.array[i]) return i;
  }

  return -1;
};

// includes() : 데이터 존재 여부 확인
Stack.prototype.includes = function (element, position = 0) {
  /* case 1 */
  // return this.array.includes(element);
  /* case 2 */
  for (let i = position; i < this.array.length; i++) {
    if (element == this.array[i]) return true;
  }

  return false;
};

각 연산은 일반적으로 시간 복잡도 $O(1)$로 매우 빠르게 수행됨.

---

3. 스택의 구현 방식

스택은 배열(Array)과 연결리스트(Linked List) 두 가지 방식으로 구현할 수 있음

구현 방식	특징
배열 기반	고정 크기(Static), 빠른 인덱스, 접근 크기 제한, 오버플로우 발생 가능
연결리스트 기반	동적 크기(Dynamic), 메모리 효율적, 포인터 관리 필요, 구현이 다소 복잡

• 배열 기반 스택: 크기가 고정되어 있어 미리 최대 크기를 정해야 하며, 인덱스 접근이 빠름.
• 연결리스트 기반 스택: 크기 제한이 없고, 필요에 따라 메모리가 할당되어 유연함

---

4. 스택의 활용 사례

스택은 다양한 분야에서 핵심적인 역할을 합니다.

• 함수 호출 관리(Recursion/Call Stack)
  함수가 호출될 때마다 현재 상태를 스택에 저장, 함수 종료 시 스택에서 꺼내 복귀

• 수식 계산 및 괄호 검사
  중위/후위/전위 표기법 변환, 괄호의 짝이 맞는지 검사할 때 활용

• 브라우저 뒤로가기(Undo/Redo)
  사용자의 이전 작업 상태를 스택에 저장, 뒤로가기/앞으로가기 기능 구현

• 문자열 역순 출력
  문자열을 한 글자씩 스택에 넣었다가 꺼내면 역순으로 출력 가능.

• 운영체제의 프로세스 스케줄링
  프로세스의 상태 저장 및 복원에 활용

---

5. 스택의 장단점

장점

• 구현이 간단하고, 삽입/삭제 연산이 매우 빠름(O(1))
• 함수 호출, undo/redo 등 다양한 분야에서 필수적으로 사용

단점

• 중간 요소에 직접 접근 불가(Top에서만 접근 가능)
• 배열 기반 스택은 크기 제한이 있을 수 있음