스택은 컴퓨터 과학과 프로그래밍에서 많이 사용되는 자료구조입니다. 여기서는 C언어를 이용해 스택의 개념과 구현 방법을 살펴보겠습니다. 또한, 스택의 메모리 레이아웃을 그림으로 표현해 이해를 돕겠습니다.

스택의 기본 개념

스택의 정의

  스택은 데이터가 LIFO 구조로 저장되는 컬렉션입니다. 즉, 마지막에 삽입된 데이터가 가장 먼저 제거됩니다. 스택은 push와 pop이라는 두 가지 기본 연산을 제공합니다.

스택의 활용 예

  스택은 함수 호출 관리, 문자열 역순 처리, 브라우저 히스토리 등 다양한 곳에서 활용됩니다. 이를 통해 스택의 유용성을 이해할 수 있습니다.

C언어로 스택 구현하기

구조체 이용한 스택 정의

  스택을 C언어로 구현하기 위해 구조체와 배열을 사용할 수 있습니다. 아래는 스택을 정의하는 코드입니다:

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

typedef struct Stack {
    int items[MAX];
    int top;
} Stack;

void initialize(Stack *s) {
    s->top = -1;
}

int isEmpty(Stack *s) {
    return s->top == -1;
}

int isFull(Stack *s) {
    return s->top == (MAX - 1);
}

void push(Stack *s, int item) {
    if (isFull(s)) {
        printf("Stack is full\n");
    } else {
        s->items[++(s->top)] = item;
    }
}

int pop(Stack *s) {
    if (isEmpty(s)) {
        printf("Stack is empty\n");
        return -1;
    } else {
        return s->items[(s->top)--];
    }
}

스택 연산 예제 코드

  다음은 스택에 데이터를 push하고 pop하는 예제입니다:

int main() {
    Stack s;
    initialize(&s);

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

    printf("Popped item: %d\n", pop(&s));
    printf("Popped item: %d\n", pop(&s));

    return 0;
}

스택의 메모리 레이아웃

메모리 상태 시각화

  스택의 메모리 상태를 쉽게 이해하기 위해 그림을 사용합니다. push 연산과 pop 연산 후의 메모리 상태는 다음과 같습니다:

초기 상태

[ ][ ][ ][ ][ ]
top = -1

push(10)

[10][ ][ ][ ][ ]
top = 0

push(20)

[10][20][ ][ ][ ]
top = 1

pop()

[10][ ][ ][ ][ ]
top = 0

메모리 레이아웃 코드 분석

  위 그림들은 push와 pop 연산 후 스택의 메모리 상태를 시각적으로 설명합니다. 이 과정을 코드와 함께 살펴보면 스택의 동작 원리를 쉽게 이해할 수 있습니다.

스택의 장단점

장점

  스택은 한쪽 끝에서만 데이터를 추가하고 제거하기 때문에 구현이 단순합니다. 또한, 데이터의 순서를 기억하고 역순으로 데이터를 처리할 때 유용합니다.

단점

  스택의 크기를 미리 지정해야 하기 때문에 메모리 낭비가 발생할 수 있습니다. 또한, 크기를 초과하는 데이터를 추가할 수 없습니다.

스택 활용 사례

재귀 호출 관리

  스택은 함수의 재귀 호출을 관리하는 데 유용합니다. 각 함수 호출 시 스택에 정보가 저장되고, 함수가 반환될 때 스택에서 제거됩니다.

수식 계산

  스택은 후위 표기법(Reverse Polish Notation) 계산기에서 사용됩니다. 연산자가 나올 때마다 스택에서 피연산자를 꺼내 계산합니다.

  스택은 또한 유효한 괄호 검사, 웹 브라우저의 뒤로 가기 기능 등에서도 중요한 역할을 합니다.

내부 링크

• C언어 조건문 정리