스택(Stack) 자료구조 완전 이해 — 백준 28278번 스택 2로 배우는 구현

📘 1️⃣ 스택이란?

Stack(스택) 은 LIFO (Last In, First Out) 구조를 가지는 자료구조입니다.
즉, 마지막에 들어온 데이터가 가장 먼저 나가는 구조죠.

🧩 예시로 생각해보면:

접시를 한 장씩 쌓아올릴 때,
맨 위의 접시(마지막으로 쌓은 것)부터 꺼내야 합니다.
이것이 바로 스택의 작동 원리입니다.

---

🧮 기본 연산

연산설명

push(X)	데이터를 스택에 삽입
pop()	스택의 맨 위 데이터를 제거하고 반환
top()	스택의 맨 위 데이터를 단순히 확인
size()	스택에 쌓인 데이터 개수 확인
empty()	스택이 비어있는지 확인 (1: 비었음, 0: 안 비었음)

---

⚙️ 2️⃣ 백준 28278번 문제 개요

문제 이름: 스택 2
문제 링크: https://www.acmicpc.net/problem/28278
알고리즘 분류: 자료구조 / 스택

---

📖 문제 설명

정수를 저장하는 스택을 구현하고, 다음 다섯 가지 명령을 처리하는 프로그램을 작성하시오.

명령설명

1 X	정수 X를 스택에 넣는다. (1 ≤ X ≤ 100,000)
2	스택이 비어 있지 않으면 맨 위의 정수를 빼고 출력, 비었으면 -1
3	스택에 들어 있는 정수의 개수를 출력
4	스택이 비어 있으면 1, 아니면 0 출력
5	스택이 비어 있지 않으면 맨 위의 정수를 출력, 비었으면 -1

---

📥 입력

• 첫째 줄에 명령의 수 N (1 ≤ N ≤ 1,000,000)
• 다음 줄부터 N개의 명령이 한 줄씩 주어짐

📤 출력

• 출력이 필요한 명령이 있을 때마다 결과를 한 줄씩 출력

 

---

💡 예제

입력

 

9

4

1 3

1 5

3

2

5

2

2

5

출력

 

1

2

5

3

3

-1

-1

---

🧠 3️⃣ 문제 접근 방식

이 문제는 스택 기본 구현 문제지만,
입력의 크기가 최대 100만 줄까지 들어오기 때문에
입출력 속도를 반드시 최적화해야 합니다.

 

동적 메모리 할당보다 배열 기반 스택이 훨씬 효율적 입니다.

---

💻 4️⃣ C언어 코드 구현

#include <stdio.h>

#define STACK_MAX 1000000

void push_stack(int* stack, int* top_idx, int x);
void pop_stack(int* stack, int* top_idx);
void top_stack(int* stack, int top_idx);

int stack[STACK_MAX];

int main () {
    int N;
    int i;
    int top_idx = -1;

    scanf("%d", &N);

    for (i = 0; i < N; i++) {
        int cmd;
        scanf("%d", &cmd);

        switch (cmd) {
        case 1:
            // push
            int x;
            scanf("%d", &x);
            push_stack(stack, &top_idx, x);
            break;
        case 2:
            // pop
            pop_stack(stack, &top_idx);
            break;
        case 3:
            // size
            printf("%d\n", top_idx + 1);
            break;
        case 4:
            // empty
            if (top_idx == -1)
                printf("1\n");
            else
                printf("0\n");
            break;
        case 5:
            // top
            top_stack(stack, top_idx);
            break;
        }
    }
}

// push 함수: 스택에 값 삽입
void push_stack(int* stack, int* top_idx, int x) {
    stack[*top_idx + 1] = x;
    (*top_idx)++;
}

// pop 함수: 스택에서 값 제거 후 출력
void pop_stack(int* stack, int* top_idx) {
    if (*top_idx > -1) {
        printf("%d\n", stack[*top_idx]);
        (*top_idx)--;
    } else {
        printf("-1\n");
    }
}

// top 함수: 스택의 맨 위 값 출력
void top_stack(int* stack, int top_idx) {
    if (top_idx > -1)
        printf("%d\n", stack[top_idx]);
    else
        printf("-1\n");
}