MENU
  1. ホーム
  2. C 언어
  3. C언어에서 스택의 기본 개념과 구현 방법

C언어에서 스택의 기본 개념과 구현 방법

C 언어

스택은 데이터 구조의 기본 중 하나로, 데이터를 “후입선출(LIFO: Last In, First Out)” 방식으로 처리하는 특징이 있습니다. 이 자료구조는 컴퓨터 과학 전반에서 다양한 용도로 활용되며, 특히 함수 호출 스택, 문자열 뒤집기, 수식의 괄호 검사 등에서 그 중요성이 강조됩니다. 본 기사에서는 C언어를 사용하여 스택의 동작 원리와 구현 방법을 이해하고, 이를 실제 문제 해결에 어떻게 적용할 수 있는지 살펴봅니다.

목차

스택이란 무엇인가


스택(Stack)은 데이터 구조 중 하나로, “후입선출(LIFO: Last In, First Out)” 방식을 따릅니다. 이는 가장 마지막에 삽입된 데이터가 가장 먼저 제거된다는 것을 의미합니다.

스택의 주요 특징


스택은 다음과 같은 특징을 갖습니다:

  • 선형 구조: 데이터가 순차적으로 저장되고 처리됩니다.
  • 제한된 접근: 데이터 삽입과 삭제는 스택의 꼭대기(top)에서만 가능합니다.
  • 단순한 연산: 데이터 삽입은 푸시(push), 삭제는 팝(pop) 연산으로 처리됩니다.

스택의 개념적 이해


스택은 흔히 접시 더미에 비유됩니다. 접시는 위에서 추가되며, 맨 위의 접시부터 제거할 수 있습니다. 이와 마찬가지로, 스택에서도 가장 최근에 추가된 데이터부터 처리됩니다.

스택의 기본 개념은 간단하지만, 소프트웨어 개발에서 중요한 역할을 하며 다양한 응용 사례로 확장됩니다.

스택의 활용 사례

스택은 다양한 문제 해결과 시스템 동작에서 중요한 역할을 합니다. 아래는 스택이 주로 활용되는 대표적인 사례들입니다.

함수 호출 관리


프로그램이 실행 중 함수를 호출하면, 호출된 함수의 정보(매개변수, 반환 주소 등)는 스택에 저장됩니다. 함수 실행이 끝나면 스택에서 제거되며, 이전 상태로 복구됩니다. 이를 호출 스택(Call Stack) 이라고 합니다.

문자열 역순 처리


문자열을 뒤집는 작업은 스택의 후입선출(LIFO) 특성과 잘 맞습니다. 문자열의 각 문자를 스택에 삽입하고(pop) 다시 꺼내(push) 읽으면 역순으로 정렬됩니다.

괄호 유효성 검사


수식에서 괄호가 올바르게 열리고 닫혔는지 확인할 때 스택이 사용됩니다. 열리는 괄호는 스택에 삽입하고, 닫히는 괄호가 나오면 스택의 최상위 데이터를 비교하여 일치 여부를 확인합니다.

후위 표기법 계산


수식을 계산할 때 후위 표기법(Postfix Notation)은 스택을 활용해 연산의 우선순위를 간단히 처리합니다. 피연산자를 스택에 저장하고, 연산자가 나오면 스택에서 데이터를 꺼내 계산합니다.

재귀 알고리즘


재귀 알고리즘은 내부적으로 스택을 활용합니다. 각 재귀 호출은 스택에 기록되고, 재귀가 완료되면 기록된 데이터를 사용해 이전 상태로 돌아갑니다.

스택은 이러한 다양한 활용 사례를 통해 효율적이고 체계적인 데이터 처리가 가능하도록 지원합니다.

스택의 기본 연산

스택은 제한된 접근 방식을 가지며, 다음과 같은 주요 연산을 통해 데이터를 처리합니다.

푸시(Push)


푸시는 데이터를 스택의 꼭대기(top)에 추가하는 연산입니다. 푸시 연산이 수행되면 스택의 크기가 증가합니다.

  • 예시: 스택에 숫자 5를 추가하면, 5가 스택의 가장 위에 저장됩니다.

팝(Pop)


팝은 스택의 꼭대기에서 데이터를 제거하는 연산입니다. 제거된 데이터는 반환되며, 스택의 크기가 감소합니다.

  • 예시: 스택의 꼭대기에 있는 5를 팝하면 스택에서 5가 제거됩니다.

피크(Peek 또는 Top)


피크는 스택의 꼭대기에 있는 데이터를 확인하는 연산입니다. 이때 데이터는 제거되지 않습니다.

  • 예시: 스택의 꼭대기에 있는 5를 확인하지만 스택은 그대로 유지됩니다.

