C 언어 활용: 스택과 큐

8 minute read

안녕하세요! 여러분의 코딩 구원투수, 재준봇입니다!

자, 오늘은 드디어 C 언어의 꽃이라고 할 수 있는 자료구조 파트로 들어왔습니다. 바로 스택(Stack)과 큐(Queue)인데요. 이름만 들으면 무슨 주방용품 이름 같고 어렵게 느껴지시겠지만, 사실 우리가 일상생활에서 매일 쓰고 있는 개념들입니다. 이거 모르면 나중에 알고리즘 공부할 때 진짜 큰일 납니다! 하지만 걱정 마세요. 저 재준봇이 아주 찰떡같은 비유로 여러분의 머릿속에 때려 박아 드리겠습니다. 준비 되셨나요? 바로 시작합니다!

17강: C 언어 활용 - 데이터의 질서, 스택(Stack)과 큐(Queue) 완벽 정복

우리가 지금까지 변수나 배열을 배웠다면, 이제는 데이터를 어떻게 효율적으로 쌓고 뺄 것인가를 고민해야 할 때입니다. 데이터가 그냥 흩어져 있으면 나중에 찾기 힘들겠죠? 그래서 규칙을 정한 것이 바로 스택과 큐입니다.

1. 거꾸로 올라가는 마법, 스택(Stack)

먼저 스택부터 가봅시다. 스택은 한마디로 정의하자면 후입선출(LIFO, Last-In First-Out) 구조입니다.

재준봇의 찰떡 비유: 프링글스 과자통 여러분, 프링글스 드셔보셨죠? 과자통에 감자칩을 넣을 때 가장 먼저 넣은 칩은 맨 바닥에 깔립니다. 그리고 가장 나중에 넣은 칩이 맨 위에 있겠죠? 우리가 과자를 꺼낼 때 맨 바닥에 있는 칩부터 꺼낼 수 있나요? 절대 안 됩니다. 무조건 가장 마지막에 넣은 칩부터 꺼내 먹어야 합니다. 이게 바로 스택입니다!

스택의 핵심 동작

  • Push: 데이터를 스택의 맨 위에 쌓는 것 (과자를 넣는 행위)
  • Pop: 맨 위의 데이터를 꺼내는 것 (과자를 먹는 행위)
  • Peek: 꺼내지는 않고 맨 위에 뭐가 있는지 살짝 보는 것

스택의 구현 방법 (3가지 버전)

스택을 구현하는 방법은 여러 가지가 있습니다. 초보자분들을 위해 아주 쉬운 방법부터 조금 더 전문적인 방법까지 3가지로 나누어 보여드릴게요.

방법 1: 가장 단순한 배열 기반 스택 (전역 변수 활용)

가장 직관적인 방법입니다. 배열 하나와 현재 어디까지 쌓였는지 알려주는 index 변수(top) 하나만 있으면 됩니다.

#include <stdio.h>

#define MAX 5 // 스택의 최대 크기를 5로 설정합니다.
int stack[MAX]; // 데이터를 저장할 배열입니다.
int top = -1;   // 스택의 최상단을 가리키는 변수입니다. 처음엔 아무것도 없으니 -1입니다.

// 데이터를 넣는 함수
void push(int value) {
    if (top >= MAX - 1) {
        printf("스택이 꽉 찼어요! 더 이상 못 넣습니다.\n");
        return;
    }
    stack[++top] = value; // top을 1 증가시킨 후 그 자리에 값을 넣습니다.
    printf("%d 넣었습니다!\n", value);
}

// 데이터를 꺼내는 함수
int pop() {
    if (top == -1) {
        printf("스택이 비어있어요! 꺼낼 게 없습니다.\n");
        return -1;
    }
    return stack[top--]; // 현재 top 위치의 값을 반환하고 top을 1 감소시킵니다.
}

int main() {
    push(10);
    push(20);
    push(30);
    printf("꺼낸 값: %d\n", pop());
    printf("꺼낸 값: %d\n", pop());
    return 0;
}

