2. 스택 (Stack)

스택이란?

위키디피아의 스택 이미지

 후입선출(Last In First Out / LIFO) 특성을 가지는 선형 자료 구조이다. 구조가 간단하고 후입선출이라는 특성을 이용해 각종 알고리즘과 로직, 메모리에 사용된다. 예를 들어보자면, ctrl + z를 누르면 실행되는 '되돌리기'가 스택의 예이다. 가장 나중에 들어온 작업이 가장 먼저 나오는 방식이다.

 

스택의 연산

기능	명칭	시간복잡도
삽입	push	O(1)
삭제 및 반환	pop	O(1)
상단 값 조회	top	O(1)

 

 스택의 모든 연산은 상수시간의 시간복잡도를 가지고 있다. 하지만 이는 장단점을 가지기 마련이다.

 

스택의 장점

 1. 매우 간단하다. 배열과 더불어 간단한 구조, 배열보다 훨씬 간단한 연산과 규칙으로 구현과 사용이 매우 쉽다. 배열과 별도의 변수를 이용해 구현할 수 있고, 연결리스트로도 손쉽게 구현이 가능하다.

 

 2. 매우 빠르다. 삽입과 삭제가 모두 즉시 수행 가능하기 때문에, LIFO를 잘 이용한다면, 어느 자료 구조보다 빠르게 연산이 가능하다.

 

 3. 데이터의 무결성. 스택은 중간에 위치한 데이터를 함부로 삽입, 삭제가 불가능하므로, 데이터의 무결성과 순서를 보장한다. 그러므로 순서가 중요한 재귀함수 호출 구조, 괄호의 짝 맞추기 문제 등에 쓰인다.

 

스택의 단점

 1. 접근 제한. 앞서 말했 듯이 스택의 연산은 모두 가장 마지막에 삽입된 데이터를 기준으로 진행되기 때문에 그 이전에 나온 데이터들을 순서를 무시하고 접근할 수 없다. 그러므로 중간에 위치한 데이터들의 조회가 많은 경우, 검색을 해야하는 경우 비효율적일 수 있다.

 

 2. 오버플로우, 언더플로우 문제. 스택은 보통 제한된 크기를 가지는데, 이 같은 경우 크기를 초과할 수 있는 오버플로우와 빈 경우에도 삭제를 시행하는 언더플로우가 발생할 수 있다. 이에 대한 대비를 필수적으로 해야한다.

 

 3. 용도의 제한. 스택의 그 특성으로 인해 특정 알고리즘과 로직에 한해서 효율적이고, 검색과 중간 삽입 등의 연산지 끼어있는 경우 기하급수적으로 효율성이 낮아진다. 그렇기에 로직을 잘 분석하고 알맞게 스택을 사용하는 것이 중요하다.

 

스택의 예시

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

#define MAX 100  // 스택의 최대 크기

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

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

// 스택이 비어있는지 확인
int isEmpty(Stack* stack) {
    return stack->top == -1;
}

// 스택이 가득 찼는지 확인
int isFull(Stack* stack) {
    return stack->top == MAX - 1;
}

// 스택에 데이터 삽입 (push)
void push(Stack* stack, int value) {
    if (isFull(stack)) {
        printf("Stack Overflow\n");
        return;
    }
    stack->data[++stack->top] = value;
}

// 스택에서 데이터 제거 (pop)
int pop(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack Underflow\n");
        return -1;  // 에러 코드 반환
    }
    return stack->data[stack->top--];
}

// 스택의 최상위 데이터 확인 (top)
int top(Stack* stack) {
    if (isEmpty(stack)) {
        printf("Stack is empty\n");
        return -1;  // 에러 코드 반환
    }
    return stack->data[stack->top];
}

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

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

    printf("Top element is %d\n", top(&stack));

    printf("Popped element is %d\n", pop(&stack));
    printf("Top element is %d\n", top(&stack));

    return 0;
}

 

 C언어 배열과 top의 위치를 나타내는 변수로 구성된 구조체를 활용한 스택이다. 스택의 구조와 연산 방식을 직관적으로 볼 수 있다. 오버플로우와 언더플로우로 인한 프로그램 중단을 막기위해 예외처리도 포함하였다.