공백 검사(IsEmpty)


스택이 비어 있는지 확인하는 연산입니다. 스택이 비어 있으면 true, 그렇지 않으면 false를 반환합니다.

  • 예시: 비어 있는 스택에서 IsEmpty 연산을 수행하면 true를 반환합니다.

스택의 상태


스택은 배열이나 연결 리스트를 사용해 구현되며, 현재 스택의 크기와 최대 크기를 기준으로 상태를 확인할 수 있습니다.

  • 오버플로우(Overflow): 스택이 가득 차 더 이상 데이터를 추가할 수 없는 상태입니다.
  • 언더플로우(Underflow): 스택이 비어 있어 데이터를 제거할 수 없는 상태입니다.

이러한 기본 연산을 조합하면 스택을 효과적으로 사용할 수 있습니다. 이를 바탕으로 다양한 알고리즘과 문제 해결에 스택을 응용할 수 있습니다.

배열 기반 스택 구현

배열 기반 스택은 배열을 사용하여 데이터를 저장하고, 스택의 기본 연산(푸시, 팝, 피크 등)을 구현합니다. 다음은 배열 기반 스택을 C언어로 구현하는 방법입니다.

코드 구현

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

#define MAX_SIZE 100  // 스택의 최대 크기 정의

typedef struct {
    int data[MAX_SIZE];
    int top;  // 스택의 꼭대기를 가리키는 인덱스
} Stack;

// 스택 초기화
void initStack(Stack *stack) {
    stack->top = -1;
}

// 푸시 연산
void push(Stack *stack, int value) {
    if (stack->top == MAX_SIZE - 1) {
        printf("스택 오버플로우 발생!\n");
        return;
    }
    stack->data[++stack->top] = value;
}

// 팝 연산
int pop(Stack *stack) {
    if (stack->top == -1) {
        printf("스택 언더플로우 발생!\n");
        return -1;  // 오류 값 반환
    }
    return stack->data[stack->top--];
}

// 피크 연산
int peek(Stack *stack) {
    if (stack->top == -1) {
        printf("스택이 비어 있습니다!\n");
        return -1;  // 오류 값 반환
    }
    return stack->data[stack->top];
}

// 공백 검사
int isEmpty(Stack *stack) {
    return stack->top == -1;
}

int main() {
    Stack stack;
    initStack(&stack);

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("스택의 꼭대기 값: %d\n", peek(&stack));
    printf("스택에서 제거된 값: %d\n", pop(&stack));
    printf("스택이 비었는가? %s\n", isEmpty(&stack) ? "Yes" : "No");

    return 0;
}

코드 설명

  • 스택 초기화: initStack 함수는 스택의 꼭대기를 가리키는 top을 -1로 초기화합니다.
  • 푸시 연산: 새로운 데이터를 추가할 때 top을 증가시키고 해당 위치에 데이터를 저장합니다.
  • 팝 연산: top 위치의 데이터를 반환하고 top을 감소시킵니다.
  • 피크 연산: top 위치의 데이터를 확인하지만, 스택에서 제거하지 않습니다.
  • 오버플로우 및 언더플로우 처리: 스택의 크기 제한을 초과하거나 비어 있을 경우 적절한 메시지를 출력합니다.

장점과 단점

  • 장점: 구현이 간단하며, 메모리가 연속적으로 할당되므로 접근 속도가 빠릅니다.
  • 단점: 배열 크기가 고정되어 있어 크기를 동적으로 조정할 수 없습니다.

배열 기반 스택은 간단한 스택 연산을 구현하기에 적합하며, 메모리 제한이 명확한 환경에서 효율적으로 사용할 수 있습니다.

연결 리스트 기반 스택 구현

연결 리스트를 사용한 스택 구현은 배열 기반 스택의 고정 크기 한계를 극복할 수 있습니다. 연결 리스트는 노드 단위로 메모리를 동적으로 할당하며, 스택 연산을 효과적으로 수행할 수 있습니다.

코드 구현

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

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

// 스택의 꼭대기를 가리키는 포인터
typedef struct {
    Node *top;
} Stack;

// 스택 초기화
void initStack(Stack *stack) {
    stack->top = NULL;
}

// 푸시 연산
void push(Stack *stack, int value) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    if (newNode == NULL) {
        printf("메모리 할당 실패!\n");
        return;
    }
    newNode->data = value;
    newNode->next = stack->top;
    stack->top = newNode;
}

// 팝 연산
int pop(Stack *stack) {
    if (stack->top == NULL) {
        printf("스택 언더플로우 발생!\n");
        return -1;  // 오류 값 반환
    }
    Node *temp = stack->top;
    int poppedValue = temp->data;
    stack->top = stack->top->next;
    free(temp);
    return poppedValue;
}

