[자료구조] 스택을 알아보자

스택(Stack)은 컴퓨터 과학에서 중요한 자료구조 중 하나로, 후입선출(Last In, First Out, 줄여서 LIFO) 구조를 가지고 있다. 이는 가장 최근에 추가된 요소가 가장 먼저 제거되는 구조를 의미한다. 이러한 특징으로 인해 스택은 다양한 프로그래밍 문제와 애플리케이션에서 유용하게 사용된다.

모르면 때려 치우자.

아래는 스택의 데이터 흐름을 이미지로 표현한 것이다.

이미지 출처 : https://www.programiz.com/dsa/stack

스택은 다음과 같은 주요 연산들을 포함하는 추상 데이터 타입이다.

ADT

1. push: 스택의 맨 위에 새로운 요소를 추가한다.
2. pop: 스택의 맨 위에서 요소를 제거하고 반환한다. 이 때, 스택이 비어있는 경우에는 에러를 반환한다.
3. peek 또는 top: 스택의 맨 위에 있는 요소를 반환하지만, 제거하지는 않는다. 스택이 비어있는 경우에는 에러를 반환한다.
4. is_empty: 스택이 비어 있는지 여부를 확인한다.

이제 스택을 구현해보자. Single Linked List 기반으로 구현한 C 코드이다.

구현

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

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

typedef struct Stack {
    Node* top;
} Stack;

Stack* create_stack() {
    Stack* stack = (Stack*) malloc(sizeof(Stack));
    stack->top = NULL;
    return stack;
}

int is_empty(Stack* stack) {
    return stack->top == NULL;
}

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

int pop(Stack* stack) {
    if (is_empty(stack)) {
        printf("Stack is empty. Cannot pop.\n");
        return -1;
    }

    Node* temp = stack->top;
    int popped_data = temp->data;
    stack->top = temp->next;
    free(temp);
    return popped_data;
}

int peek(Stack* stack) {
    if (is_empty(stack)) {
        printf("Stack is empty. Cannot peek.\n");
        return -1;
    }

    return stack->top->data;
}

그럼 스택은 실제 어떤 프로그램에서 사용되고 있을지 알아보자.

스택의 실무 사용 예시

1. 함수 호출과 실행 컨텍스트: 프로그래밍 언어에서 함수 호출을 관리할 때 스택을 사용한다. 함수가 호출되면 호출된 함수의 실행 컨텍스트가 스택에 쌓이고, 함수가 종료되면 스택에서 제거된다. 이를 통해 함수의 실행 순서와 지역 변수 저장 등을 관리한다.
2. 문자열 역순 출력: 스택을 사용하여 문자열을 역순으로 출력할 수 있다. 문자열의 각 문자를 스택에 푸시한 다음, 스택에서 문자를 하나씩 팝하여 출력하면 역순으로 출력된 문자열을 얻을 수 있다.
3. 괄호 검사: 스택은 괄호의 짝이 맞는지 검사하는데 사용할 수 있다. 여는 괄호를 만날 때마다 스택에 푸시하고, 닫는 괄호를 만날 때마다 스택에서 팝하여 짝이 맞는지 확인한다. 스택이 비어 있지 않으면 괄호가 올바르게 짝지어지지 않은 것이다.
4. 역폴란드 표기법 계산: 스택은 후위 표기법(역폴란드 표기법)으로 표현된 수식을 계산하는 데 사용된다. 피연산자를 만날 때마다 스택에 푸시하고, 연산자를 만날 때마다 스택에서 피연산자를 팝하여 계산한 후 결과를 다시 스택에 푸시한다.
5. 웹 브라우저 방문 기록: 웹 브라우저의 뒤로 가기 기능은 스택을 사용하여 구현된다. 사용자가 웹페이지를 방문할 때마다 해당 페이지의 URL이 스택에 쌓이고, 사용자가 뒤로 가기 버튼을 클릭하면 스택에서 URL을 팝하여 이전 페이지로 돌아간다. 이렇게 스택을 활용하면 웹 브라우저의 방문 기록을 쉽게 관리할 수 있다.
6. 실행 취소(Undo) 기능: 많은 응용 프로그램에서 실행 취소 기능을 구현할 때 스택을 사용한다. 사용자가 수행한 작업을 스택에 저장하고, 실행 취소를 원할 때 스택에서 작업을 팝하여 이전 상태로 되돌린다. 이렇게 스택을 활용하면 사용자의 작업 이력을 효과적으로 관리할 수 있다.
7. 깊이 우선 탐색(DFS): 그래프와 트리에서 깊이 우선 탐색(DFS) 알고리즘을 구현할 때 스택을 사용한다. 방문한 노드를 스택에 저장하고, 스택이 비어있지 않은 동안 다음 노드로 이동하며 탐색을 수행한다. 스택을 사용하면 깊이 우선 탐색 과정에서 방문 순서를 효율적으로 관리할 수 있다.
8. 메모리 관리: 운영 체제에서 메모리를 관리하는 데 스택이 사용된다. 각 프로세스는 자신의 스택 공간을 가지며, 변수와 함수 호출에 필요한 메모리를 할당한다. 이를 통해 메모리를 효율적으로 관리하고, 각 프로세스가 독립적으로 실행될 수 있도록 지원한다.
9. 백트래킹 알고리즘: 스택은 백트래킹 알고리즘에서 솔루션을 구성하는 데 사용된다. 알고리즘이 진행되면서 해결책을 찾기 위해 스택에 요소를 추가하고, 해결책이 발견되지 않으면 스택에서 요소를 제거하여 이전 상태로 돌아간다. 이를 통해 탐색 공간을 효율적으로 관리하고, 문제 해결에 도움을 준다.
10. 컴파일러 및 어셈블러: 컴파일러와 어셈블러는 스택을 사용하여 심볼 테이블, 타입 체크, 코드 생성 등의 작업을 수행한다. 스택을 사용하면 이러한 작업들을 효율적으로 수행할 수 있으며, 프로그램의 구조를 올바르게 이해하고 처리할 수 있다.

이러한 예시들은 스택이 프로그래밍 및 컴퓨터 과학에서 얼마나 다양한 분야에서 활용되는지를 보여준다. 스택은 간단한 자료구조임에도 불구하고, 그 특성 때문에 다양한 문제 해결과 실무 애플리케이션 개발에 큰 도움을 준다. 스택의 개념을 이해하고 적절한 상황에서 활용하면, 프로그램의 성능과 효율성을 크게 향상시킬 수 있다.