스택과 큐는 컴퓨터 과학에서 가장 기본적인 자료구조 중 하나로, 각각 후입선출(LIFO)과 선입선출(FIFO) 특성을 가집니다. 이번 글에서는 배열 기반과 연결 리스트 기반의 두 가지 구현 방법을 모두 다룹니다.

스택(Stack) 자료구조

스택은 후입선출(LIFO) 원칙을 따르는 자료구조로, 가장 마지막에 추가된 요소가 가장 먼저 제거됩니다.

배열 기반 스택 구현

/* 스택 헤더 파일 - StackArray.h */
#ifndef STACK_ARRAY_H
#define STACK_ARRAY_H

#define MAX_STACK_SIZE 100
typedef int stack_element_t;

typedef struct {
    stack_element_t items[MAX_STACK_SIZE];
    int top_index;
} ArrayStack;

void initStack(ArrayStack *stack);
int pushStack(ArrayStack *stack, stack_element_t value);
int popStack(ArrayStack *stack, stack_element_t *value);
int peekStack(const ArrayStack *stack, stack_element_t *value);
int isStackEmpty(const ArrayStack *stack);
int isStackFull(const ArrayStack *stack);

#endif

/* 스택 구현 파일 - StackArray.c */
#include "StackArray.h"
#include <stdio.h>

void initStack(ArrayStack *stack) {
    stack->top_index = -1;
}

int pushStack(ArrayStack *stack, stack_element_t value) {
    if (isStackFull(stack)) {
        printf("스택이 가득 찼습니다!\n");
        return 0;
    }
    stack->items[++stack->top_index] = value;
    return 1;
}

int popStack(ArrayStack *stack, stack_element_t *value) {
    if (isStackEmpty(stack)) {
        printf("스택이 비어있습니다!\n");
        return 0;
    }
    *value = stack->items[stack->top_index--];
    return 1;
}

int peekStack(const ArrayStack *stack, stack_element_t *value) {
    if (isStackEmpty(stack)) {
        return 0;
    }
    *value = stack->items[stack->top_index];
    return 1;
}

int isStackEmpty(const ArrayStack *stack) {
    return stack->top_index == -1;
}

int isStackFull(const ArrayStack *stack) {
    return stack->top_index == MAX_STACK_SIZE - 1;
}

연결 리스트 기반 스택 구현

/* 스택 헤더 파일 - StackList.h */
#ifndef STACK_LIST_H
#define STACK_LIST_H

typedef int stack_value_t;

typedef struct stack_node {
    stack_value_t data;
    struct stack_node *next;
} StackNode;

typedef struct {
    StackNode *top_node;
    int count;
} LinkedListStack;

void initLinkedListStack(LinkedListStack *stack);
int pushLinkedListStack(LinkedListStack *stack, stack_value_t value);
int popLinkedListStack(LinkedListStack *stack, stack_value_t *value);
int peekLinkedListStack(const LinkedListStack *stack, stack_value_t *value);
int isLinkedListStackEmpty(const LinkedListStack *stack);

#endif

/* 스택 구현 파일 - StackList.c */
#include "StackList.h"
#include <stdio.h>
#include <stdlib.h>

void initLinkedListStack(LinkedListStack *stack) {
    stack->top_node = NULL;
    stack->count = 0;
}

int pushLinkedListStack(LinkedListStack *stack, stack_value_t value) {
    StackNode *new_node = (StackNode *)malloc(sizeof(StackNode));
    if (new_node == NULL) {
        printf("메모리 할당 실패!\n");
        return 0;
    }
    
    new_node->data = value;
    new_node->next = stack->top_node;
    stack->top_node = new_node;
    stack->count++;
    return 1;
}

int popLinkedListStack(LinkedListStack *stack, stack_value_t *value) {
    if (isLinkedListStackEmpty(stack)) {
        printf("스택이 비어있습니다!\n");
        return 0;
    }
    
    StackNode *temp = stack->top_node;
    *value = temp->data;
    stack->top_node = temp->next;
    free(temp);
    stack->count--;
    return 1;
}

int peekLinkedListStack(const LinkedListStack *stack, stack_value_t *value) {
    if (isLinkedListStackEmpty(stack)) {
        return 0;
    }
    
    *value = stack->top_node->data;
    return 1;
}

int isLinkedListStackEmpty(const LinkedListStack *stack) {
    return stack->top_node == NULL;
}

큐(Queue) 자료구조

