[자료구조] 스택(stack) / 백준 10828 (C)

스택이란?

삽입과 제거가 한쪽 끝에서만 이루어지는 특수한 선형 리스트.

후입 선출(Last-In-First-Out) 구조이다. 즉, 가장 마지막에(최신에) 들어온 데이터가 가장 먼저 나간다.

 

stack

 

스택의 주요 연산

- push(): 스택에 원소 삽입
- pop(): 스택에서 원소 제거 (후 그 값을 반환)
- top()/peek(): 가장 위에 있는 원소 반환
- isEmpty(): 스택이 비었는지 확인
- isFull(): 스택이 가득 찼는지 확인

아래는 C언어로 스택의 주요 연산을 구현한 것이다. 백준 10828문제의 소스코드이다.

(문제링크: www.acmicpc.net/problem/10828)

#include <stdio.h>
#include <string.h>
#define MAX_STACK_SIZE 10000

int stack[MAX_STACK_SIZE]; // 스택 배열
int topIndex = -1; // 스택의 top의 인덱스

// push X: 정수 X를 스택에 넣는 연산이다.
void push(int x) {
    stack[++topIndex] = x;
}

// pop: 스택에서 가장 위에 있는 정수를 빼고, 그 수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
int pop() {
    if (empty()) {
        return -1; // 스택이 비었을 경우 -1 출력
    }
    return stack[topIndex--];
}

// size: 스택에 들어있는 정수의 개수를 출력한다.
int size() {
    return topIndex + 1; // 1 더해주는 이유? 배열 인덱스가 0부터 시작하므로. top이 2면 0, 1, 2에 값 있는 것.
}

// empty: 스택이 비어있으면 1, 아니면 0을 출력한다.
int empty() {
    if (topIndex == -1) {
        return 1;
    }
    else return 0;
}

// top: 스택의 가장 위에 있는 정수를 출력한다. 만약 스택에 들어있는 정수가 없는 경우에는 -1을 출력한다.
int top() {
    if (topIndex == -1) {
        return -1;
    }
    return stack[topIndex];
}

int main() {
    int N;
    scanf("%d", &N);

    for (int i = 0; i < N; i++) {
        char command[6];
        scanf("%s", command);

        if (!strcmp(command, "push")) {
            int x;
            scanf("%d\n", &x);
            push(x);
        }
        else if (!strcmp(command, "pop")) {
            printf("%d\n", pop());
        }
        else if (!strcmp(command, "size")) {
            printf("%d\n", size());
        }
        else if (!strcmp(command, "empty")) {
            printf("%d\n", empty());
        }
        else if (!strcmp(command, "top")) {
            printf("%d\n", top());
        }
    }

    return 0;
}

스택의 응용

• 괄호 검사 알고리즘
• 함수 호출시 활성 레코드 저장(시스템소프트웨어, 컴퓨터구조, 운영체제 등 시간에 배움)
• 수식의 계산

다음 시간에는 C++에서 스택 헤더를 사용해서 스택 자료구조를 사용하는 법에 대해 정리해보겠다.