스택(프로그래밍)

개요

스택(Stack)은 컴퓨터 과학에서 널리 사용되는 추상 자료형으로, 데이터를 저장하고 관리하는 자료 구조이다. 스택의 가장 큰 특징은 '후입선출'(LIFO: Last In First Out) 원칙을 따른다는 점이다. 이는 나중에 들어온 데이터가 가장 먼저 나가는 구조를 의미한다.

LIFO vs FIFO

데이터 구조를 이해하는 데 있어 LIFO와 FIFO의 개념은 매우 중요합니다.

LIFO (Last In First Out)

• LIFO는 "나중에 들어온 것이 먼저 나간다"는 원칙이다.
• 스택(Stack)이 대표적인 LIFO 구조다.
• 실생활의 예: 접시 쌓기, 웹 브라우저의 뒤로 가기 버튼

FIFO (First In First Out)

자세한 내용은 큐(프로그래밍) 문서를 참고하세요!

• FIFO는 "먼저 들어온 것이 먼저 나간다"는 원칙이다.
• 큐(Queue)가 대표적인 FIFO 구조다.
• 실생활의 예: 계산대에 줄 서 있는 사람들, 프린터의 인쇄 대기열

스택(Stack)의 특징

1. LIFO 원칙: 나중에 들어온 데이터가 가장 먼저 나간다.
2. 주요 작업:
   1. Push: 스택의 위쪽(top)에 새로운 요소를 추가한다.
   2. Pop: 스택의 위쪽(top)에서 요소를 제거한다.
3. 주요 위치:
   1. Top: 스택의 가장 위에 있는 요소의 위치

스택의 기본 연산

1. push(item): 스택의 위쪽(top)에 새로운 요소를 추가한다.
2. pop(): 스택의 위쪽(top)에서 요소를 제거하고 반환한다.
3. peek(): 스택의 가장 위에 있는 요소를 반환하지만 제거하지는 않는다.
4. isEmpty(): 스택이 비어있는지 확인한다.
5. isFull(): 스택이 가득 찼는지 확인한다. (배열로 구현된 경우)

스택의 구현 방식

스택은 주로 두 가지 방식으로 구현된다:

1. 배열 기반 구현

배열을 사용하여 스택을 구현하는 방식이다.

장점

• 구현이 간단하다.
• 랜덤 접근이 가능하다.

단점

• 크기가 고정되어 있어 스택이 가득 찼을 때 새로운 요소를 추가할 수 없다.

C언어 예제

#include <stdio.h>
#define MAX_SIZE 100

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

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

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

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

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

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

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

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

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

    return 0;
}

2. 연결 리스트 기반 구현

연결 리스트를 사용하여 스택을 구현하는 방식이다.

장점

• 크기가 동적으로 조절된다.
• 요소의 추가와 제거가 효율적이다.

단점

• 추가적인 메모리가 필요하다. (포인터를 저장해야 하므로)
• 랜덤 접근이 불가능하다.

C언어 예제

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

typedef struct Node {
    int data;
    struct Node* next;
} Node;

typedef struct {
    Node* top;
} Stack;

void initializeStack(Stack* s) {
    s->top = NULL;
}

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

void push(Stack* s, int value) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    newNode->data = value;
    newNode->next = s->top;
    s->top = newNode;
}

int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1;
    }

    Node* temp = s->top;
    int item = temp->data;
    s->top = s->top->next;
    free(temp);

    return item;
}

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

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

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

    return 0;
}

스택의 응용 분야

스택은 다양한 분야에서 활용된다:

1. 함수 호출의 관리 (호출 스택)
2. 수식 계산 및 구문 분석
3. 웹 브라우저의 뒤로 가기 기능
4. 깊이 우선 탐색(DFS) 알고리즘
5. 역순 문자열 만들기
6. 운영 체제의 메모리 관리

스택의 변형

1. 동적 스택(Dynamic Stack): 연결 리스트를 이용해 크기가 동적으로 조절되는 스택.
2. 다중 스택(Multi Stack): 하나의 배열을 여러 개의 스택으로 나누어 사용하는 구조.
3. 우선순위 스택(Priority Stack): 각 요소에 우선순위가 부여된 스택. (스택보다는 우선순위 큐에 가까운 개념)

결론

스택은 LIFO 원칙을 따르는 간단하면서도 강력한 자료 구조이다. 이 구조는 많은 실제 상황을 모델링하는 데 이상적이며, 컴퓨터 과학의 여러 분야에서 중요한 역할을 한다. 스택의 개념을 이해하고 적절히 활용할 수 있다면, 다양한 프로그래밍 문제를 효과적으로 해결할 수 있을 것이다.