자료구조 4장 - 스택

스택(Stack) 개요

스택(Stack)은 가장 단순하지만 강력한 자료구조 중 하나입니다.
자료를 한쪽 방향(Top)에서만 넣고 빼는 구조로, LIFO (Last In, First Out) 원칙을 따릅니다.

쉽게 말하면, 컵 쌓기와 같습니다. 맨 위에 컵을 쌓고, 맨 위의 컵만 꺼낼 수 있는 구조예요.

---

1️⃣ 스택의 구조

• Top(탑) : 삽입과 삭제가 일어나는 위치
• Push : 스택에 데이터를 넣는 연산
• Pop : 스택에서 데이터를 꺼내는 연산
• Peek/Top : 현재 스택의 가장 위에 있는 데이터를 확인하는 연산

---

2️⃣ 스택의 장점과 단점

✅ 장점

• 구현이 간단하다.
• 함수 호출(재귀), 수식 계산, 브라우저 뒤로가기 등 실제 응용이 많음.

❌ 단점

• 중간 데이터에 접근할 수 없다. (Top에서만 접근 가능)
• 크기가 제한된 경우(배열 기반) 오버플로우/언더플로우 발생 가능

---

3️⃣ 스택의 주요 연산

Push (삽입)

데이터를 스택의 Top에 추가합니다.

void push(int stack[], int& top, int size, int x) {
    if (top >= size - 1) {
        cout << "Stack Overflow\n";
        return;
    }
    stack[++top] = x;
}

---

Pop (삭제)

스택의 Top 데이터를 꺼내고 제거합니다.

int pop(int stack[], int& top) {
    if (top < 0) {
        cout << "Stack Underflow\n";
        return -1;
    }
    return stack[top--];
}

---

Peek (탑 원소 확인)

int peek(int stack[], int top) {
    if (top < 0) {
        cout << "Stack is Empty\n";
        return -1;
    }
    return stack[top];
}

---

4️⃣ 스택의 성능 분석

연산 시간 복잡도 설명

Push	O(1)	Top에 원소 추가
Pop	O(1)	Top 원소 제거
Peek	O(1)	Top 원소 확인

스택은 삽입, 삭제, 조회가 모두 O(1) 로 매우 효율적입니다.

---

5️⃣ 스택의 활용 예시

• 함수 호출 관리 (Call Stack)
  → 재귀 호출에서 함수가 순차적으로 쌓였다가 반환될 때 하나씩 Pop 됨
• 문자열 역순 출력
  → 문자를 차례대로 Push 후, Pop 하면서 꺼내면 문자열이 뒤집힘
• 수식 계산
  → 후위 표기법(Postfix) 계산에 활용
• 브라우저 뒤로가기 / 실행 취소 (Undo 기능)
  → 최근 작업을 순서대로 되돌릴 수 있음

---

결론

스택은 단순한 구조이지만, 실제 프로그램 내부에서 광범위하게 사용되는 핵심 자료구조입니다.
특히, 재귀와 수식 계산, 프로그램 실행 흐름 제어 같은 곳에서 없어서는 안 될 도구죠.