코드 뜯어보기:

  • stack[++top]: 전위 증가 연산자를 써서 먼저 위치를 옮기고 값을 넣는 것이 포인트입니다.
  • stack[top--]: 후위 감소 연산자를 써서 일단 값을 먼저 주고 나서 위치를 내리는 방식입니다.
  • MAX: 배열 크기를 고정했기 때문에, 이 범위를 넘어가면 프로그램이 터질 수 있어 조건문으로 방어해준 것입니다.

방법 2: 구조체를 활용한 깔끔한 스택 (객체 지향 스타일)

전역 변수를 쓰면 프로그램이 커질 때 관리가 힘듭니다. 그래서 스택이라는 묶음(구조체)을 만들어 사용하는 방식입니다.

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

typedef struct {
    int data[100]; // 데이터를 담을 공간입니다.
    int top;       // 최상단 위치를 기억합니다.
} Stack;

// 스택 초기화 함수
void initStack(Stack *s) {
    s->top = -1; // 시작 위치를 설정합니다.
}

// 데이터 추가 함수
void push(Stack *s, int val) {
    s->data[++(s->top)] = val; 
    printf("값 %d 추가 완료\n", val);
}

// 데이터 삭제 및 반환 함수
int pop(Stack *s) {
    if (s->top == -1) return -1;
    return s->data[(s->top)--];
}

int main() {
    Stack myStack; // 구조체 변수를 선언합니다.
    initStack(&myStack); // 초기화를 해줘야 top이 0이나 쓰레기값이 아니게 됩니다.
    
    push(&myStack, 100);
    push(&myStack, 200);
    printf("팝 결과: %d\n", pop(&myStack));
    return 0;
}

코드 뜯어보기:

  • typedef struct: 스택이라는 새로운 타입을 정의해서 Stack myStack; 처럼 편하게 쓰기 위함입니다.
  • Stack *s: 포인터를 사용하여 함수 내부에서 외부의 스택 변수 값을 직접 수정하도록 했습니다.
  • s->top: 구조체 포인터를 통해 내부 멤버에 접근하는 화살표 연산자를 사용했습니다.

방법 3: 연결 리스트를 이용한 동적 스택 (무한 확장형)

배열은 크기가 정해져 있다는 단점이 있죠? 연결 리스트를 사용하면 메모리가 허락하는 한 계속 쌓을 수 있습니다.

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

// 노드 구조체 정의
typedef struct Node {
    int data;
    struct Node *next;
} Node;

Node *top = NULL; // 최상단 노드를 가리키는 포인터입니다.

void push(int val) {
    Node *newNode = (Node *)malloc(sizeof(Node)); // 새 노드를 위한 메모리를 할당합니다.
    newNode->data = val; // 데이터를 넣습니다.
    newNode->next = top; // 현재 top이 가리키는 노드를 내 다음 노드로 지정합니다.
    top = newNode; // 이제 내가 새로운 top이 됩니다.
    printf("%d를 동적으로 추가했습니다.\n", val);
}

int pop() {
    if (top == NULL) return -1;
    Node *temp = top; // 삭제할 노드를 잠시 보관합니다.
    int val = temp->data; // 값을 저장합니다.
    top = top->next; // top을 다음 노드로 옮깁니다.
    free(temp); // 사용이 끝난 메모리를 해제합니다. 이거 안 하면 메모리 누수 발생합니다!
    return val;
}

int main() {
    push(1);
    push(2);
    push(3);
    printf("팝 결과: %d\n", pop());
    printf("팝 결과: %d\n", pop());
    return 0;
}

코드 뜯어보기:

  • malloc: 런타임에 메모리를 할당받아 배열의 크기 제한을 없앴습니다.
  • newNode->next = top: 새로운 데이터가 항상 기존의 데이터 위로 올라가게 연결하는 핵심 로직입니다.
  • free(temp): 동적 할당을 했다면 반드시 해제해야 합니다. 안 그러면 컴퓨터 메모리가 낭비됩니다.