큐는 선입선출(FIFO) 원칙을 따르는 자료구조로, 가장 먼저 추가된 요소가 가장 먼저 제거됩니다. 이번 구현에서는 양방향 큐(Deque) 개념도 포함합니다.

배열 기반 큐 구현

/* 큐 헤더 파일 - QueueArray.h */
#ifndef QUEUE_ARRAY_H
#define QUEUE_ARRAY_H

#define MAX_QUEUE_SIZE 100
typedef int queue_element_t;

typedef struct {
    queue_element_t elements[MAX_QUEUE_SIZE];
    int front;
    int rear;
    int size;
} ArrayQueue;

void initQueue(ArrayQueue *queue);
int enqueue(ArrayQueue *queue, queue_element_t value);
int dequeue(ArrayQueue *queue, queue_element_t *value);
int peekQueue(const ArrayQueue *queue, queue_element_t *value);
int isQueueEmpty(const ArrayQueue *queue);
int isQueueFull(const ArrayQueue *queue);
int getQueueSize(const ArrayQueue *queue);

#endif

/* 큐 구현 파일 - QueueArray.c */
#include "QueueArray.h"
#include <stdio.h>

void initQueue(ArrayQueue *queue) {
    queue->front = 0;
    queue->rear = 0;
    queue->size = 0;
}

int enqueue(ArrayQueue *queue, queue_element_t value) {
    if (isQueueFull(queue)) {
        printf("큐가 가득 찼습니다!\n");
        return 0;
    }
    
    queue->elements[queue->rear] = value;
    queue->rear = (queue->rear + 1) % MAX_QUEUE_SIZE;
    queue->size++;
    return 1;
}

int dequeue(ArrayQueue *queue, queue_element_t *value) {
    if (isQueueEmpty(queue)) {
        printf("큐가 비어있습니다!\n");
        return 0;
    }
    
    *value = queue->elements[queue->front];
    queue->front = (queue->front + 1) % MAX_QUEUE_SIZE;
    queue->size--;
    return 1;
}

int peekQueue(const ArrayQueue *queue, queue_element_t *value) {
    if (isQueueEmpty(queue)) {
        return 0;
    }
    
    *value = queue->elements[queue->front];
    return 1;
}

int isQueueEmpty(const ArrayQueue *queue) {
    return queue->size == 0;
}

int isQueueFull(const ArrayQueue *queue) {
    return queue->size == MAX_QUEUE_SIZE;
}

int getQueueSize(const ArrayQueue *queue) {
    return queue->size;
}

연결 리스트 기반 큐 구현

/* 큐 헤더 파일 - QueueList.h */
#ifndef QUEUE_LIST_H
#define QUEUE_LIST_H

typedef int queue_value_t;

typedef struct queue_node {
    queue_value_t data;
    struct queue_node *next;
} QueueNode;

typedef struct {
    QueueNode *head;
    QueueNode *tail;
    int length;
} LinkedListQueue;

LinkedListQueue* createQueue();
void destroyQueue(LinkedListQueue *queue);
int enqueueQueue(LinkedListQueue *queue, queue_value_t value);
int dequeueQueue(LinkedListQueue *queue, queue_value_t *value);
int peekQueueList(const LinkedListQueue *queue, queue_value_t *value);
int isQueueListEmpty(const LinkedListQueue *queue);
int getQueueListSize(const LinkedListQueue *queue);

#endif

/* 큐 구현 파일 - QueueList.c */
#include "QueueList.h"
#include <stdio.h>
#include <stdlib.h>

LinkedListQueue* createQueue() {
    LinkedListQueue *queue = (LinkedListQueue *)malloc(sizeof(LinkedListQueue));
    if (queue == NULL) {
        printf("메모리 할당 실패!\n");
        return NULL;
    }
    
    queue->head = NULL;
    queue->tail = NULL;
    queue->length = 0;
    return queue;
}

void destroyQueue(LinkedListQueue *queue) {
    if (queue == NULL) return;
    
    while (queue->head != NULL) {
        QueueNode *temp = queue->head;
        queue->head = temp->next;
        free(temp);
    }
    
    free(queue);
}

int enqueueQueue(LinkedListQueue *queue, queue_value_t value) {
    QueueNode *new_node = (QueueNode *)malloc(sizeof(QueueNode));
    if (new_node == NULL) {
        printf("메모리 할당 실패!\n");
        return 0;
    }
    
    new_node->data = value;
    new_node->next = NULL;
    
    if (queue->tail == NULL) {
        queue->head = new_node;
        queue->tail = new_node;
    } else {
        queue->tail->next = new_node;
        queue->tail = new_node;
    }
    
    queue->length++;
    return 1;
}