// 피크 연산
int peek(Stack *stack) {
    if (stack->top == NULL) {
        printf("스택이 비어 있습니다!\n");
        return -1;  // 오류 값 반환
    }
    return stack->top->data;
}

// 공백 검사
int isEmpty(Stack *stack) {
    return stack->top == NULL;
}

// 메모리 해제
void freeStack(Stack *stack) {
    while (stack->top != NULL) {
        pop(stack);
    }
}

int main() {
    Stack stack;
    initStack(&stack);

    push(&stack, 10);
    push(&stack, 20);
    push(&stack, 30);

    printf("스택의 꼭대기 값: %d\n", peek(&stack));
    printf("스택에서 제거된 값: %d\n", pop(&stack));
    printf("스택이 비었는가? %s\n", isEmpty(&stack) ? "Yes" : "No");

    freeStack(&stack);
    return 0;
}

코드 설명

  • 스택 초기화: initStack 함수는 스택의 꼭대기를 가리키는 포인터 top을 NULL로 초기화합니다.
  • 푸시 연산: 새로운 노드를 생성하고, 그 노드를 스택의 꼭대기로 설정합니다.
  • 팝 연산: 꼭대기 노드를 제거하고, 메모리를 해제합니다.
  • 피크 연산: 스택의 꼭대기 데이터 값을 확인합니다.
  • 메모리 관리: 동적으로 할당된 메모리를 반드시 해제해야 메모리 누수를 방지할 수 있습니다.

장점과 단점

  • 장점: 크기가 동적으로 조정되므로 배열 기반 스택의 크기 제한을 극복할 수 있습니다.
  • 단점: 각 노드에 대해 추가 메모리(포인터)를 사용하므로 메모리 오버헤드가 발생할 수 있습니다.

연결 리스트 기반 스택은 메모리 사용이 유연하며, 크기 제한이 없는 스택이 필요한 상황에서 적합합니다.

스택 오버플로우와 언더플로우 처리

스택은 제한된 크기의 데이터 구조이므로, 데이터를 삽입하거나 제거할 때 조건을 충족하지 못하면 오류 상황이 발생할 수 있습니다. 이를 스택 오버플로우와 스택 언더플로우라고 합니다.

스택 오버플로우(Stack Overflow)


스택 오버플로우는 스택이 가득 찬 상태에서 추가 데이터를 삽입하려고 할 때 발생합니다.

  • 배열 기반 스택에서의 원인: 스택 크기(MAX_SIZE)를 초과하여 데이터를 삽입하려고 하면 발생합니다.
  • 연결 리스트 기반 스택에서의 원인: 메모리 부족으로 더 이상 노드를 할당할 수 없는 경우 발생합니다.

해결 방법:

  1. 배열 기반 스택: 삽입 전 스택의 현재 크기와 최대 크기를 확인하여 오버플로우를 방지합니다.
   if (stack->top == MAX_SIZE - 1) {
       printf("스택 오버플로우 발생!\n");
   }
  1. 연결 리스트 기반 스택: malloc 함수의 반환값을 확인하여 메모리 할당 실패 시 처리합니다.
   if (newNode == NULL) {
       printf("메모리 할당 실패!\n");
   }

스택 언더플로우(Stack Underflow)


스택 언더플로우는 스택이 비어 있는 상태에서 데이터를 제거하려고 할 때 발생합니다.

  • 배열 기반 스택에서의 원인: 스택이 비어 있어(top == -1) 팝 연산을 수행할 데이터가 없을 때 발생합니다.
  • 연결 리스트 기반 스택에서의 원인: 스택의 꼭대기 노드가 NULL인 상태에서 데이터를 제거하려고 하면 발생합니다.

해결 방법:

  1. 배열 기반 스택: 제거 전 스택이 비어 있는지 확인합니다.
   if (stack->top == -1) {
       printf("스택 언더플로우 발생!\n");
   }
  1. 연결 리스트 기반 스택: top 포인터가 NULL인지 확인하여 언더플로우를 방지합니다.
   if (stack->top == NULL) {
       printf("스택 언더플로우 발생!\n");
   }

오류 예방 전략

  1. 사전 조건 확인: 연산 수행 전에 스택의 상태(크기, 꼭대기 인덱스)를 확인합니다.
  2. 오류 메시지 출력: 오류 발생 시 적절한 메시지를 출력하여 사용자에게 알립니다.
  3. 유효성 검사 함수 활용: isFull 또는 isEmpty와 같은 유효성 검사 함수를 사용하여 오류를 예방합니다.

예시: 공백 검사와 크기 확인