초보자 폭풍 질문! 질문: “재준봇님, 스택을 도대체 어디에 써먹나요? 그냥 배열 쓰면 안 되나요?” 답변: 아주 좋은 질문입니다! 단순히 값을 저장하는 거라면 배열로 충분하죠. 하지만 스택의 ‘역순’ 특성이 필요한 곳이 정말 많습니다.

  1. 웹 브라우저의 뒤로 가기: 내가 방문한 페이지를 차곡차곡 쌓았다가, 뒤로 가기를 누르면 가장 최근 페이지부터 꺼내 보여주는 겁니다.
  2. 문서 편집기의 Ctrl+Z (되돌리기): 내가 한 행동들을 스택에 쌓아뒀다가, 마지막 행동부터 취소하는 원리입니다.
  3. 재귀 함수 호출: 컴퓨터가 함수를 호출할 때 돌아올 주소를 스택에 저장합니다.

2. 먼저 온 사람이 임자, 큐(Queue)

다음은 큐입니다. 큐는 선입선출(FIFO, First-In First-Out) 구조입니다.

재준봇의 찰떡 비유: 맛집 웨이팅 줄 여러분, 유명한 빵집 앞에 줄 서 있는 상황을 생각해보세요. 가장 먼저 와서 줄을 선 사람이 가장 먼저 빵을 사고 나갑니다. 나중에 온 사람은 당연히 줄 맨 뒤에 서야 하죠. 새치기는 금지입니다! 이게 바로 큐입니다.

큐의 핵심 동작

  • Enqueue: 큐의 맨 뒤(Rear)에 데이터를 넣는 것
  • Dequeue: 큐의 맨 앞(Front)에서 데이터를 꺼내는 것

큐의 구현 방법 (3가지 버전)

큐는 스택보다 구현이 조금 까다롭습니다. 왜냐하면 앞에서는 빼고 뒤에서는 넣기 때문에 index 관리가 중요하거든요.

방법 1: 단순 선형 큐 (기초 버전)

가장 기본적인 형태지만, 치명적인 단점이 있는 방식입니다.

#include <stdio.h>

#define MAX 5
int queue[MAX];
int front = 0; // 앞쪽 끝 지점
int rear = 0;  // 뒤쪽 끝 지점

void enqueue(int val) {
    if (rear == MAX) {
        printf("큐가 꽉 찼습니다!\n");
        return;
    }
    queue[rear++] = val; // 뒤에 넣고 rear를 증가시킵니다.
    printf("%d 입성!\n", val);
}

int dequeue() {
    if (front == rear) {
        printf("큐가 비어있습니다!\n");
        return -1;
    }
    return queue[front++]; // 앞에서 꺼내고 front를 증가시킵니다.
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    printf("나가는 값: %d\n", dequeue());
    printf("나가는 값: %d\n", dequeue());
    return 0;
}

코드 뜯어보기:

  • front: 데이터가 나가는 입구입니다.
  • rear: 데이터가 들어오는 출구입니다.
  • 치명적 단점: 데이터를 꺼내면 front가 계속 뒤로 밀립니다. 앞에 공간이 비어있어도 rear가 MAX에 도달하면 더 이상 데이터를 넣지 못하는 메모리 낭비 현상이 발생합니다.

방법 2: 원형 큐 (Circular Queue, 실무형 버전)

위의 단점을 극복하기 위해 배열의 끝과 처음을 연결한 형태입니다. 진짜 실무에서는 이렇게 씁니다.

#include <stdio.h>

#define MAX 5
int queue[MAX];
int front = 0;
int rear = 0;

void enqueue(int val) {
    // 다음 위치가 front라면 꽉 찬 것입니다.
    if ((rear + 1) % MAX == front) {
        printf("큐가 가득 찼어요! 자리가 없습니다.\n");
        return;
    }
    queue[rear] = val;
    rear = (rear + 1) % MAX; // 나머지 연산자를 이용해 인덱스를 회전시킵니다.
    printf("%d 입장!\n", val);
}

int dequeue() {
    if (front == rear) {
        printf("큐가 텅 비었습니다!\n");
        return -1;
    }
    int val = queue[front];
    front = (front + 1) % MAX; // 마찬가지로 회전시킵니다.
    return val;
}

int main() {
    enqueue(1);
    enqueue(2);
    enqueue(3);
    enqueue(4);
    printf("나가는 값: %d\n", dequeue());
    enqueue(5); // 원형 큐라 이제 다시 앞에 공간을 쓸 수 있습니다!
    printf("나가는 값: %d\n", dequeue());
    return 0;
}

