06. 스택

06-1 스택 개념

먼저 입력한 데이터를 제일 나중에 꺼낼 수 있는 자료구조

LIFO (Last in, First Out)

자료구조란? - 자료를 잘 저장하고, 효율적으로 꺼내 쓸 수 있도록 정리해둔 설계도

스택의 어원은 ‘쌓는다’

5번이 들어오면 5번부터 나온다.

• push : 스택에 삽입하는 연산
• pop : 스택을 꺼내는 연산

---

06-2 스택의 정의

ADT(abstract data type) - 추상자료형

자료형의 설계도

인터페이스만 알고 실제로 구현되지 않은 자료형

내부 구현은 감추고, 사용자가 "어떤 기능을 수행할 수 있는지"만 알도록 설계된 자료형

🔹 ADT의 핵심 특징

1. 데이터와 연산을 추상적으로 정의 (구현 방식은 감춰짐)
2. 인터페이스만 제공하고 내부 구조는 비공개
3. 구현 방식과 상관없이 동일한 동작을 제공해야 함

---

🔹 대표적인 ADT 예시

ADT 주요 연산 설명

스택 (Stack)	push(x), pop(), peek(), isEmpty()	후입선출 (LIFO) 구조
큐 (Queue)	enqueue(x), dequeue(), front(), isEmpty()	선입선출 (FIFO) 구조
덱 (Deque)	pushFront(x), pushBack(x), popFront(), popBack()	양쪽에서 삽입/삭제 가능
리스트 (List)	insert(i, x), delete(i), get(i), size()	순서대로 저장하는 구조
집합 (Set)	add(x), remove(x), contains(x)	중복 없는 데이터 모음
맵 (Map, Dictionary)	put(k, v), get(k), remove(k)	키-값 쌍 저장

---

🔹 ADT vs. 실제 구현

• *ADT는 개념(사용 방법을 정의)**이고,
• 실제 구현은 다양한 방법(배열, 연결 리스트 등)이 있을 수 있음.

예를 들어, 스택 ADT는 내부적으로 배열 or 연결 리스트로 구현할 수 있다.

// 스택 ADT 구현 (배열 사용)
class Stack {
  constructor() {
    this.items = [];
  }
  push(x) {
    this.items.push(x);
  }
  pop() {
    return this.items.pop();
  }
  peek() {
    return this.items[this.items.length - 1];
  }
  isEmpty() {
    return this.items.length === 0;
  }
}

const stack = new Stack();
stack.push(1);
stack.push(2);
console.log(stack.pop()); // 2

---

🔹 ADT의 장점

✅ 구현을 몰라도 사용 가능 → 인터페이스만 알면 됨

✅ 여러 방식으로 구현 가능 → 최적의 방법 선택 가능

✅ 코드의 유지보수성 향상 → 내부 구현이 바뀌어도 사용법은 동일

---

🔹 정리

• ADT(추상 자료형)는 "데이터 구조 + 연산"을 정의한 개념
• 구현 방식은 감춰지고, 인터페이스만 제공됨
• 스택, 큐, 리스트, 맵 등 다양한 ADT가 존재함
• ADT는 내부 구현 방식(배열, 연결 리스트 등)에 따라 성능이 달라질 수 있음

💡 한마디로, ADT는 "사용법을 정리한 설명서" 같은 것

연산 설명

push(값)	스택에 값을 추가 (맨 위에 넣음)
pop()	스택에서 값을 제거 (맨 위에서 뺌)
isFull()	스택이 가득 찼는지 확인 (배열 기반 스택일 때 유용)
isEmpty()	스택이 비었는지 확인
top() / peek()	스택의 맨 위 값 확인 (꺼내지는 않음)

• top()은 peek()과 같은 역할.

---

🤔 isFull()은 js에서 왜 잘 안 쓰일까?

1. 배열 기반 스택에서는 유용
   • 만약 고정된 크기를 가지는 배열(Array)로 스택을 만들면, 공간이 다 차면 isFull()로 체크해야한다.
   • 예제: stack = [None] * 5 (크기 5로 제한됨)
