[C] 스택 알고리즘 Stack Algorithm

#1. 스택 이란?

스택은 요소에 액세스하는 후입선출(LIFO) 순서가 있는 요소 모음을 나타내는 추상 데이터 유형이에요. 가장 최근에 추가된 요소가 가장 먼저 제거된다는 의미인 "후입선출(last in, first out)" 원칙에 따라 작동해요.

맨 위에 있는 책에만 액세스할 수 있는 책 더미를 상상해 보세요. 책 더미에 새 책을 추가하려면 책을 맨 위에 놓고 책을 제거하려면 맨 위에 있는 책을 책 더미에서 꺼내요. 이는 스택 데이터 구조가 작동하는 방식과 유사해요.

스택에는 두 가지 주요 작업이 있어요.

1. Push: 이 작업은 스택의 맨 위에 요소를 추가합니다. 새 요소가 맨 위 요소가 되고 기존 요소는 한 위치 아래로 푸시되어요.
2. Pop: 이 작업은 스택에서 맨 위 요소를 제거합니다. 맨 위 요소 아래의 요소가 새 맨 위 요소가 되어요.

이러한 기본 작업 외에도 스택에는 맨 위 요소를 제거하지 않고 볼 수 있는 peek 또는 top, 스택이 비어 있는지 확인하는 isEmpty와 같은 다른 유용한 작업이 있을 수 있어요.

스택은 일반적으로 컴퓨터 과학 및 프로그래밍에서 사용됩니다. 함수 호출을 관리하고, 프로그램 실행을 추적하고, 재귀를 처리하고, 식을 구문 분석하는 등의 방법을 제공해요. 또한 메모리 관리 및 데이터 구조 구현에도 사용됩니다.

#2. 예제 코드

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

#define MAX_SIZE 10

// 스택을 나타내는 구조체
struct Stack 
{
    int data[MAX_SIZE]; // 스택의 요소를 저장하는 배열
    int top; // 스택의 맨 위 요소의 인덱스
};

// 스택을 초기화하는 함수
void initStack(struct Stack* s) 
{
    s -> top = -1; // 스택의 맨 위 요소를 -1로 설정하여 스택이 비어있음을 나타냄
}

// 스택이 비어있는지 확인하는 함수
int isEmpty(struct Stack* s) 
{
    return s -> top == -1; // 스택의 맨 위 요소가 -1이면 스택이 비어있음을 나타냄
}

// 스택이 가득 찼는지 확인하는 함수
int isFull(struct Stack* s) 
{
    return s -> top == MAX_SIZE - 1; // 스택의 맨 위 요소의 인덱스가 MAX_SIZE - 1이면 스택이 가득 찼음을 나타냄
}

// 스택에 요소를 추가하는 함수
void push(struct Stack* s, int value) 
{
    if (isFull(s)) // 스택이 가득 찼을 때
    { 
        printf("Stack overflow!\n"); // 에러 메시지 출력
        exit(1); // 프로그램 종료
    }
    s -> top++; // 스택의 맨 위 요소의 인덱스 증가
    s -> data[s -> top] = value; // 스택의 맨 위에 value를 추가
}

// 스택에서 요소를 제거하는 함수
int pop(struct Stack* s) 
{
    if (isEmpty(s)) // 스택이 비어있을 때
    { 
        printf("Stack underflow!\n"); // 에러 메시지 출력
        exit(1); // 프로그램 종료
    }
    int value = s -> data[s -> top]; // 스택의 맨 위 요소를 저장
    s -> top--; // 스택의 맨 위 요소의 인덱스 감소
    return value; // 저장된 요소 반환
}

int main() 
{
    struct Stack s;
    initStack(&s); // 스택 초기화
    
    push(&s, 1);
    push(&s, 2);
    push(&s, 3);
    
    printf("Popped: %d\n", pop(&s));
    printf("Popped: %d\n", pop(&s));
    printf("Popped: %d\n", pop(&s));
    
    return 0;
}