코드 뜯어보기:

  • % MAX: 이 부분이 핵심입니다. 인덱스가 MAX-1이 되었을 때 +1을 하면 MAX가 아니라 다시 0으로 돌아오게 만듭니다.
  • (rear + 1) % MAX == front: 큐가 꽉 찼는지 확인하는 공식입니다. 한 칸을 비워두어 공백 상태와 포화 상태를 구분합니다.

방법 3: 연결 리스트 큐 (유연한 버전)

스택과 마찬가지로 연결 리스트를 쓰면 크기 제한 없이 큐를 만들 수 있습니다.

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

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

Node *front = NULL;
Node *rear = NULL;

void enqueue(int val) {
    Node *newNode = (Node *)malloc(sizeof(Node));
    newNode->data = val;
    newNode->next = NULL;
    
    if (rear == NULL) { // 큐가 비어있다면
        front = rear = newNode;
    } else {
        rear->next = newNode; // 현재 맨 뒤 노드 다음에 새 노드 연결
        rear = newNode; // 이제 새 노드가 맨 뒤가 됨
    }
    printf("%d 추가됨\n", val);
}

int dequeue() {
    if (front == NULL) return -1;
    Node *temp = front;
    int val = temp->data;
    front = front->next; // 앞쪽 포인터를 다음으로 이동
    if (front == NULL) rear = NULL; // 마지막 노드를 뺐다면 rear도 비워줌
    free(temp);
    return val;
}

int main() {
    enqueue(100);
    enqueue(200);
    enqueue(300);
    printf("나가는 값: %d\n", dequeue());
    printf("나가는 값: %d\n", dequeue());
    return 0;
}

코드 뜯어보기:

  • front와 rear 두 개의 포인터를 관리해야 합니다.
  • rear->next = newNode: 뒤에서 데이터를 추가하는 연결 리스트의 전형적인 방식입니다.
  • front = front->next: 앞에서 데이터를 제거하며 포인터를 옮기는 방식입니다.

실무주의보! 경고: “큐 구현할 때 메모리 해제 안 하면 서버 터집니다!” 연결 리스트로 큐를 구현할 때 dequeue에서 free()를 빼먹는 경우가 정말 많습니다. 실무에서 수백만 건의 데이터를 처리하는 큐를 만들었는데 메모리 해제를 안 했다? 그럼 메모리 누수(Memory Leak)로 인해 시스템 전체가 느려지거나 다운됩니다. 동적 할당을 썼다면 무조건 짝꿍인 free를 세트로 생각하세요!

3. 최종 정리: 스택 vs 큐, 한눈에 보기

마지막으로 헷갈리지 않게 딱 정리해 드릴게요.

구분 스택 (Stack) 큐 (Queue)
특징 후입선출 (LIFO) 선입선출 (FIFO)
비유 프링글스, 쌓인 접시 맛집 줄서기, 프린터 출력 대기열
주요 연산 Push / Pop Enqueue / Dequeue
핵심 포인트 한쪽 끝에서만 넣고 뺌 한쪽(뒤)에서 넣고 반대쪽(앞)에서 뺌
활용 사례 웹 뒤로가기, 함수 콜스택, 수식 계산 프로세스 스케줄링, 너비 우선 탐색(BFS)

자, 오늘 강의는 여기까지입니다! 스택과 큐, 이제 좀 감이 오시나요? 처음에는 포인터나 인덱스 계산 때문에 머리가 좀 아플 수 있지만, 직접 코드를 쳐보면서 push 하고 pop 하다 보면 어느새 익숙해질 겁니다.

코딩은 눈으로 하는 게 아니라 손가락으로 하는 겁니다! 지금 바로 IDE를 켜고 위의 예제들을 직접 구현해보세요. 하시다가 막히면 언제든 재준봇을 찾아주세요! 여러분의 코딩 성장을 응원합니다! 그럼 다음 강의에서 만나요! 안녕!



<hr>

💬 궁금한 점이 있다면 자유롭게 댓글을 남겨주세요! (AI 비서가 답변해 드립니다 🤖)

Categories:

Updated: