[C언어] 기초 자료구조 - 스택(Stack)

c언어

---

1. 스택(Stack)이란?

• 스택은 후입선출(LIFO, Last In First Out) 방식으로 동작하는 자료구조입니다.
• 특징
  1. 데이터가 맨 위(top)에서만 삽입(push)되고 삭제(pop)됨.
  2. 제한된 접근 방식으로 특정 위치의 데이터를 바로 접근할 수 없음.
• 활용 사례
  1. 함수 호출(재귀 호출 관리)
  2. 괄호 짝 검사
  3. 되돌리기(Undo) 기능
• 동작 원리
  1. Push: 데이터를 스택의 맨 위에 추가.
  2. Pop: 데이터를 스택의 맨 위에서 제거.
  3. Peek(Top): 스택의 맨 위 요소를 반환하지만 제거하지 않음.
  4. IsEmpty: 스택이 비어 있는지 확인.

---

2. 배열 기반 스택 구현

스택을 배열로 구현 시 고정된 크기의 정적 스택을 만들 수 있음.

#include <stdio.h>
#define MAX 5 // 스택의 최대 크기

int stack[MAX];
int top = -1; // 스택의 맨 위를 가리키는 변수

// Push 함수
void push(int data) {
    if (top == MAX - 1) {
        printf("스택 오버플로우! 더 이상 삽입할 수 없습니다.\n");
        return;
    }
    stack[++top] = data;
}

// Pop 함수
int pop() {
    if (top == -1) {
        printf("스택 언더플로우! 스택이 비어 있습니다.\n");
        return -1;
    }
    return stack[top--];
}

// Peek 함수
int peek() {
    if (top == -1) {
        printf("스택이 비어 있습니다.\n");
        return -1;
    }
    return stack[top];
}

// IsEmpty 함수
int isEmpty() {
    return top == -1;
}

int main() {
    push(10);
    push(20);
    push(30);
    printf("Top 요소: %d\n", peek()); // 30
    printf("Pop: %d\n", pop());       // 30
    printf("Pop: %d\n", pop());       // 20
    printf("스택이 비어 있나요? %s\n", isEmpty() ? "예" : "아니오");
    return 0;
}

---

3. 연결 리스트를 이용한 스택 구현

유동적으로 크기를 늘릴 수 있는 연결 리스트 기반 스택

#include <stdio.h>
#include <stdlib.h>

// 노드 구조체 정의
typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *top = NULL;

// Push 함수
void push(int data) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = data;
    newNode->next = top;
    top = newNode;
}

// Pop 함수
int pop() {
    if (top == NULL) {
        printf("스택 언더플로우! 스택이 비어 있습니다.\n");
        return -1;
    }
    int data = top->data;
    Node *temp = top;
    top = top->next;
    free(temp);
    return data;
}

// Peek 함수
int peek() {
    if (top == NULL) {
        printf("스택이 비어 있습니다.\n");
        return -1;
    }
    return top->data;
}

// IsEmpty 함수
int isEmpty() {
    return top == NULL;
}

int main() {
    push(10);
    push(20);
    push(30);
    printf("Top 요소: %d\n", peek()); // 30
    printf("Pop: %d\n", pop());       // 30
    printf("Pop: %d\n", pop());       // 20
    printf("스택이 비어 있나요? %s\n", isEmpty() ? "예" : "아니오");
    return 0;
}

---

4. 스택 활용 예제

• 괄호 짝 검사

#include <stdio.h>
#include <string.h>
#define MAX 100

char stack[MAX];
int top = -1;

// Push 함수
void push(char c) {
    stack[++top] = c;
}

// Pop 함수
char pop() {
    return stack[top--];
}

// 괄호 검사 함수
int isBalanced(char *expr) {
    for (int i = 0; i < strlen(expr); i++) {
        char c = expr[i];
        if (c == '(' || c == '{' || c == '[') {
            push(c);
        } else if (c == ')' || c == '}' || c == ']') {
            if (top == -1) return 0; // 스택이 비어 있으면 불균형
            char topChar = pop();
            if ((c == ')' && topChar != '(') ||
                (c == '}' && topChar != '{') ||
                (c == ']' && topChar != '[')) {
                return 0;
            }
        }
    }
    return top == -1; // 스택이 비어 있으면 균형
}

int main() {
    char expr[] = "{[()]}";
    printf("괄호가 균형 잡혔나요? %s\n", isBalanced(expr) ? "예" : "아니오");
    return 0;
}

• 스택으로 수열 뒤집기

#include <stdio.h>
#define MAX 100

int stack[MAX];
int top = -1;

// Push 함수
void push(int data) {
    stack[++top] = data;
}

// Pop 함수
int pop() {
    return stack[top--];
}

int main() {
    int arr[] = {1, 2, 3, 4, 5};
    int n = 5;

    // 스택에 푸시
    for (int i = 0; i < n; i++) {
        push(arr[i]);
    }

    // 스택에서 팝하며 뒤집기
    printf("뒤집힌 수열: ");
    while (top != -1) {
        printf("%d ", pop());
    }
    return 0;
}

---

5. 스택의 한계와 주의점

• 배열 기반 스택
  • 크기가 고정되므로 메모리 낭비 또는 스택 오버플로우 발생 가능.
• 연결 리스트 기반 스택
  • 동적 메모리를 사용하므로 메모리 해제를 반드시 신경 써야함.
• 시간 복잡도
  • Push, Pop 연산은 O(1)로 매우 효율적.