2. 동적 배열 (JS, Python 리스트)에서는 필요 없음
   • push()를 해도 자동으로 크기가 늘어나기 때문에 isFull()을 따로 쓸 필요가 없음.
   • 그래서 자바스크립트, 파이썬에서는 잘 안 씀.

• isFull()은 고정된 크기(배열 기반) 스택에서만 의미 있음.
• 동적 크기(Array, List)를 사용하는 JavaScript, Python에서는 잘 안 씀.

---

✅ Push & Pop (스택 기본 연산)

✔ push(value) → 스택의 맨 위(top)에 데이터 추가

✔ pop() → 스택의 맨 위(top)에서 데이터 제거하고 반환

✔ LIFO (Last In, First Out) 구조

---

📌 Push & Pop 동작 과정

1️⃣ push(value) → 데이터 추가

1. isFull() 확인 → 스택이 가득 찼는지 체크
2. top++ → top을 1 증가
3. data[top] = value; → 새로운 데이터를 top 위치에 추가

2️⃣ pop() → 데이터 제거

1. isEmpty() 확인 → 스택이 비었는지 체크
2. data[top] 값을 저장 (나중에 반환)
3. top-- → top을 1 감소 (맨 위 데이터 제거 효과)
4. 제거한 데이터 반환

---

🔥 Push & Pop 구현 (JavaScript)

class Stack {
  constructor(size) {
    this.max_size = size;   // 스택 최대 크기
    this.data = new Array(size); // 배열 기반 스택
    this.top = -1;          // 스택의 초기 상태 (비어 있음)
  }

  isFull() {
    return this.top === this.max_size - 1;  // 스택이 가득 찼는지 확인
  }

  isEmpty() {
    return this.top === -1;  // 스택이 비었는지 확인
  }

  push(value) {
    if (this.isFull()) {
      console.log("스택이 가득 찼습니다!");
      return;
    }
    this.top++;             // top 증가
    this.data[this.top] = value; // 데이터 추가
    console.log(`Push: ${value} (top: ${this.top})`);
  }

  pop() {
    if (this.isEmpty()) {
      console.log("스택이 비었습니다!");
      return null;
    }
    let removedValue = this.data[this.top];  // 제거할 값 저장
    this.top--; // top 감소
    console.log(`Pop: ${removedValue} (top: ${this.top})`);
    return removedValue;
  }

  printStack() {
    console.log("Stack:", this.data.slice(0, this.top + 1));
  }
}

// 📌 사용 예시 (Push & Pop 함께 실행)
let stack = new Stack(5);
stack.push(3);  // Push: 3 (top: 0)
stack.push(5);  // Push: 5 (top: 1)
stack.push(7);  // Push: 7 (top: 2)
stack.printStack(); // Stack: [3, 5, 7]

stack.pop();   // Pop: 7 (top: 1)
stack.printStack(); // Stack: [3, 5]

stack.push(9); // Push: 9 (top: 2)
stack.printStack(); // Stack: [3, 5, 9]

---

🏗 Step-by-Step 실행 예제

동작 top 값 data 배열 상태

초기 상태	-1	[ , , , , ] (비어 있음)
push(3)	0	[3, , , , ]
push(5)	1	[3, 5, , , ]
push(7)	2	[3, 5, 7, , ]
pop() (7 제거)	1	[3, 5, , , ]
push(9)	2	[3, 5, 9, , ]

---

✅ Push & Pop 핵심 정리

연산 동작 시간 복잡도

Push	top++ 후 data[top] = value	O(1)
Pop	data[top] 제거 후 top--	O(1)

✔ 스택은 마지막에 넣은 게 먼저 나온다! (LIFO - Last In, First Out)

✔ Push는 top을 증가시키고 데이터를 저장

✔ Pop은 top 위치의 데이터를 제거하고 top을 감소