if (isEmpty(stack)) {
    printf("스택이 비어 있어 팝 연산을 수행할 수 없습니다.\n");
}
if (stack->top >= MAX_SIZE - 1) {
    printf("스택이 가득 차 있어 푸시 연산을 수행할 수 없습니다.\n");
}

스택 오버플로우와 언더플로우를 적절히 처리하면 스택을 보다 안정적으로 사용할 수 있으며, 오류로 인한 프로그램 중단을 방지할 수 있습니다.

스택 구현 심화 예제

스택의 기본 개념과 구현을 바탕으로, 이를 활용한 실질적인 문제 해결 사례를 살펴보겠습니다. 이번 예제에서는 후위 표기법 계산기를 구현합니다. 후위 표기법(Postfix Notation)은 스택의 특성을 활용하여 연산 우선순위를 단순화할 수 있는 수식 표현 방식입니다.

후위 표기법 계산기 구현

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

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

// 스택 초기화
void initStack(Stack *stack) {
    stack->top = -1;
}

// 푸시 연산
void push(Stack *stack, int value) {
    if (stack->top == MAX_SIZE - 1) {
        printf("스택 오버플로우 발생!\n");
        return;
    }
    stack->data[++stack->top] = value;
}

// 팝 연산
int pop(Stack *stack) {
    if (stack->top == -1) {
        printf("스택 언더플로우 발생!\n");
        exit(EXIT_FAILURE);
    }
    return stack->data[stack->top--];
}

// 후위 표기법 계산 함수
int evaluatePostfix(const char *expression) {
    Stack stack;
    initStack(&stack);

    for (int i = 0; expression[i] != '\0'; i++) {
        char ch = expression[i];

        // 숫자인 경우 스택에 푸시
        if (isdigit(ch)) {
            push(&stack, ch - '0');  // 문자 숫자를 정수로 변환
        } 
        // 연산자인 경우
        else {
            int operand2 = pop(&stack);
            int operand1 = pop(&stack);

            switch (ch) {
                case '+':
                    push(&stack, operand1 + operand2);
                    break;
                case '-':
                    push(&stack, operand1 - operand2);
                    break;
                case '*':
                    push(&stack, operand1 * operand2);
                    break;
                case '/':
                    push(&stack, operand1 / operand2);
                    break;
                default:
                    printf("잘못된 연산자: %c\n", ch);
                    exit(EXIT_FAILURE);
            }
        }
    }

    return pop(&stack);
}

int main() {
    const char *expression = "52+83-*";  // 예제: (5 + 2) * (8 - 3)
    printf("후위 표기법 수식: %s\n", expression);
    printf("계산 결과: %d\n", evaluatePostfix(expression));
    return 0;
}

코드 설명

  • 숫자 처리: 문자열로 주어진 후위 표기법 수식을 순회하며, 숫자는 스택에 푸시합니다.
  • 연산자 처리: 연산자가 나오면 스택에서 두 개의 피연산자를 팝하고, 연산을 수행한 결과를 다시 스택에 푸시합니다.
  • 결과 반환: 수식이 끝나면 스택의 마지막 값이 결과가 됩니다.

예제 실행

  • 입력 수식: "52+83-*"
  • (5 + 2) * (8 - 3)로 해석됩니다.
  • 계산 과정:
  1. 5와 2를 스택에 푸시
  2. + 연산자를 만나 5 + 2 = 7을 스택에 푸시
  3. 8과 3을 스택에 푸시
  4. - 연산자를 만나 8 - 3 = 5를 스택에 푸시
  5. * 연산자를 만나 7 * 5 = 35를 계산
  6. 결과: 35

스택 활용의 장점

  • 연산 우선순위 관리: 괄호 없이도 연산 순서를 명확히 유지할 수 있습니다.
  • 효율성: 후위 표기법은 스택을 사용하여 수식의 계산을 효율적으로 처리합니다.

응용


이 방법은 후위 표기법 계산뿐만 아니라, 중위 표기법을 후위 표기법으로 변환하거나, 스택을 활용한 다양한 수식 계산에도 확장하여 사용할 수 있습니다.

요약

본 기사에서는 스택의 기본 개념과 C언어를 활용한 구현 방법, 그리고 다양한 활용 사례를 다루었습니다. 스택은 배열 기반과 연결 리스트 기반으로 구현할 수 있으며, 각 방식의 장단점을 비교하여 상황에 맞는 선택이 중요합니다. 또한, 후위 표기법 계산기와 같은 응용 예제를 통해 스택의 실질적인 활용 가능성을 확인했습니다. 스택의 구조와 동작을 깊이 이해하고, 이를 실제 문제 해결에 적용하여 더욱 효율적인 코드를 작성할 수 있을 것입니다.

C 언어
C언어 데이터구조 스택 알고리즘
목차