스택과 큐: 기본 개념과 구현

1. 스택의 기본 개념

스택(Stack)은 특별한 형태의 선형 자료구조로, 한쪽 끝에서만 데이터를 삽입하고 삭제할 수 있도록 제한되어 있습니다. 이러한 제한으로 인해 스택은 "후입선출"(LIFO, Last In First Out) 특성을 가지게 됩니다. 즉, 가장 마지막에 추가된 데이터가 가장 먼저 제거되는 구조입니다.

스택의 핵심 요소

  • 스택 최상단(Top): 데이터의 삽입과 삭제가 이루어지는 단말
  • 스택 최하단(Bottom): 스택 최상단의 반대편으로, 직접적인 연산이 불가능
  • 푸시(Push): 데이터를 스택 최상단에 추가하는 연산
  • 팝(Pop): 데이터를 스택 최상단에서 제거하는 연산
  • peek 연산: 스택 최상단의 데이터를 확인만 하고 제거하지 않는 연산

실생활에서의 스택 예시

우리 주변에는 스택의 원리를 활용한 사례가 많습니다. 쌓여 있는 접시들에서 가장 위에 있는 접시를 먼저 꺼내고, 총알magazine에서는 마지막에 넣은 총알이 먼저 발사됩니다. 엘리베이터에 마지막으로 탄 사람이最先退出电梯，还有函数调用에서도 가장 마지막에 호출된 함수가 가장 먼저 반환됩니다.

2. 스택의 저장 방식

스택은 두 가지 주요 방식으로 구현할 수 있습니다.

  • 순차 스택: 배열을 기반으로 구현, 연속적인 메모리 사용
  • 연결 스택: 연결 리스트를 기반으로 구현, 동적 메모리 할당

3. 스택의 구현

3.1 순차 스택 구현

순차 스택은 배열을 사용하여 스택을 구현하는 방식입니다. 다음은 순차 스택의 구조체 정의입니다.

typedef struct sequential_stack {
    element_type *element_array;  // 스택 데이터 저장을 위한 배열 포인터
    int stack_capacity;           // 스택의 최대 용량
    int stack_top_index;          // 현재 스택 최상단의 인덱스
} seq_stack, *seq_stack_ptr;

순차 스택의 주요 연산 구현은 다음과 같습니다.

// 스택 초기화 함수
seq_stack_ptr stack_initialize(int capacity_limit) {
    seq_stack_ptr stack_instance = (seq_stack_ptr)malloc(sizeof(seq_stack));
    if (stack_instance != NULL) {
        stack_instance->element_array = (element_type *)malloc(sizeof(element_type) * capacity_limit);
        stack_instance->stack_capacity = capacity_limit;
        stack_instance->stack_top_index = -1;  // 빈 스택을 나타내는 값
    }
    return stack_instance;
}

// 스택이 비어있는지 확인
boolean stack_is_empty(seq_stack_ptr stack_instance) {
    return (stack_instance->stack_top_index == -1);
}

// 스택이 가득 찼는지 확인
boolean stack_is_full(seq_stack_ptr stack_instance) {
    return (stack_instance->stack_top_index == stack_instance->stack_capacity - 1);
}

// 데이터 삽입 (푸시)
int stack_push(seq_stack_ptr stack_instance, element_type new_data) {
    if (stack_is_full(stack_instance)) {
        return -1;  // 스택이 가득 찼을 때
    }
    stack_instance->stack_top_index++;
    stack_instance->element_array[stack_instance->stack_top_index] = new_data;
    return 0;
}

// 데이터 제거 (팝)
int stack_pop(seq_stack_ptr stack_instance) {
    if (stack_is_empty(stack_instance)) {
        return -1;  // 스택이 비어있을 때
    }
    stack_instance->stack_top_index--;
    return 0;
}

3.2 연결 스택 구현

연결 스택은 연결 리스트를 활용하여 구현합니다. 각 노드가 다음 노드를 가리키는 구조로 되어 있습니다.

// 노드 구조체 정의
typedef struct stack_node {
    element_type node_data;
    struct stack_node *next_node_ptr;
} stack_node_t, *stack_node_ptr;

// 스택 관리 구조체
typedef struct linked_stack {
    stack_node_ptr top_node_ptr;  // 최상단 노드를 가리키는 포인터
    int element_count;            // 현재 저장된 요소 개수
} linked_stack, *linked_stack_ptr;
// 연결 스택 초기화
linked_stack_ptr linked_stack_init(void) {
    linked_stack_ptr stack_ptr = (linked_stack_ptr)malloc(sizeof(linked_stack));
    if (stack_ptr != NULL) {
        stack_ptr->top_node_ptr = (stack_node_ptr)malloc(sizeof(stack_node_t));
        stack_ptr->top_node_ptr->next_node_ptr = stack_ptr->top_node_ptr;  // 자기 참조
        stack_ptr->element_count = 0;
    }
    return stack_ptr;
}

// 연결 스택에 데이터 삽입 (헤드 삽입 방식)
void linked_stack_push(linked_stack_ptr stack_ptr, stack_node_ptr new_node) {
    stack_node_ptr header_node = stack_ptr->top_node_ptr;
    new_node->next_node_ptr = header_node->next_node_ptr;
    header_node->next_node_ptr = new_node;
    stack_ptr->element_count++;
}

4. 큐의 기본 개념

큐(Queue)는 또 다른 중요한 선형 자료구조입니다. 스택과 달리 큐는 두 개의 서로 다른 끝단에서 연산이 이루어집니다. 한쪽 끝에서는 삽입만, 다른 끝단에서는 삭제만 수행할 수 있습니다. 이러한 특성으로 인해 큐는 "선입선출"(FIFO, First In First Out) 원칙을 따르게 됩니다.

큐의 핵심 요소

  • 프론트(Front): 데이터가 삭제되는 앞쪽 끝단
  • 리어(Rear): 데이터가 삽입되는 뒤쪽 끝단
  • 인큐(EnQueue): 데이터를 큐의 뒤쪽에 추가하는 연산
  • 디큐(DeQueue): 큐의 앞쪽에서 데이터를 제거하는 연산
  • 프론트 peek: 큐의 앞쪽 데이터를 확인만 하는 연산

5. 큐의 저장 방식

큐도 스택과 마찬가지로 두 가지 방식으로 구현할 수 있습니다.

  • 순차 큐: 배열을 기반으로 구현
  • 연결 큐: 연결 리스트를 기반으로 구현

6. 큐의 구현

6.1 순차 큐 (순환 큐) 구현

순차 큐에서 중요한 문제는 "가짜 오버플로"입니다. 배열의 끝에 도달하면 다시 시작점으로 돌아갈 수 있도록 순환 형태로 구현합니다.

typedef struct sequential_queue {
    element_type *queue_array;    // 큐 데이터 저장을 위한 배열 포인터
    int queue_capacity;           // 큐의 용량
    int front_index;              // 프론트 포인터
    int rear_index;               // 리어 포인터
} seq_queue, *seq_queue_ptr;
// 순차 큐 초기화
seq_queue_ptr queue_initialize(int capacity_limit) {
    seq_queue_ptr queue_instance = (seq_queue_ptr)malloc(sizeof(seq_queue));
    if (queue_instance != NULL) {
        queue_instance->queue_array = (element_type *)malloc(sizeof(element_type) * capacity_limit);
        queue_instance->queue_capacity = capacity_limit;
        queue_instance->front_index = 0;
        queue_instance->rear_index = 0;
    }
    return queue_instance;
}

// 큐가 비어있는지 확인
boolean queue_is_empty(seq_queue_ptr queue_instance) {
    return (queue_instance->front_index == queue_instance->rear_index);
}

// 큐가 가득 찼는지 확인
boolean queue_is_full(seq_queue_ptr queue_instance) {
    return ((queue_instance->rear_index + 1) % queue_instance->queue_capacity == queue_instance->front_index);
}

// 데이터 삽입 (인큐)
int queue_enqueue(seq_queue_ptr queue_instance, element_type new_data) {
    if (queue_is_full(queue_instance)) {
        return -1;
    }
    queue_instance->queue_array[queue_instance->rear_index] = new_data;
    queue_instance->rear_index = (queue_instance->rear_index + 1) % queue_instance->queue_capacity;
    return 0;
}

