스택(Stack)

• “쌓다”라는 뜻, 데이터를 차곡차곡 쌓아 올린 구조
• 마지막에 넣은 데이터가 가장 먼저 나오는 특징
  • LIFO : Last In First Out

Stack의 핵심 동작

• push(데이터) : 스택 위에 새로운 데이터를 추가
• pop() : 스택 맨 위 데이터를 꺼내고 제거
• peek() or top() : 스택 맨 위 데이터를 제거하지 않고 조회만 한다.
• isEmpty() : 스택이 비어있는지 확인

Stack의 구조

스택은 보통 배열이나 연결 리스트(Linked List)를 이용해서 만들 수 있다.

• 배열 기반 스택 : 고정된 크기, 빠른 접근
• 연결 리스트 기반 스택 : 크기가 가변적, 메모리를 유연하게 사용

Stack의 대표적인 사용 사례

• 프로그램 실행
  • 함수 호출 스택 (함수 호출/반환 시)
• 자료구조 / 알고리즘
  • DFS(깊이 우선 탐색), 괄호 검사
• 시스템
  • 웹 브라우저 뒤로가기 기록
• 수학
  • 수식 계산 (후위 표기법 계산)
• 기타
  • Undo(되돌리기) 기능

Stack의 시간 복잡도

• push : O(1)
• pop : O(1)
• peek : O(1)
• isEmpty : O(1)

💡 스택은 모든 기본 연산이 매우 빠르다(상수 시간, O(1))

배열 스택을 가진 코드

#include <iostream>
using namespace std;

#define MAX 100  // 스택 최대 크기

class Stack {
    int arr[MAX];
    int top;  // 스택의 가장 위를 가리키는 인덱스

public:
    Stack() { 
        // 비어 있는 상태
        top = -1; 
    }

    bool isEmpty() {
        return top == -1;
    }

    bool isFull() {
        return top == MAX - 1;
    }

    void push(int value) {
        if (isFull()) {
            cout << "Stack Full\n";
            return;
        }
        arr[++top] = value;
    }

    int pop() {
        if (isEmpty()) {
            cout << "Stack Empty\n";
            return -1;  // 에러값
        }
        return arr[top--];
    }

    int peek() {
        if (isEmpty()) {
            cout << "Stack Empty\n";
            return -1;
        }
        return arr[top];
    }
};

int main() {
    Stack s;
    s.push(10);
    s.push(20);
    s.push(30);

    cout << s.pop() << endl;  // 30 출력
    cout << s.peek() << endl; // 20 출력
    cout << s.pop() << endl;  // 20 출력
}

실제 메모리 스택 구조 예시

메모리 안에서 스택의 사용

메모리 전체 공간
┌────────────────────┐
│ 코드/데이터 영역    │
├────────────────────┤
│ 힙 영역 (아래→위)   │   │ ↑↑↑ 확장
├────────────────────┤
│ 스택 영역 (위→아래) │   │ ↓↓↓ 확장
└────────────────────┘

• 스택은 주소가 높은 곳 → 낮은 곳 으로 쌓인다.
  • 힙(Heap) 은 동적으로 위로 올라가며 메모리를 잡아먹고
  • 스택(Stack) 은 아래로 내려가며 메모리를 잡아먹는다.
• 메모리 공간을 효율적으로 쓰기 위해