int dequeueQueue(LinkedListQueue *queue, queue_value_t *value) {
    if (isQueueListEmpty(queue)) {
        printf("큐가 비어있습니다!\n");
        return 0;
    }
    
    QueueNode *temp = queue->head;
    *value = temp->data;
    queue->head = temp->next;
    
    if (queue->head == NULL) {
        queue->tail = NULL;
    }
    
    free(temp);
    queue->length--;
    return 1;
}

int peekQueueList(const LinkedListQueue *queue, queue_value_t *value) {
    if (isQueueListEmpty(queue)) {
        return 0;
    }
    
    *value = queue->head->data;
    return 1;
}

int isQueueListEmpty(const LinkedListQueue *queue) {
    return queue->length == 0;
}

int getQueueListSize(const LinkedListQueue *queue) {
    return queue->length;
}

테스트 코드 예시

/* 스택 테스트 코드 */
#include "StackArray.h"
#include "StackList.h"
#include <stdio.h>

void testArrayStack() {
    ArrayStack stack;
    initStack(&stack);
    
    // 스택에 요소 추가
    for (int i = 1; i <= 10; i++) {
        pushStack(&stack, i * 10);
    }
    
    // 스택에서 요소 제거 및 출력
    stack_element_t value;
    printf("배열 기반 스택 내용:\n");
    while (!isStackEmpty(&stack)) {
        peekStack(&stack, &value);
        printf("%d ", value);
        popStack(&stack, &value);
    }
    printf("\n");
}

void testLinkedListStack() {
    LinkedListStack stack;
    initLinkedListStack(&stack);
    
    // 스택에 요소 추가
    for (int i = 1; i <= 10; i++) {
        pushLinkedListStack(&stack, i * 10);
    }
    
    // 스택에서 요소 제거 및 출력
    stack_value_t value;
    printf("연결 리스트 기반 스택 내용:\n");
    while (!isLinkedListStackEmpty(&stack)) {
        peekLinkedListStack(&stack, &value);
        printf("%d ", value);
        popLinkedListStack(&stack, &value);
    }
    printf("\n");
}

int main() {
    testArrayStack();
    testLinkedListStack();
    return 0;
}

/* 큐 테스트 코드 */
#include "QueueArray.h"
#include "QueueList.h"
#include <stdio.h>

void testArrayQueue() {
    ArrayQueue queue;
    initQueue(&queue);
    
    // 큐에 요소 추가
    for (int i = 1; i <= 10; i++) {
        enqueue(&queue, i * 10);
    }
    
    // 큐에서 요소 제거 및 출력
    queue_element_t value;
    printf("배열 기반 큐 내용:\n");
    while (!isQueueEmpty(&queue)) {
        peekQueue(&queue, &value);
        printf("%d ", value);
        dequeue(&queue, &value);
    }
    printf("\n");
}

void testLinkedListQueue() {
    LinkedListQueue *queue = createQueue();
    
    // 큐에 요소 추가
    for (int i = 1; i <= 10; i++) {
        enqueueQueue(queue, i * 10);
    }
    
    // 큐에서 요소 제거 및 출력
    queue_value_t value;
    printf("연결 리스트 기반 큐 내용:\n");
    while (!isQueueListEmpty(queue)) {
        peekQueueList(queue, &value);
        printf("%d ", value);
        dequeueQueue(queue, &value);
    }
    printf("\n");
    
    destroyQueue(queue);
}

int main() {
    testArrayQueue();
    testLinkedListQueue();
    return 0;
}

구현 분석

배열 기반 구현은 고정된 크기의 메모리를 사용하여 효율적이지만, 크기 제한이 있습니다. 반면 연결 리스트 기반 구현은 동적 메모리 할당을 통해 유연한 크기를 가집니다. 배열 기반 구현에서는 순환 버퍼 기법을 사용하여 공간을 효율적으로 활용할 수 있습니다.

두 자료구조 모두 시간 복잡도 O(1)의 삽입 및 삭제 연산을 제공하므로 다양한 알고리즘에 활용될 수 있습니다. 스택은 재귀 알고리즘, 표현식 평가, 역추적 문제 등에 큐는 작업 스케줄링, 너비 우선 탐색 등에 주로 사용됩니다.