6.2 연결 큐 구현

// 노드 구조체
typedef struct queue_node {
    element_type node_data;
    struct queue_node *next_node_ptr;
} queue_node_t, *queue_node_ptr;

// 큐 관리 구조체
typedef struct linked_queue {
    queue_node_ptr front_node_ptr;  // 프론트 포인터
    queue_node_ptr rear_node_ptr;   // 리어 포인터
    int element_count;              // 요소 개수
} linked_queue, *linked_queue_ptr;
// 연결 큐 초기화
linked_queue_ptr linked_queue_init(void) {
    linked_queue_ptr queue_ptr = (linked_queue_ptr)malloc(sizeof(linked_queue));
    if (queue_ptr != NULL) {
        queue_node_ptr dummy_node = (queue_node_ptr)malloc(sizeof(queue_node_t));
        dummy_node->next_node_ptr = dummy_node;
        queue_ptr->front_node_ptr = dummy_node;
        queue_ptr->rear_node_ptr = dummy_node;
        queue_ptr->element_count = 0;
    }
    return queue_ptr;
}

// 연결 큐에 데이터 삽입 (테일 삽입 방식)
void linked_queue_enqueue(linked_queue_ptr queue_ptr, queue_node_ptr new_node) {
    queue_ptr->rear_node_ptr->next_node_ptr = new_node;
    new_node->next_node_ptr = queue_ptr->front_node_ptr;
    queue_ptr->rear_node_ptr = new_node;
    queue_ptr->element_count++;
}

7. 스택과 큐의 비교

특성스택큐
연산 원칙LIFO (후입선출)FIFO (선입선출)
연산 가능端한쪽 끝단のみ (최상단)양쪽 끝단 (프론트: 삭제, 리어: 삽입)
주요 연산푸시, 팝, 피크인큐, 디큐, 프론트
적용 분야함수 호출, 표현식 평가, 백트래킹메시지 큐, 작업 스케줄링, 너비 우선 탐색

8. 실제 활용 사례

스택의 활용

스택은 다양한 알고리즘과 시스템에서 필수적으로 사용됩니다. 함수 호출 시 실행 흐름과 지역 변수를 저장하고 복원하는 데 스택이 활용됩니다. 수학 표현식에서는 중위 표기식을 후위 표기식으로 변환하거나 후위 표기식을 계산하는 데 사용됩니다. 소스 코드의 괄호가 올바르게 닫혀 있는지 검증하는 데도 스택이 필요합니다. 웹 브라우저의 뒤로 가기/앞으로 가기 기능도 두 개의 스택으로 구현됩니다.

큐의 활용

큐는 시스템 간 비동기 통신에서 메시지를 일시적으로 저장하는 데 사용됩니다. CPU 스케줄링이나 프린터 작업 대기열처럼 요청을 순서대로 처리해야 하는 경우에 필수적입니다. 그래프에서 너비 우선 탐색을 수행할 때 노드를 순차적으로 방문하기 위해 큐를 활용합니다. 캐시 메모리에서 오래된 데이터를 우선적으로 제거하는 FIFO 전략에도 큐가 사용됩니다.

9. 학습 시 주의사항

핵심 이해 포인트

스택의 LIFO 특성과 큐의 FIFO 특성을 정확히 이해해야 합니다. 순차 구현과 연결 구현 두 가지 방식을 모두 습득하고, 각 연산의 시간 복잡도를 분석할 수 있어야 합니다. 특히 순환 큐에서 모듈로 연산을 어떻게 활용하는지 반드시 이해해야 합니다.

흔히 발생하는 실수

스택이 비어있을 때 팝 연산을 수행하거나 스택이 가득 찼을 때 푸시 연산을 시도하는 경우가 있습니다. 큐에서도 마찬가지로 빈 큐에서 디큐하려고 하거나 상태 검사를 건너뛰는 실수가 발생합니다. 순환 큐에서는 특히 큐가 가득 찼는지 판단하는 조건식을 정확히 구현해야 합니다.

5월 22일 13:10에 게시됨

인기 태그

©2026 괴물 클럽