학습 목표
이번 주차를 마치면 다음을 할 수 있습니다.
- 스택(LIFO)을 배열과 연결 리스트 두 방식으로 구현하고, 어느 쪽을 언제 쓸지 고를 수 있다
- 함수 호출 스택이 어떻게 쌓이고 걷히는지, 스택 오버플로가 왜 나는지 설명할 수 있다
- 원형 배열 큐(FIFO)의 감아 돌기(wrap-around)를
%연산으로 구현하고, 인덱스가 어떻게 움직이는지 손으로 추적할 수 있다 - 연결 리스트 큐의 단골 버그(tail 정리 누락)를 직접 일으키고 Valgrind와 AddressSanitizer로 잡아낼 수 있다
- 우선순위 큐와 생산자-소비자 패턴이 어디에 쓰이는지 안다
- 덱(양방향 큐)으로 스택과 큐를 모두 흉내 낼 수 있고, 음수 인덱스 함정을 피할 수 있다
- 함수형 매크로의 세 가지 함정을 피하고, 매크로로 타입 안전한 제네릭 코드를 만들 수 있다
들어가며
브라우저의 뒤로 가기 버튼을 누르면 어떻게 직전 페이지로 돌아갈까요? 편집기에서 Ctrl + Z 를 누르면 왜 가장 최근에 한 일부터 취소될까요? 1주차에서 gcc 가 “여기 ; 가 빠졌다”고 정확히 짚어 준 것을 봤는데, 컴파일러는 { } ( ) [ ] 의 짝이 맞는지 어떻게 알까요? 그리고 프린터에 문서 세 개를 연달아 보내면 왜 먼저 보낸 것부터 인쇄될까요?
답은 전부 같습니다. 데이터를 한 줄로 세워 두고, 어느 끝에서 넣고 빼느냐만 다른 두 가지 규칙입니다. 나중에 넣은 것을 먼저 빼면 스택(stack), 먼저 넣은 것을 먼저 빼면 큐(queue), 양쪽 끝을 다 쓰면 덱(deque) 입니다. 이 셋을 선형 자료구조라고 부릅니다. 규칙이 너무 단순해서 시시해 보이지만, 여러분이 이 글을 읽는 지금도 CPU 안에서는 함수 호출 스택이 쌓이고 있고, 키보드 입력은 큐를 통과하는 중입니다.
지난 10주차에 우리는 벽돌을 구웠습니다. 동적 배열과 연결 리스트입니다. 이번 주에는 그 벽돌로 첫 건물을 짓습니다. 놀랍게도 새 재료는 거의 필요 없습니다. 지난주의 push_back 과 pop_back 을 그대로 쓰면 스택이고, push_back 과 pop_front 를 쓰면 큐입니다. 그래서 이번 주의 핵심은 새 코드를 외우는 것이 아니라, 같은 코드에 다른 규칙을 씌우면 전혀 다른 도구가 된다는 것을 몸으로 익히는 것입니다.
덤으로 매크로를 배웁니다. 지난주 void * 로 만든 제네릭 코드는 잘못된 타입을 넣어도 컴파일러가 잡지 못했습니다. 이번 주에는 매크로로 타입별 코드를 찍어내서, 잘못된 타입이면 컴파일 단계에서 걸리게 만듭니다. 그 전에 매크로가 여러분을 물어뜯는 세 가지 방법부터 실제로 물려 봅니다.
이번 주 예제는 모두 week11/ 폴더에 있고, 저장소 루트에서 이렇게 빌드합니다.
$ cd week11
$ make
$ ls build
bracket_check deque_array postfix_calc queue_circular stack_list
browser_history generic_macro priority_queue queue_list task_scheduler
call_stack_sim macro_basics producer_consumer stack_array xmacro
5주차에서 배운 대로 Makefile 이 examples/*.c 와 projects/*.c 를 전부 build/ 아래에 같은 이름의 실행 파일로 만듭니다. 컴파일 옵션은 늘 쓰던 -Wall -Wextra -std=c11 -g 이고, 이번 주 소스 15개는 모두 경고 0개로 컴파일됩니다. 글에 실린 출력은 전부 이 머신에서 실제로 돌린 결과입니다.
1. 스택 (Stack) — 나중에 온 것이 먼저
1.1 LIFO: 접시 쌓기
식당 주방의 접시 더미를 떠올려 보세요. 설거지한 접시는 맨 위에 올립니다. 요리사가 접시를 가져갈 때도 맨 위에서 집습니다. 중간이나 바닥에서 빼는 일은 없습니다. 그러니 가장 나중에 올린 접시가 가장 먼저 쓰입니다. 이것이 LIFO(Last In, First Out), “나중에 들어온 것이 먼저 나간다”입니다.
스택의 연산은 딱 세 개입니다. 이름은 영어 동사 그대로입니다.
| 연산 | 뜻 | 하는 일 | 시간 |
|---|---|---|---|
| push (밀어 넣다) | 맨 위에 쌓기 | 새 원소를 top 위에 올린다 | O(1) |
| pop (튀어나오다) | 맨 위에서 꺼내기 | top 원소를 빼서 돌려주고, 그 아래가 새 top 이 된다 | O(1) |
| peek (엿보다) | 꺼내지 않고 맨 위 보기 | top 원소의 값만 알려 준다. 스택은 그대로 | O(1) |
여기서 top 은 “맨 위 원소” 또는 “맨 위 원소가 있는 자리”를 뜻하는 이름입니다. 앞으로 코드에서 계속 만납니다.
O(1) 이 세 번 나온 것을 눈여겨보세요. 10주차 성능 비교에서 봤듯이 “몇 개가 들어 있든 시간이 같다”는 뜻입니다. 스택은 한쪽 끝만 건드리기 때문에 원소가 백만 개여도 push 와 pop 이 한 번의 대입으로 끝납니다. 이 성질 덕분에 컴퓨터는 함수를 초당 수억 번 호출하고 돌아올 수 있습니다.
1.2 배열 기반 스택: 이미 다 배웠습니다
지난주에 만든 동적 배열을 기억하시나요? push_back 은 끝에 붙이고 pop_back 은 끝에서 뗐습니다. 배열의 끝을 스택의 top 이라고 부르기로 하면, 그 코드가 그대로 스택입니다. examples/stack_array.c 전체를 봅시다.
/*
* stack_array.c - 배열 기반 스택 (동적 확장)
* 11주차: 스택, 큐, 덱
*
* 스택(Stack)은 "나중에 넣은 것이 먼저 나오는" LIFO 구조입니다.
* (Last In, First Out - 접시 쌓기를 떠올리세요)
*
* 10주차의 동적 배열을 그대로 재사용합니다.
* push = push_back, pop = pop_back. 이미 다 배운 것입니다!
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *data;
size_t size; /* 쌓인 개수 = 다음에 push될 위치 */
size_t capacity;
} Stack;
void stack_init(Stack *s) {
s->data = NULL;
s->size = 0;
s->capacity = 0;
}
int stack_is_empty(const Stack *s) {
return s->size == 0;
}
/* push: 맨 위에 쌓기. 공간이 없으면 2배 확장 (10주차 패턴 그대로) */
int stack_push(Stack *s, int value) {
if (s->size == s->capacity) {
size_t new_cap = (s->capacity == 0) ? 4 : s->capacity * 2;
int *tmp = realloc(s->data, new_cap * sizeof(int));
if (tmp == NULL) return 0;
s->data = tmp;
s->capacity = new_cap;
}
s->data[s->size++] = value;
return 1;
}
/* pop: 맨 위에서 꺼내기 */
int stack_pop(Stack *s, int *out) {
if (stack_is_empty(s)) return 0;
s->size--;
if (out != NULL) *out = s->data[s->size];
return 1;
}
/* peek: 꺼내지 않고 맨 위만 들여다보기 */
int stack_peek(const Stack *s, int *out) {
if (stack_is_empty(s)) return 0;
*out = s->data[s->size - 1];
return 1;
}
void stack_free(Stack *s) {
free(s->data);
stack_init(s);
}
void stack_print(const Stack *s) {
printf("바닥 [");
for (size_t i = 0; i < s->size; i++) {
printf("%d%s", s->data[i], (i + 1 < s->size) ? " " : "");
}
printf("] <- top\n");
}
int main(void) {
Stack s;
stack_init(&s);
printf("=== push: 접시 쌓기 ===\n");
for (int i = 1; i <= 5; i++) {
stack_push(&s, i * 10);
printf("push(%2d): ", i * 10);
stack_print(&s);
}
printf("\n=== peek: 맨 위 확인 (꺼내지 않음) ===\n");
int top;
stack_peek(&s, &top);
printf("top = %d (size는 그대로 %zu)\n", top, s.size);
printf("\n=== pop: 역순으로 나온다 (LIFO) ===\n");
int value;
while (stack_pop(&s, &value)) {
printf("pop() = %2d, 남은 것: ", value);
stack_print(&s);
}
printf("\n빈 스택에서 pop 시도: %s\n",
stack_pop(&s, &value) ? "성공" : "실패 (안전하게 거부)");
stack_free(&s);
return 0;
}
구조체 세 칸의 뜻
typedef struct {
int *data; /* 원소들이 들어 있는 배열 (힙에 있음) */
size_t size; /* 쌓인 개수 = 다음에 push될 위치 */
size_t capacity; /* 배열의 칸 수 (size 이하로 내려갈 수 없음) */
} Stack;
data: 원소가 실제로 들어 있는 배열입니다. 7주차에서 배운 대로malloc/realloc으로 힙에 잡습니다. 처음에는NULL입니다.size: 지금 몇 개가 쌓여 있는지입니다. 그런데 주석을 보면 “다음에 push될 위치”라고도 적혀 있습니다. 두 뜻이 같은 숫자라는 게 배열 스택의 핵심입니다. 원소가 3개면data[0],data[1],data[2]가 차 있고, 다음 원소는data[3]에 들어가니까요.size하나가 개수이자 다음 자리입니다.capacity: 배열에 칸이 몇 개 있는지입니다.size가capacity에 닿으면 배열을 늘려야 합니다.
size_t 는 2주차에서 본 “크기와 개수를 담는 부호 없는 정수”입니다. 음수가 될 수 없는 값에 씁니다.
push 한 줄씩
int stack_push(Stack *s, int value) {
if (s->size == s->capacity) {
칸이 다 찼는지 먼저 봅니다. 처음에는 size 도 capacity 도 0이라 첫 push 부터 이 안으로 들어갑니다.
size_t new_cap = (s->capacity == 0) ? 4 : s->capacity * 2;
새 크기를 정합니다. 3주차의 조건 연산자입니다. 처음이면 4칸, 아니면 지금의 2배입니다. 왜 2배일까요? 10주차에서 잰 대로, 매번 1칸씩 늘리면 push 마다 realloc 이 일어나 O(n) 이 되지만, 2배씩 늘리면 realloc 횟수가 log n 으로 줄어서 push 한 번의 평균 비용이 O(1) 에 수렴합니다. 이것을 분할 상환 O(1) 이라고 부릅니다.
int *tmp = realloc(s->data, new_cap * sizeof(int));
if (tmp == NULL) return 0;
s->data = tmp;
s->capacity = new_cap;
}
7주차의 realloc 안전 패턴입니다. s->data = realloc(s->data, ...) 라고 바로 대입하면, 실패해서 NULL 이 돌아왔을 때 원래 배열의 주소를 잃어버려 누수가 납니다. 그래서 임시 변수 tmp 에 받아 확인한 뒤에 옮깁니다.
s->data[s->size++] = value;
return 1;
}
이 한 줄이 push 의 전부입니다. 3주차에서 배운 후위 ++ 의 성질 그대로입니다. s->data[s->size] 에 값을 넣은 뒤, size 를 1 늘립니다. size 가 3이었다면 data[3] 에 넣고 size 는 4가 됩니다. “다음 자리”에 넣고 “개수”를 늘린 것인데, 둘이 같은 변수라 한 줄로 끝납니다.
pop 한 줄씩
int stack_pop(Stack *s, int *out) {
if (stack_is_empty(s)) return 0;
빈 스택에서 pop 하면 거부합니다. 이 검사가 없으면 size 가 0에서 1을 빼서 size_t 의 최댓값(18446744073709551615)이 되고, data[그 값] 을 읽으려다 죽습니다. 이 검사가 얼마나 중요한지는 뒤의 실험에서 봅니다.
s->size--;
if (out != NULL) *out = s->data[s->size];
return 1;
}
push 의 정확한 역순입니다. push 는 “넣고 늘리기”, pop 은 “줄이고 꺼내기”입니다. size 가 4였다면 3으로 줄인 뒤 data[3] 을 꺼냅니다. 방금 push 한 자리와 정확히 같은 자리입니다. 꺼낸 값은 배열에 그대로 남아 있지만, size 가 3이니 다음 push 가 덮어씁니다. 지울 필요가 없습니다.
out 이 NULL 이면 값을 돌려주지 않고 그냥 버립니다. “맨 위를 버려라”라고 쓰고 싶을 때 stack_pop(&s, NULL) 로 부를 수 있게 한 배려입니다. 6주차에서 배운 “포인터로 결과를 돌려주기”와 “NULL 검사”가 여기 함께 쓰였습니다.
peek 와 free
int stack_peek(const Stack *s, int *out) {
if (stack_is_empty(s)) return 0;
*out = s->data[s->size - 1];
return 1;
}
맨 위는 data[size - 1] 입니다. size 가 “다음 자리”니까 “지금 맨 위”는 그 바로 앞이죠. 매개변수가 const Stack * 인 것도 보세요. peek 는 스택을 바꾸지 않겠다는 약속입니다. 5주차에서 배운 대로, 이 약속을 어기고 안에서 s->size-- 를 쓰면 컴파일러가 오류를 냅니다.
void stack_free(Stack *s) {
free(s->data);
stack_init(s);
}
배열을 해제하고 세 칸을 초기 상태로 되돌립니다. 7주차에서 배운 “해제한 뒤 포인터를 NULL 로” 습관이 stack_init 안에 들어 있습니다.
메모리 그림으로 따라가기
main 의 첫 반복에서 10, 20, 30 을 push 할 때 구조체가 어떻게 바뀌는지 그려 봅시다.
stack_init 직후 push(10) 직후 push(20) 직후
┌──────────┐ ┌──────────┐ ┌──────────┐
│ data NULL│ │ data ●───┼──▶[10][ ][ ][ ] │ data ●───┼──▶[10][20][ ][ ]
│ size 0 │ │ size 1 │ 0 1 2 3 │ size 2 │ 0 1 2 3
│ cap 0 │ │ cap 4 │ │ cap 4 │
└──────────┘ └──────────┘ └──────────┘
↑ realloc 으로 4칸 확보 ↑ data[1] 에 쓰고 size 를 2로
push(30) 직후 pop() 직후 (30 을 돌려줌)
┌──────────┐ ┌──────────┐
│ data ●───┼──▶[10][20][30][ ] │ data ●───┼──▶[10][20][30][ ] ← 30 은 아직 배열에 남아 있다
│ size 3 │ 0 1 2 3 │ size 2 │ 0 1 2 3 하지만 size 가 2라 "없는 것"
│ cap 4 │ │ cap 4 │
└──────────┘ └──────────┘
마지막 그림이 중요합니다. pop 은 값을 지우지 않습니다. size 만 줄입니다. 배열 스택에서 “들어 있다”는 뜻은 “size 보다 작은 인덱스에 있다”는 뜻일 뿐입니다.
실행 결과 (stack_array)
$ ./build/stack_array
=== push: 접시 쌓기 ===
push(10): 바닥 [10] <- top
push(20): 바닥 [10 20] <- top
push(30): 바닥 [10 20 30] <- top
push(40): 바닥 [10 20 30 40] <- top
push(50): 바닥 [10 20 30 40 50] <- top
=== peek: 맨 위 확인 (꺼내지 않음) ===
top = 50 (size는 그대로 5)
=== pop: 역순으로 나온다 (LIFO) ===
pop() = 50, 남은 것: 바닥 [10 20 30 40] <- top
pop() = 40, 남은 것: 바닥 [10 20 30] <- top
pop() = 30, 남은 것: 바닥 [10 20] <- top
pop() = 20, 남은 것: 바닥 [10] <- top
pop() = 10, 남은 것: 바닥 [] <- top
빈 스택에서 pop 시도: 실패 (안전하게 거부)
배열 스택
넣은 순서는 10, 20, 30, 40, 50 인데 나온 순서는 50, 40, 30, 20, 10 입니다. 이것이 LIFO 입니다. while (stack_pop(&s, &value)) 는 “pop 이 성공하는 동안 반복”이라 스택이 비면 저절로 끝나고, 그다음 한 번 더 pop 을 시도하면 거부됩니다.
실험: 용량은 언제 늘어날까?
stack_print 는 size 만 보여 줘서 capacity 가 언제 바뀌는지는 안 보입니다. main 의 출력 문장에 두 값을 같이 찍도록 잠깐 고쳐서 돌려 봤습니다.
push(10) size=1 cap=4: 바닥 [10] <- top
push(20) size=2 cap=4: 바닥 [10 20] <- top
push(30) size=3 cap=4: 바닥 [10 20 30] <- top
push(40) size=4 cap=4: 바닥 [10 20 30 40] <- top
push(50) size=5 cap=8: 바닥 [10 20 30 40 50] <- top
첫 push 에서 0 → 4, 다섯 번째 push 에서 4 → 8 로 두 번만 늘어났습니다. 원소를 백만 개 넣어도 realloc 은 약 20번(2의 20제곱이 약 백만)이면 됩니다. 10주차 perf_compare 에서 본 “realloc 19번”이 바로 이 숫자였습니다.
실험: 빈 스택 검사를 빼면?
stack_pop 의 첫 줄 if (stack_is_empty(s)) return 0; 을 지우면 어떻게 될지 예상해 보세요. size 가 0인데 s->size-- 를 하면 size_t 라 음수가 못 되고 18446744073709551615 로 감아 돕니다. 그다음 s->data[18446744073709551615] 를 읽으니, 4주차에서 본 범위 밖 접근이고, 십중팔구 세그멘테이션 오류입니다. 이 검사 한 줄이 프로그램의 생사를 가릅니다. “pop 은 실패할 수 있다”는 사실을 반환값으로 알리고, 부르는 쪽이 반환값을 확인하는 것이 이번 주 내내 지킬 규칙입니다.
1.3 연결 리스트 기반 스택
같은 스택을 10주차의 연결 리스트로도 만들 수 있습니다. 리스트의 머리(head) 를 top 으로 삼으면, push_front 가 push 이고 pop_front 가 pop 입니다. examples/stack_list.c 입니다.
/*
* stack_list.c - 연결 리스트 기반 스택
* 11주차: 스택, 큐, 덱
*
* 10주차 단일 연결 리스트의 push_front/pop_front가 곧 스택입니다.
* 머리(top)에서만 넣고 빼므로 둘 다 O(1)입니다.
*
* 배열 기반과의 비교:
* - 배열: 캐시 친화적, 가끔 재할당, 메모리 낭비 적음 -> 보통 이쪽 추천
* - 리스트: 재할당 없음(일정한 성능), 노드마다 malloc + 포인터 오버헤드
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
typedef struct {
Node *top; /* 리스트의 머리 = 스택의 꼭대기 */
size_t size;
} Stack;
void stack_init(Stack *s) {
s->top = NULL;
s->size = 0;
}
int stack_is_empty(const Stack *s) {
return s->top == NULL;
}
/* push = 머리 삽입: O(1) */
int stack_push(Stack *s, int value) {
Node *node = malloc(sizeof(Node));
if (node == NULL) return 0;
node->data = value;
node->next = s->top; /* 새 노드가 기존 top을 밟고 올라선다 */
s->top = node;
s->size++;
return 1;
}
/* pop = 머리 삭제: O(1) */
int stack_pop(Stack *s, int *out) {
if (s->top == NULL) return 0;
Node *node = s->top;
if (out != NULL) *out = node->data;
s->top = node->next;
free(node);
s->size--;
return 1;
}
int stack_peek(const Stack *s, int *out) {
if (s->top == NULL) return 0;
*out = s->top->data;
return 1;
}
void stack_free(Stack *s) {
Node *cur = s->top;
while (cur != NULL) {
Node *next = cur->next; /* 10주차 규칙: 백업 먼저! */
free(cur);
cur = next;
}
stack_init(s);
}
void stack_print(const Stack *s) {
printf("top -> ");
for (Node *cur = s->top; cur != NULL; cur = cur->next) {
printf("[%d] -> ", cur->data);
}
printf("NULL\n");
}
int main(void) {
Stack s;
stack_init(&s);
printf("=== 연결 리스트 스택 ===\n");
for (int i = 1; i <= 5; i++) {
stack_push(&s, i * 10);
}
stack_print(&s); /* 50이 top (마지막에 넣은 것) */
printf("size = %zu\n", s.size);
printf("\n=== pop 두 번 ===\n");
int value;
stack_pop(&s, &value);
printf("pop() = %d\n", value);
stack_pop(&s, &value);
printf("pop() = %d\n", value);
stack_print(&s);
printf("\n=== 중간에 해제해도 누수 없음 ===\n");
stack_free(&s); /* 남은 노드 전부 해제 */
stack_print(&s);
printf("valgrind --leak-check=full 로 확인해 보세요\n");
return 0;
}
push 두 줄의 순서
node->next = s->top; /* 새 노드가 기존 top을 밟고 올라선다 */
s->top = node;
새 노드를 만들어 기존 top 을 가리키게 한 뒤, 그 노드를 새 top 으로 삼습니다. 그림으로 보면 이렇습니다.
push(30) 전: top ──▶ [20] ──▶ [10] ──▶ NULL
① node 를 만든다: [30] ──▶ ?
② node->next = s->top [30] ──▶ [20] ──▶ [10] ──▶ NULL (top 은 아직 [20])
③ s->top = node top ──▶ [30] ──▶ [20] ──▶ [10] ──▶ NULL
이 두 줄의 순서를 바꾸면 무슨 일이 생길까요? 직접 바꿔서 돌려 봤습니다.
s->top = node; /* 순서를 바꿔 봄 */
node->next = s->top; /* 이제 s->top 은 node 자신! */
$ ./sl_bug | head -c 200
=== 연결 리스트 스택 ===
top -> [50] -> [50] -> [50] -> [50] -> [50] -> [50] -> [50] -> [50] -> [50] -> [50] -> ...
프로그램이 영원히 [50] 을 찍습니다. s->top 을 먼저 node 로 바꿔 버리니, 다음 줄의 node->next = s->top 은 자기 자신을 가리키게 됩니다. 노드가 자기 꼬리를 문 고리가 되어 stack_print 의 반복문이 끝나지 않습니다(Ctrl + C 로 멈춰야 합니다). 기존 리스트 [40] → [30] → … 는 아무도 가리키지 않게 되어 통째로 누수됩니다. “새 노드가 먼저 기존 것을 붙잡고, 그다음에 머리를 옮긴다.” 10주차 push_front 에서도 같은 순서였습니다.
실행 결과 (stack_list)
$ ./build/stack_list
=== 연결 리스트 스택 ===
top -> [50] -> [40] -> [30] -> [20] -> [10] -> NULL
size = 5
=== pop 두 번 ===
pop() = 50
pop() = 40
top -> [30] -> [20] -> [10] -> NULL
=== 중간에 해제해도 누수 없음 ===
top -> NULL
valgrind --leak-check=full 로 확인해 보세요
출력이 권하는 대로 7주차의 Valgrind 로 확인해 봅시다.
$ valgrind --leak-check=full ./build/stack_list
...
==313110== HEAP SUMMARY:
==313110== in use at exit: 0 bytes in 0 blocks
==313110== total heap usage: 6 allocs, 6 frees, 4,176 bytes allocated
==313110== All heap blocks were freed -- no leaks are possible
==313110== ERROR SUMMARY: 0 errors from 0 contexts (suppressed: 0 from 0)
6 allocs, 6 frees 입니다. 노드 5개를 malloc 했고(나머지 하나는 printf 가 내부에서 쓴 버퍼입니다), pop 두 번과 stack_free 로 5개를 전부 free 했습니다. 7주차에서 배운 “할당 횟수와 해제 횟수가 같은지”를 보는 습관입니다.
배열이냐 리스트냐
| 배열 기반 | 리스트 기반 | |
|---|---|---|
| push/pop | 분할 상환 O(1). 가끔 realloc 으로 한 번 느림 |
항상 O(1). 대신 매번 malloc |
| 메모리 | 원소 4바이트씩 빽빽이. 여유 칸이 조금 남음 | 원소마다 노드 16바이트(값 4 + 포인터 8 + 패딩 4, 8주차) |
| 캐시 | 연속 메모리라 빠름 (10주차 측정) | 노드가 흩어져 있어 불리 |
| 크기 제한 | realloc 이 실패할 때까지 |
malloc 이 실패할 때까지 |
| 추천 | 대부분의 경우 | 재할당으로 잠깐 멈추는 것조차 허용 못 하는 특수한 경우 |
노드 크기를 실제로 재 보면 이렇습니다.
$ ./sz
sizeof(Node)=16, sizeof(int)=4
값 4바이트를 담으려고 16바이트를 씁니다. 8주차의 패딩 때문에 12가 아니라 16입니다. 원소가 백만 개면 배열 스택은 4MB, 리스트 스택은 16MB 에 malloc 이 덧붙이는 관리 정보까지 더해 그 이상입니다. 10주차 성능 측정의 결론(“일단 배열”)이 스택에도 그대로 적용됩니다.
그럼 리스트 스택은 왜 배울까요? 이번 주 프로젝트 3(브라우저 히스토리)처럼 원소가 문자열이라 크기가 제각각이거나, 뒤에 나올 연결 리스트 큐처럼 양 끝을 다 다뤄야 할 때 리스트가 자연스럽기 때문입니다.
1.4 응용: 괄호 짝 검사
스택의 가장 유명한 응용입니다. 들어가며에서 던진 질문, “컴파일러는 괄호 짝을 어떻게 검사할까”의 답이기도 합니다.
먼저 생각해 봅시다. ({[]}) 는 짝이 맞고 (] 는 안 맞습니다. 사람은 어떻게 판단할까요? 닫는 괄호를 만났을 때 “가장 최근에 열린 괄호” 와 종류가 같은지 봅니다. (] 에서 ] 를 만났을 때 가장 최근에 열린 것은 ( 이니 틀렸습니다. “가장 최근에 열린 것”을 기억하고 있다가 꺼내는 것, 이게 정확히 스택의 pop 입니다.
규칙은 세 줄입니다.
- 여는 괄호를 만나면 push
- 닫는 괄호를 만나면 pop 해서, 종류가 맞는지 확인. pop 할 것이 없거나 종류가 다르면 실패
- 끝까지 읽었을 때 스택이 비어 있어야 성공. 남아 있으면 닫히지 않은 괄호가 있는 것
examples/bracket_check.c 입니다.
/*
* bracket_check.c - 괄호 짝 검사 (스택의 대표 응용)
* 11주차: 스택, 큐, 덱
*
* 컴파일러가 여러분의 코드에서 { } ( ) [ ] 짝을 검사하는 원리입니다.
*
* 알고리즘:
* - 여는 괄호를 만나면 push
* - 닫는 괄호를 만나면 pop해서 짝이 맞는지 확인
* - 다 읽었을 때 스택이 비어 있어야 성공
*/
#include <stdio.h>
#include <string.h>
#define MAX_DEPTH 128
/* 이 예제는 char 스택이 필요하므로 간단한 고정 배열 스택을 사용 */
typedef struct {
char data[MAX_DEPTH];
int top; /* 비었을 때 -1 */
} CharStack;
void cs_init(CharStack *s) { s->top = -1; }
int cs_is_empty(const CharStack *s){ return s->top < 0; }
int cs_push(CharStack *s, char c) {
if (s->top + 1 >= MAX_DEPTH) return 0; /* 너무 깊음 */
s->data[++s->top] = c;
return 1;
}
int cs_pop(CharStack *s, char *out) {
if (cs_is_empty(s)) return 0;
*out = s->data[s->top--];
return 1;
}
/* 닫는 괄호에 대응하는 여는 괄호 */
char matching_open(char close) {
switch (close) {
case ')': return '(';
case ']': return '[';
case '}': return '{';
default: return '\0';
}
}
/* 괄호 검사: 성공하면 -1, 실패하면 문제가 생긴 위치(0부터 세는 인덱스) 반환 */
int check_brackets(const char *text) {
CharStack s;
cs_init(&s);
for (int i = 0; text[i] != '\0'; i++) {
char c = text[i];
if (c == '(' || c == '[' || c == '{') {
if (!cs_push(&s, c)) return i; /* 스택 넘침 */
} else if (c == ')' || c == ']' || c == '}') {
char open;
if (!cs_pop(&s, &open)) {
return i; /* 닫는 괄호가 남아돈다 */
}
if (open != matching_open(c)) {
return i; /* 종류가 안 맞는다 */
}
}
/* 괄호가 아닌 문자는 무시 */
}
if (!cs_is_empty(&s)) {
return (int)strlen(text); /* 여는 괄호가 남았다 */
}
return -1; /* 성공 */
}
void test(const char *text) {
int pos = check_brackets(text);
if (pos < 0) {
printf(" [OK] %s\n", text);
} else {
printf(" [XX] %s\n", text);
printf(" %*s^-- %d번째 글자에서 문제 발견\n", pos, "", pos + 1);
}
}
int main(void) {
printf("=== 괄호 짝 검사 ===\n\n");
printf("올바른 경우:\n");
test("()");
test("({[]})");
test("int main(void) { int a[3] = {1, 2, 3}; }");
test("no brackets at all");
printf("\n잘못된 경우:\n");
test("(]"); /* 종류 불일치 */
test("((())"); /* 여는 괄호 남음 */
test("())"); /* 닫는 괄호 남음 */
test("if (x > 0) { printf(\"hi\"); ]"); /* } 대신 ] */
printf("\n원리: 가장 최근에 열린 괄호가 가장 먼저 닫혀야 한다 = LIFO = 스택\n");
return 0;
}
이번에는 다른 모양의 스택
앞의 두 스택과 달리 이 CharStack 은 고정 크기 배열이고, top 이 -1 에서 시작하는 int 입니다. 스택을 만드는 방법이 한 가지가 아니라는 것을 보여 주려고 일부러 다르게 만들었습니다. 두 방식을 나란히 놓으면 이렇습니다.
stack_array.c |
bracket_check.c |
|
|---|---|---|
| top 의 뜻 | size = 다음 자리 (빈 스택이면 0) |
top = 맨 위 원소의 인덱스 (빈 스택이면 -1) |
| push | data[size++] = c |
data[++top] = c |
| pop | size--; return data[size] |
return data[top--] |
| 비었나 | size == 0 |
top < 0 |
++top 과 top-- 의 차이를 3주차 연산자 절과 함께 다시 보세요. push 는 먼저 올리고(전위) 그 자리에 쓰고, pop 은 그 자리를 읽고 나중에 내립니다(후위). top 을 -1 에서 시작해야 첫 push 가 data[0] 에 들어갑니다. top 이 int 인 이유도 여기 있습니다. -1 을 담아야 하니 size_t 는 못 씁니다.
손으로 추적하기
({[]}) 를 한 글자씩 따라가 봅시다. 스택은 왼쪽이 바닥입니다.
| i | 글자 | 동작 | 스택 (바닥 → top) |
|---|---|---|---|
| 0 | ( |
push | ( |
| 1 | { |
push | ( { |
| 2 | [ |
push | ( { [ |
| 3 | ] |
pop → [, matching_open(']') = [, 일치 |
( { |
| 4 | } |
pop → {, 일치 |
( |
| 5 | ) |
pop → (, 일치 |
(비었음) |
| 끝 | 스택이 비었으니 성공 |
이번에는 ((()) 입니다.
| i | 글자 | 동작 | 스택 |
|---|---|---|---|
| 0~2 | ((( |
push 세 번 | ( ( ( |
| 3 | ) |
pop, 일치 | ( ( |
| 4 | ) |
pop, 일치 | ( |
| 끝 | 스택에 ( 가 남았다 → strlen 인 5 를 반환 |
strlen(text) 를 돌려주는 이유는 “문제가 있는 자리”가 문자열의 끝이기 때문입니다. 닫는 괄호가 있어야 할 자리가 거기니까요.
실행 결과 (bracket_check)
$ ./build/bracket_check
=== 괄호 짝 검사 ===
올바른 경우:
[OK] ()
[OK] ({[]})
[OK] int main(void) { int a[3] = {1, 2, 3}; }
[OK] no brackets at all
잘못된 경우:
[XX] (]
^-- 2번째 글자에서 문제 발견
[XX] ((())
^-- 6번째 글자에서 문제 발견
[XX] ())
^-- 3번째 글자에서 문제 발견
[XX] if (x > 0) { printf("hi"); ]
^-- 28번째 글자에서 문제 발견
원리: 가장 최근에 열린 괄호가 가장 먼저 닫혀야 한다 = LIFO = 스택
괄호 검사
^ 가 정확히 문제의 글자 아래에 찍힙니다. printf("%*s", pos, "") 는 2주차에서 본 폭 지정으로, 빈 문자열을 pos 칸 폭으로 찍어서 공백을 pos 개 만드는 요령입니다. 1주차 10절에서 GCC 가 오류 위치에 ^ 를 그려 주던 것과 같은 방법입니다.
세 번째 줄의 진짜 C 코드도 통과합니다. 괄호가 아닌 글자는 무시하니까요. 그리고 마지막 줄은 } 대신 ] 를 썼는데, 28번째 글자에서 “종류가 안 맞는다”고 정확히 잡아냅니다.
실험: 스택이 넘치면?
MAX_DEPTH 가 128 이니 여는 괄호를 129개 넣으면 어떻게 될까요? cs_push 의 if (s->top + 1 >= MAX_DEPTH) return 0; 이 막습니다. 같은 스택으로 확인해 봤습니다.
$ ./deep
129번째 push에서 거부 (top=127)
128개까지는 들어가고(top 이 0 부터 127), 129번째에서 거부합니다. check_brackets 는 이때 return i 로 “여기서 문제”라고 답합니다. 실제 컴파일러는 이보다 훨씬 깊은 중첩도 받아 주지만, 원리는 같습니다. 128 이라는 한도가 없다면 data[128] 부터 배열 밖에 쓰게 되고, 4주차에서 본 스택 스매싱이 일어납니다.
이 문제가 왜 큐로는 안 될까?
([)]를 생각해 보세요. 여는 괄호(,[두 개와 닫는 괄호),]두 개로 개수는 맞습니다. 하지만)를 만났을 때 가장 최근에 열린 것은[라서 틀렸습니다. 큐(먼저 넣은 것부터)로 검사하면(가 나와서 맞다고 착각합니다. “가장 최근”을 꺼내야 하는 문제는 스택이고, “가장 오래된”을 꺼내야 하는 문제는 큐입니다. 자료구조를 고르는 기준은 늘 이것입니다.
1.5 함수 호출 스택: 여러분은 매일 스택을 쓰고 있습니다
5주차에서 재귀를 배울 때 “함수를 부르면 스택 프레임이 쌓인다”는 말을 들었습니다. 그때는 그림으로만 봤는데, 이제 스택을 직접 만들었으니 그 스택이 바로 이 스택이라는 것을 확인할 수 있습니다.
함수를 호출하면 CPU 는 스택 프레임(그 함수의 지역 변수, 매개변수, 그리고 끝나면 돌아갈 주소)을 스택에 push 합니다. return 하면 pop 합니다. 재귀 함수는 자기 자신을 부르니 프레임이 층층이 쌓였다가, 바닥에 닿으면 하나씩 걷힙니다. examples/call_stack_sim.c 는 이 과정을 두 가지 방법으로 보여 줍니다.
/*
* call_stack_sim.c - 함수 호출 스택 시뮬레이션
* 11주차: 스택, 큐, 덱
*
* 함수를 호출하면 컴퓨터는 "스택 프레임"(지역 변수 + 돌아갈 위치)을
* 스택에 쌓고, return하면 걷어냅니다. 재귀가 동작하는 원리이자,
* 재귀가 너무 깊으면 스택 오버플로우가 나는 이유입니다.
*
* 여기서는 factorial(4)의 재귀 호출을
* 1) 실제 재귀로 추적하고
* 2) 명시적 스택으로 똑같이 재현합니다.
* "모든 재귀는 스택을 쓰는 반복문으로 바꿀 수 있다"를 눈으로 확인하세요.
*/
#include <stdio.h>
static int depth = 0; /* 현재 호출 깊이 (들여쓰기용) */
void indent(void) {
for (int i = 0; i < depth; i++) printf(" ");
}
/* 1. 실제 재귀: 호출/복귀 과정을 출력으로 추적 */
long factorial_recursive(int n) {
indent(); printf("-> factorial(%d) 호출 (프레임 push)\n", n);
depth++;
long result;
if (n <= 1) {
result = 1;
} else {
result = n * factorial_recursive(n - 1);
}
depth--;
indent(); printf("<- factorial(%d) = %ld 반환 (프레임 pop)\n", n, result);
return result;
}
/* 2. 명시적 스택으로 같은 계산 재현 */
#define MAX_FRAMES 64
typedef struct {
int n; /* 이 프레임의 인자 */
} Frame;
long factorial_iterative(int n) {
Frame stack[MAX_FRAMES];
int top = -1;
/* 호출 단계: factorial(n), factorial(n-1), ... factorial(1)을 차례로 push
* (재귀가 바닥까지 내려가는 과정과 동일) */
printf("[호출 단계] ");
for (int i = n; i >= 1; i--) {
stack[++top] = (Frame){ .n = i };
printf("push(%d) ", i);
}
printf("\n");
/* 복귀 단계: 위에서부터 pop하며 결과를 누적
* (재귀가 return하며 올라오는 과정과 동일) */
long result = 1;
printf("[복귀 단계] ");
while (top >= 0) {
Frame f = stack[top--];
result *= f.n;
printf("pop(%d)->%ld ", f.n, result);
}
printf("\n");
return result;
}
int main(void) {
printf("=== 1. 실제 재귀 호출 추적: factorial(4) ===\n");
long r1 = factorial_recursive(4);
printf("결과: %ld\n", r1);
printf("\n=== 2. 명시적 스택으로 재현 ===\n");
long r2 = factorial_iterative(4);
printf("결과: %ld\n", r2);
printf("\n=== 스택 오버플로우는 왜 생기나 ===\n");
printf("프레임 하나가 수십~수백 바이트인데 스택 전체는 보통 8MB.\n");
printf("종료 조건 없는 재귀 -> 프레임이 무한히 쌓임 -> 한도 초과 -> 크래시!\n");
printf("(ulimit -s 명령으로 내 시스템의 스택 한도를 확인해 보세요)\n");
return 0;
}
(Frame){ .n = i } 는 복합 리터럴(compound literal) 이라는 C99 문법으로, 구조체 값을 변수 없이 그 자리에서 만드는 방법입니다. .n = i 는 8주차의 지정 초기화와 같은 꼴입니다. static int depth 는 파일 안에서만 보이는 전역 변수(5주차)로, 들여쓰기 깊이를 셉니다.
실행 결과 (call_stack_sim)
$ ./build/call_stack_sim
=== 1. 실제 재귀 호출 추적: factorial(4) ===
-> factorial(4) 호출 (프레임 push)
-> factorial(3) 호출 (프레임 push)
-> factorial(2) 호출 (프레임 push)
-> factorial(1) 호출 (프레임 push)
<- factorial(1) = 1 반환 (프레임 pop)
<- factorial(2) = 2 반환 (프레임 pop)
<- factorial(3) = 6 반환 (프레임 pop)
<- factorial(4) = 24 반환 (프레임 pop)
결과: 24
=== 2. 명시적 스택으로 재현 ===
[호출 단계] push(4) push(3) push(2) push(1)
[복귀 단계] pop(1)->1 pop(2)->2 pop(3)->6 pop(4)->24
결과: 24
=== 스택 오버플로우는 왜 생기나 ===
프레임 하나가 수십~수백 바이트인데 스택 전체는 보통 8MB.
종료 조건 없는 재귀 -> 프레임이 무한히 쌓임 -> 한도 초과 -> 크래시!
(ulimit -s 명령으로 내 시스템의 스택 한도를 확인해 보세요)
1번의 들여쓰기가 곧 스택의 높이입니다. factorial(4) 가 factorial(3) 을 부르고, 그것이 factorial(2) 를 부르고… 가장 깊은 factorial(1) 이 가장 먼저 반환됩니다. 가장 나중에 push 된 프레임이 가장 먼저 pop 됩니다. LIFO 입니다.
2번은 같은 계산을 재귀 없이 합니다. 4, 3, 2, 1 을 push 하는 것이 “재귀가 바닥까지 내려가는 과정”이고, 1, 2, 3, 4 를 pop 하며 곱하는 것이 “return 하며 올라오는 과정”입니다. 결과가 같은 24 입니다. 이것이 증명하는 사실은 중요합니다. 모든 재귀는 명시적 스택과 반복문으로 바꿀 수 있습니다. 다음 주 트리 순회에서 이 기법을 실제로 씁니다.
실험: 스택 오버플로를 직접 내 보기
출력이 권하는 대로 스택 한도를 확인해 봅시다.
$ ulimit -s
8192
단위는 KB 라서 8MB 입니다. 그러면 종료 조건이 없는 재귀는 어떻게 될까요? 5주차에서 한 번 봤지만, 이번에는 깊이를 세면서 죽여 봅니다.
static long depth = 0;
void down(void) {
depth++;
if (depth % 100000 == 0) { printf("depth %ld\n", depth); fflush(stdout); }
down();
}
int main(void) { down(); return 0; }
$ gcc -Wall -Wextra -std=c11 inf.c -o inf
inf.c:3:6: warning: infinite recursion detected [-Winfinite-recursion]
$ ./inf | tail -2
depth 400000
depth 500000
$ echo $?
139
GCC 13 은 컴파일할 때부터 “무한 재귀”라고 경고합니다. 실행하면 50만 번 넘게 쌓이다가 종료 코드 139, 세그멘테이션 오류로 죽습니다. 8MB 를 약 52만 프레임으로 나누면 프레임 하나가 16바이트쯤입니다. 이 함수는 지역 변수가 없어서 돌아갈 주소(8바이트)와 프레임 포인터(8바이트)만 쌓이기 때문입니다. 지역 변수가 많은 함수라면 프레임이 커져서 훨씬 적은 횟수에 죽습니다.
fflush(stdout) 을 넣은 이유는 9주차에서 배운 버퍼링 때문입니다. 프로그램이 죽으면 버퍼에 남은 출력이 사라지므로, 죽기 전에 강제로 내보내야 마지막 depth 를 볼 수 있습니다.
2. 큐 (Queue) — 먼저 온 것이 먼저
2.1 FIFO: 줄 서기
은행 창구의 대기줄입니다. 새로 온 사람은 뒤에 서고, 창구는 앞 사람부터 부릅니다. 먼저 온 사람이 먼저 나갑니다. FIFO(First In, First Out) 입니다. 스택이 “한쪽 끝에서 넣고 같은 끝에서 빼기”라면, 큐는 “한쪽 끝에서 넣고 반대쪽 끝에서 빼기”입니다.
| 연산 | 뜻 | 하는 일 | 시간 |
|---|---|---|---|
| enqueue (줄에 넣다) | 뒤에 붙이기 | 새 원소를 rear 뒤에 붙인다 | O(1) |
| dequeue (줄에서 빼다) | 앞에서 꺼내기 | front 원소를 빼서 돌려주고, 그다음이 새 front 가 된다 | O(1) |
| peek | 꺼내지 않고 앞 보기 | front 원소의 값만 알려 준다 | O(1) |
front 는 줄의 맨 앞(다음에 나갈 사람), rear 는 맨 뒤(가장 최근에 온 사람)입니다. 스택은 top 하나만 기억하면 됐는데, 큐는 양쪽 끝을 다 기억해야 하니 조금 더 손이 갑니다. 그리고 여기서 배열 기반 구현에 함정이 하나 생깁니다.
2.2 원형 배열 큐: % 연산의 마법
문제: 앞에서 빼면 앞칸이 낭비된다
배열로 큐를 만든다고 합시다. enqueue 는 스택의 push 처럼 뒤에 붙이면 됩니다. 문제는 dequeue 입니다. 앞에서 빼야 하는데, 배열의 앞칸을 비우면 어떻게 될까요?
enqueue 10, 20, 30, 40, 50 (용량 5):
[10][20][30][40][50]
↑ front ↑ rear
dequeue 세 번 (10, 20, 30 이 나감):
[ ][ ][ ][40][50]
↑ front ↑ rear
앞 세 칸이 비었는데 rear 는 배열 끝에 닿았습니다. 이제 60 을 넣으려면? 방법 1은 전체를 앞으로 당기는 것입니다. 원소가 n 개면 n 번 옮겨야 하니 O(n) 이고, 큐가 크면 dequeue 할 때마다 큰 비용이 듭니다. 방법 2는 그냥 “가득 찼다”고 거부하는 것인데, 앞이 텅텅 비어 있는데 거부하는 건 말이 안 됩니다.
해결: 배열을 둥글게 쓴다
세 번째 방법이 원형 배열(circular array) 입니다. rear 가 배열 끝에 닿으면 처음으로 돌아가서 빈 앞칸을 다시 씁니다. 배열을 직선이 아니라 시계처럼 둥글게 보는 것입니다. 인덱스 4 다음은 5가 아니라 0 입니다.
[0]
[4] [1] ← 인덱스 4 다음에 0 으로 감아 돈다
[3] [2]
“4 다음에 0” 을 계산하는 연산이 3주차에서 배운 나머지 연산 % 입니다. (4 + 1) % 5 = 0, (2 + 1) % 5 = 3. 인덱스에 1 을 더한 뒤 용량으로 나눈 나머지를 취하면, 끝에 닿았을 때만 0 으로 돌아가고 나머지는 그대로입니다. 이것을 감아 돌기(wrap-around) 라고 합니다.
examples/queue_circular.c 입니다. 용량을 일부러 5 로 작게 잡아서 감아 도는 순간을 볼 수 있게 했습니다.
/*
* queue_circular.c - 원형 배열 기반 큐
* 11주차: 스택, 큐, 덱
*
* 큐(Queue)는 "먼저 넣은 것이 먼저 나오는" FIFO 구조입니다.
* (First In, First Out - 줄 서기를 떠올리세요)
*
* 배열로 큐를 만들 때의 함정: 앞에서 빼면 빈칸이 생기는데,
* 매번 전체를 당기면 O(n)입니다. 해결책이 "원형 배열"입니다.
* front와 rear 인덱스가 배열 끝에 닿으면 처음으로 감아 돕니다(wrap).
*/
#include <stdio.h>
#define CAPACITY 5 /* 일부러 작게: 감아 도는 것을 관찰하기 위해 */
typedef struct {
int data[CAPACITY];
int front; /* 다음에 나갈 원소의 위치 */
int count; /* 현재 원소 개수 (가득참/빈 것 구분용) */
} Queue;
void queue_init(Queue *q) {
q->front = 0;
q->count = 0;
}
int queue_is_empty(const Queue *q) { return q->count == 0; }
int queue_is_full(const Queue *q) { return q->count == CAPACITY; }
/* rear(다음에 넣을 위치)는 front와 count로 계산 */
static int rear_index(const Queue *q) {
return (q->front + q->count) % CAPACITY; /* %가 감아 도는 핵심! */
}
int enqueue(Queue *q, int value) {
if (queue_is_full(q)) return 0;
q->data[rear_index(q)] = value;
q->count++;
return 1;
}
int dequeue(Queue *q, int *out) {
if (queue_is_empty(q)) return 0;
if (out != NULL) *out = q->data[q->front];
q->front = (q->front + 1) % CAPACITY; /* front도 감아 돈다 */
q->count--;
return 1;
}
/* 내부 배열의 실제 모습을 보여준다 (학습용) */
void queue_show_internal(const Queue *q) {
printf(" 내부: [");
for (int i = 0; i < CAPACITY; i++) {
/* i가 사용 중인 칸인지 판단 */
int used = 0;
for (int k = 0; k < q->count; k++) {
if ((q->front + k) % CAPACITY == i) { used = 1; break; }
}
if (used) printf("%2d", q->data[i]);
else printf(" .");
if (i + 1 < CAPACITY) printf(" ");
}
printf("] front=%d, count=%d\n", q->front, q->count);
}
int main(void) {
Queue q;
queue_init(&q);
int value;
printf("=== enqueue: 줄 서기 (용량 %d) ===\n", CAPACITY);
for (int i = 1; i <= 5; i++) {
enqueue(&q, i * 10);
printf("enqueue(%2d)\n", i * 10);
queue_show_internal(&q);
}
printf("\n가득 찬 상태에서 enqueue: %s\n",
enqueue(&q, 99) ? "성공" : "실패 (안전하게 거부)");
printf("\n=== dequeue 3번: 앞에서부터 나간다 (FIFO) ===\n");
for (int i = 0; i < 3; i++) {
dequeue(&q, &value);
printf("dequeue() = %2d\n", value);
queue_show_internal(&q);
}
printf("\n=== 다시 enqueue: 빈 앞칸을 재사용하며 감아 돈다! ===\n");
enqueue(&q, 60);
queue_show_internal(&q);
enqueue(&q, 70);
queue_show_internal(&q); /* 인덱스 0, 1로 wrap된 것 확인 */
printf("\n=== 전부 비우기 ===\n");
while (dequeue(&q, &value)) {
printf("dequeue() = %2d\n", value);
}
printf("빈 큐에서 dequeue: %s\n",
dequeue(&q, &value) ? "성공" : "실패 (안전하게 거부)");
printf("\n핵심: %% 연산 하나로 '무한히 도는 벨트'가 된다. 당기기(O(n)) 불필요!\n");
return 0;
}
구조체: front 와 count, rear 는 계산한다
typedef struct {
int data[CAPACITY];
int front; /* 다음에 나갈 원소의 위치 */
int count; /* 현재 원소 개수 (가득참/빈 것 구분용) */
} Queue;
교과서에는 보통 front 와 rear 두 인덱스를 저장합니다. 이 예제는 front 와 count 를 저장하고, rear 는 필요할 때 계산합니다.
static int rear_index(const Queue *q) {
return (q->front + q->count) % CAPACITY; /* %가 감아 도는 핵심! */
}
“다음에 넣을 자리”는 front 에서 count 칸 뒤입니다. front 가 3 이고 원소가 3 개면 3, 4, 0 을 쓰고 있으니 다음 자리는 (3 + 3) % 5 = 1 입니다. 왜 rear 대신 count 를 저장하는지는 잠시 뒤 “가득 참과 빈 것”에서 설명합니다.
enqueue 와 dequeue 한 줄씩
int enqueue(Queue *q, int value) {
if (queue_is_full(q)) return 0; /* count == CAPACITY 면 거부 */
q->data[rear_index(q)] = value; /* 계산한 rear 자리에 쓰고 */
q->count++; /* 개수를 늘린다 */
return 1;
}
스택의 push 와 거의 같습니다. 다른 점은 “다음 자리”가 size 가 아니라 (front + count) % CAPACITY 라는 것뿐입니다.
int dequeue(Queue *q, int *out) {
if (queue_is_empty(q)) return 0; /* count == 0 이면 거부 */
if (out != NULL) *out = q->data[q->front]; /* 맨 앞을 꺼내고 */
q->front = (q->front + 1) % CAPACITY; /* front 를 한 칸 뒤로 (감아 돌며) */
q->count--;
return 1;
}
스택의 pop 과 다른 점이 여기 있습니다. 스택은 size 만 줄이면 됐는데, 큐는 front 가 한 칸 앞으로 이동해야 합니다. 그리고 front 가 배열 끝(4)에 있었다면 (4 + 1) % 5 = 0 으로 처음으로 돌아갑니다.
인덱스를 표로 추적하기
main 의 동작을 front, count, rear 로 따라가 봅시다. rear 는 저장되지 않지만 (front + count) % 5 로 매번 계산됩니다.
| 동작 | front | count | rear = (front+count)%5 | 배열 [0][1][2][3][4] |
|---|---|---|---|---|
| 초기 | 0 | 0 | 0 | . . . . . |
| enqueue 10 | 0 | 1 | 1 | 10 . . . . |
| enqueue 20 | 0 | 2 | 2 | 10 20 . . . |
| enqueue 30, 40, 50 | 0 | 5 | 0 ← (0+5)%5 | 10 20 30 40 50 |
| enqueue 99 | count == 5 라 거부 | |||
| dequeue → 10 | 1 | 4 | 0 | . 20 30 40 50 |
| dequeue → 20 | 2 | 3 | 0 | . . 30 40 50 |
| dequeue → 30 | 3 | 2 | 0 | . . . 40 50 |
| enqueue 60 | 3 | 3 | 1 | 60 . . 40 50 ← 인덱스 0 에 들어갔다 |
| enqueue 70 | 3 | 4 | 2 | 60 70 . 40 50 |
| dequeue → 40 | 4 | 3 | 2 | 60 70 . . 50 |
| dequeue → 50 | 0 ← (4+1)%5 | 2 | 2 | 60 70 . . . |
| dequeue → 60 | 1 | 1 | 2 | . 70 . . . |
| dequeue → 70 | 2 | 0 | 2 | . . . . . |
“enqueue 60” 줄을 보세요. 배열의 끝(인덱스 4)이 차 있는데도 60 이 인덱스 0 에 들어갔습니다. 앞에서 빠져나간 빈칸을 재사용한 것입니다. 그리고 “dequeue → 50” 에서 front 가 4 에서 0 으로 감아 돕니다. 논리적인 순서는 40 → 50 → 60 → 70 이지만, 물리적 배치는 [60 70 . 40 50] 으로 감겨 있습니다. 큐를 쓰는 쪽은 이 감김을 전혀 모릅니다. dequeue 가 순서대로 40, 50, 60, 70 을 돌려주니까요.
실행 결과 (queue_circular)
$ ./build/queue_circular
=== enqueue: 줄 서기 (용량 5) ===
enqueue(10)
내부: [10 . . . .] front=0, count=1
enqueue(20)
내부: [10 20 . . .] front=0, count=2
enqueue(30)
내부: [10 20 30 . .] front=0, count=3
enqueue(40)
내부: [10 20 30 40 .] front=0, count=4
enqueue(50)
내부: [10 20 30 40 50] front=0, count=5
가득 찬 상태에서 enqueue: 실패 (안전하게 거부)
=== dequeue 3번: 앞에서부터 나간다 (FIFO) ===
dequeue() = 10
내부: [ . 20 30 40 50] front=1, count=4
dequeue() = 20
내부: [ . . 30 40 50] front=2, count=3
dequeue() = 30
내부: [ . . . 40 50] front=3, count=2
=== 다시 enqueue: 빈 앞칸을 재사용하며 감아 돈다! ===
내부: [60 . . 40 50] front=3, count=3
내부: [60 70 . 40 50] front=3, count=4
=== 전부 비우기 ===
dequeue() = 40
dequeue() = 50
dequeue() = 60
dequeue() = 70
빈 큐에서 dequeue: 실패 (안전하게 거부)
핵심: % 연산 하나로 '무한히 도는 벨트'가 된다. 당기기(O(n)) 불필요!
원형 큐
표로 추적한 것과 정확히 같습니다. queue_show_internal 이 사용 중인 칸만 숫자로, 빈칸은 . 으로 그려 주는 덕분에 감김이 눈에 보입니다.
실험: % 를 빼면 무슨 일이 생길까?
“감아 도는 핵심”이라는 % 를 rear_index 에서 빼 봤습니다.
static int rear_index(const Queue *q) {
return (q->front + q->count); /* % CAPACITY 를 뺌 */
}
$ ./qc_bug
...
=== 다시 enqueue: 빈 앞칸을 재사용하며 감아 돈다! ===
내부: [10 20 30 . .] front=60, count=3
내부: [10 20 30 40 .] front=60, count=4
=== 전부 비우기 ===
dequeue() = 0
dequeue() = 20
dequeue() = 30
dequeue() = 40
이상한 것이 두 가지 보입니다. front=60 이 됐고, dequeue 로 0 이 나왔습니다. 무슨 일일까요?
60 을 넣을 때 front 는 3, count 는 2 였으니(dequeue 를 세 번 했으니 5 − 3 = 2) % 가 없으면 rear 는 3 + 2 = 5 입니다. data[5] 는 5칸짜리 배열의 밖입니다. 8주차에서 배운 구조체의 메모리 배치를 떠올리면, data[0..4] 바로 뒤에는 front 가 있고 그다음이 count 입니다.
Queue 의 메모리: [data[0]][data[1]][data[2]][data[3]][data[4]][ front ][ count ]
0바이트 20바이트 24바이트
↑ data[5] 자리 ↑ data[6] 자리
data[5] 에 60 을 쓴다는 것은 front 에 60 을 쓴다는 뜻입니다. 그래서 front=60 이 됐습니다. 그다음 70 을 넣을 때는 rear 가 60 + 3 = 63 이라 구조체를 한참 벗어난 곳에 씁니다. 나중에 dequeue 가 data[60] 을 읽으니 쓰레기(여기서는 0)가 나왔고, 60 과 70 은 영영 못 찾습니다. 범위 밖에 쓴 값이 옆 멤버를 덮어쓴 것입니다.
더 무서운 점은 이 실험을 -fsanitize=address 로 돌렸는데도 AddressSanitizer 가 잡지 못했다는 것입니다. 4주차에서 배열 범위 초과를 잡아 주던 그 도구가요. data[5] 는 구조체 안에서 배열을 넘어 옆 멤버로 넘친 것이라, 구조체 전체로 보면 “멀쩡히 할당된 메모리 안”이기 때문입니다. 도구가 못 잡는 버그는 사람이 막아야 합니다. 원형 버퍼의 인덱스 계산에는 반드시 % CAPACITY 를 붙이세요.
가득 참과 빈 것을 어떻게 구분하나
앞에서 미뤄 둔 질문입니다. 교과서처럼 front 와 rear 두 인덱스를 저장하면, 원소가 하나도 없을 때와 가득 찼을 때가 똑같이 보입니다.
빈 큐: front=2, rear=2 [ . . . . . ]
가득 찬 큐: front=2, rear=2 [40 50 10 20 30] ← rear 가 한 바퀴 돌아 front 를 따라잡음
front == rear 만 봐서는 구분할 수 없습니다. 고전적인 해결책이 두 가지입니다. 하나는 한 칸을 항상 비워 두어 “가득 참”을 (rear + 1) % CAP == front 로 정의하는 것입니다. 용량 5 인 배열에 4 개만 넣을 수 있게 되죠. 다른 하나가 이 예제의 방식으로, rear 대신 count 를 저장하는 것입니다. count == 0 이면 빈 것, count == CAPACITY 면 가득 찬 것이라 모호함이 아예 생기지 않습니다. 코드도 짧아지고, 용량을 전부 쓸 수 있습니다.
2.3 연결 리스트 큐와 단골 버그
배열 큐는 용량이 고정입니다. 크기 제한 없는 큐가 필요하면 연결 리스트로 만듭니다. 10주차 이중 연결 리스트에서 배운 대로 head 와 tail 을 둘 다 유지하면, head 에서 떼는 dequeue 와 tail 에 붙이는 enqueue 가 모두 O(1) 입니다. examples/queue_list.c 입니다.
/*
* queue_list.c - 연결 리스트 기반 큐
* 11주차: 스택, 큐, 덱
*
* head와 tail 포인터를 모두 유지하면 (10주차 이중 리스트에서 배운 기법)
* - enqueue: tail 뒤에 붙이기 O(1)
* - dequeue: head에서 떼기 O(1)
* 크기 제한도 없습니다. 단, 노드마다 malloc 비용이 듭니다.
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node *next;
} Node;
typedef struct {
Node *head; /* 나가는 쪽 (front) */
Node *tail; /* 들어오는 쪽 (rear) */
size_t size;
} Queue;
void queue_init(Queue *q) {
q->head = q->tail = NULL;
q->size = 0;
}
int queue_is_empty(const Queue *q) {
return q->head == NULL;
}
/* 꼬리에 붙이기: O(1) */
int enqueue(Queue *q, int value) {
Node *node = malloc(sizeof(Node));
if (node == NULL) return 0;
node->data = value;
node->next = NULL;
if (q->tail == NULL) { /* 빈 큐: head와 tail 모두 새 노드 */
q->head = q->tail = node;
} else {
q->tail->next = node;
q->tail = node;
}
q->size++;
return 1;
}
/* 머리에서 떼기: O(1) */
int dequeue(Queue *q, int *out) {
if (q->head == NULL) return 0;
Node *node = q->head;
if (out != NULL) *out = node->data;
q->head = node->next;
if (q->head == NULL) { /* 마지막 노드였다면 tail도 정리! */
q->tail = NULL;
}
free(node);
q->size--;
return 1;
}
int queue_peek(const Queue *q, int *out) {
if (q->head == NULL) return 0;
*out = q->head->data;
return 1;
}
void queue_free(Queue *q) {
Node *cur = q->head;
while (cur != NULL) {
Node *next = cur->next;
free(cur);
cur = next;
}
queue_init(q);
}
void queue_print(const Queue *q) {
printf("front -> ");
for (Node *cur = q->head; cur != NULL; cur = cur->next) {
printf("[%d] -> ", cur->data);
}
printf("NULL (rear) size=%zu\n", q->size);
}
int main(void) {
Queue q;
queue_init(&q);
int value;
printf("=== 연결 리스트 큐 ===\n");
for (int i = 1; i <= 5; i++) {
enqueue(&q, i * 10);
}
queue_print(&q);
printf("\n=== dequeue: 넣은 순서대로 나온다 ===\n");
dequeue(&q, &value); printf("dequeue() = %d\n", value);
dequeue(&q, &value); printf("dequeue() = %d\n", value);
queue_print(&q);
printf("\n=== 마지막 원소까지 빼면 tail도 NULL이 되어야 한다 ===\n");
while (dequeue(&q, &value)) {
printf("dequeue() = %d\n", value);
}
printf("head=%p, tail=%p (둘 다 NULL이어야 정상)\n",
(void *)q.head, (void *)q.tail);
/* tail 정리를 빼먹으면? 다음 enqueue가 해제된 노드에 접근 -> UAF!
* 큐 구현에서 가장 흔한 버그입니다. */
printf("\n비운 뒤 다시 enqueue해도 정상 동작:\n");
enqueue(&q, 100);
queue_print(&q);
queue_free(&q);
return 0;
}
enqueue: 빈 큐일 때가 특별하다
if (q->tail == NULL) { /* 빈 큐: head와 tail 모두 새 노드 */
q->head = q->tail = node;
} else {
q->tail->next = node;
q->tail = node;
}
큐가 비어 있으면 새 노드가 유일한 노드라 head 이자 tail 입니다. 비어 있지 않으면 지금 tail 의 뒤에 붙이고(q->tail->next = node), 새 노드를 tail 로 삼습니다. 그림으로 보면 이렇습니다.
enqueue(30) 전: head ──▶ [10] ──▶ [20] ──▶ NULL
▲
tail
① q->tail->next = node: head ──▶ [10] ──▶ [20] ──▶ [30] ──▶ NULL
▲ tail 은 아직 [20]
② q->tail = node: head ──▶ [10] ──▶ [20] ──▶ [30] ──▶ NULL
▲ tail
dequeue: 이 줄을 빼먹으면
q->head = node->next;
if (q->head == NULL) { /* 마지막 노드였다면 tail도 정리! */
q->tail = NULL;
}
free(node);
head 를 다음 노드로 옮기고 옛 head 를 해제합니다. 그런데 방금 뺀 노드가 마지막 노드였다면? head 는 NULL 이 되지만, tail 은 여전히 방금 해제한 노드를 가리킵니다. 그래서 head 가 NULL 이 되는 순간 tail 도 NULL 로 맞춰 줘야 합니다. 이 세 줄이 큐 구현에서 가장 자주 빠뜨리는 코드입니다. 얼마나 위험한지 직접 빼 봅시다.
실험: tail 정리를 빼면 — 해제 후 사용
q->tail = NULL; 을 주석으로 막고 세 가지 방법으로 돌려 봤습니다. 먼저 그냥 컴파일해서 실행하면 이렇습니다.
$ ./ql_bug2 | tail -3
비운 뒤 다시 enqueue해도 정상 동작:
front -> NULL (rear) size=1
$ echo $?
0
오류 없이 끝났습니다. 종료 코드도 0 입니다. 그런데 출력을 보면 size=1 인데 리스트는 front -> NULL 로 비어 있습니다. 100 을 넣었는데 사라졌습니다. 무슨 일이 일어났는지는 이렇습니다.
마지막 dequeue 직후 (tail 정리를 안 했을 때):
head ──▶ NULL
tail ──▶ [50] ← 이미 free 된 노드! (댕글링 포인터, 7주차)
enqueue(100):
q->tail 이 NULL 이 아니므로 else 쪽으로 →
q->tail->next = node; ← 해제된 메모리에 쓴다 (해제 후 사용, UAF)
q->tail = node; ← head 는 여전히 NULL 이라 100 은 아무도 못 찾는다
7주차에서 배운 해제 후 사용(use-after-free) 입니다. 해제된 메모리에 썼는데 이번에는 운 좋게 아무 일도 안 일어난 것처럼 보였습니다. 하지만 그 메모리가 다른 malloc 에 재사용된 뒤였다면 남의 데이터를 망가뜨렸을 것입니다. 이런 버그가 “가끔, 다른 컴퓨터에서만” 터지는 버그의 정체입니다.
도구로 잡아 봅시다. 7주차의 Valgrind 입니다.
$ valgrind -q ./ql_bug2
==311789== Invalid write of size 8
==311789== at 0x109297: enqueue (ql_bug.c:43)
==311789== by 0x1095AE: main (ql_bug.c:116)
==311789== Address 0x4aad1c8 is 8 bytes inside a block of size 16 free'd
==311789== at 0x484988F: free (in /usr/libexec/valgrind/vgpreload_memcheck-amd64-linux.so)
==311789== by 0x109321: dequeue (ql_bug.c:61)
==311789== by 0x10956B: main (ql_bug.c:107)
“enqueue 의 43번째 줄에서 8바이트를 잘못 썼다. 그 주소는 dequeue 61번째 줄에서 이미 free 한 16바이트 블록의 8바이트 안쪽이다.” 43번째 줄은 q->tail->next = node;, 61번째 줄은 free(node); 입니다. 노드 16바이트 중 8바이트 안쪽은 next 필드 자리입니다(data 4바이트 + 패딩 4바이트 뒤). Valgrind 가 어디서 썼는지, 어디서 해제했는지를 줄 번호로 짚어 줍니다.
4주차에서 쓴 AddressSanitizer 도 같은 것을 잡습니다. -fsanitize=address 로 컴파일하면 실행 즉시 멈춥니다.
$ gcc -Wall -Wextra -std=c11 -g -fsanitize=address ql_bug.c -o ql_bug
$ ./ql_bug
...
==311772==ERROR: AddressSanitizer: heap-use-after-free on address 0x502000000098 ...
WRITE of size 8 at 0x502000000098 thread T0
#0 0x6421392b7529 in enqueue .../ql_bug.c:43
#1 0x6421392b7c81 in main .../ql_bug.c:116
...
0x502000000098 is located 8 bytes inside of 16-byte region [0x502000000090,0x5020000000a0)
freed by thread T0 here:
#0 0x779a956fc4d8 in free ...
#1 0x6421392b76cf in dequeue .../ql_bug.c:61
...
SUMMARY: AddressSanitizer: heap-use-after-free .../ql_bug.c:43 in enqueue
heap-use-after-free, 그리고 같은 줄 번호 43 과 61 입니다. 두 도구의 보고가 일치합니다. 리스트를 다루는 코드를 쓰면 일단 한 번은 이 도구들로 돌려 보세요. 이번 주 Makefile 의 make memcheck 가 동적 할당을 쓰는 프로그램 다섯 개를 Valgrind 로 한꺼번에 검사합니다.
실행 결과 (queue_list)
$ ./build/queue_list
=== 연결 리스트 큐 ===
front -> [10] -> [20] -> [30] -> [40] -> [50] -> NULL (rear) size=5
=== dequeue: 넣은 순서대로 나온다 ===
dequeue() = 10
dequeue() = 20
front -> [30] -> [40] -> [50] -> NULL (rear) size=3
=== 마지막 원소까지 빼면 tail도 NULL이 되어야 한다 ===
dequeue() = 30
dequeue() = 40
dequeue() = 50
head=(nil), tail=(nil) (둘 다 NULL이어야 정상)
비운 뒤 다시 enqueue해도 정상 동작:
front -> [100] -> NULL (rear) size=1
고친 코드에서는 head=(nil), tail=(nil) 로 둘 다 NULL 이고, 다시 넣은 100 이 제대로 보입니다. %p 로 NULL 을 찍으면 glibc 는 (nil) 이라고 표시합니다.
2.4 우선순위 큐: 급한 것이 먼저
일반 큐는 “먼저 온 순서”입니다. 그런데 응급실은 그렇지 않습니다. 늦게 왔어도 위급한 환자가 먼저입니다. 이렇게 순서가 아니라 우선순위로 꺼내는 큐를 우선순위 큐(priority queue) 라고 합니다.
구현 방법은 여러 가지인데, 이번 주는 가장 이해하기 쉬운 정렬 삽입 방식입니다. 리스트를 항상 우선순위 순으로 정렬된 상태로 유지합니다.
- enqueue: 리스트를 앞에서부터 훑어 내 자리를 찾아 끼어듭니다. 최악의 경우 끝까지 가니 O(n) 입니다.
- dequeue: 맨 앞이 항상 가장 급한 원소이니 그냥 뗍니다. O(1) 입니다.
examples/priority_queue.c 입니다.
/*
* priority_queue.c - 우선순위 큐 기초
* 11주차: 스택, 큐, 덱
*
* 일반 큐는 "먼저 온 순서"지만, 우선순위 큐는 "급한 순서"입니다.
* 응급실을 떠올리세요: 늦게 와도 중환자가 먼저입니다.
*
* 이번 주는 가장 이해하기 쉬운 "정렬 삽입" 방식으로 구현합니다.
* - enqueue: 우선순위에 맞는 자리에 끼워 넣기 O(n)
* - dequeue: 맨 앞에서 빼기 O(1)
* 12주차에서 힙(heap)으로 O(log n) 버전을 만듭니다. 기대하세요!
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
typedef struct PNode {
char name[24];
int priority; /* 숫자가 작을수록 급함 (1 = 최우선) */
struct PNode *next;
} PNode;
typedef struct {
PNode *head; /* 항상 가장 급한 환자가 머리에 */
size_t size;
} PQueue;
void pq_init(PQueue *pq) {
pq->head = NULL;
pq->size = 0;
}
/* 우선순위 순서를 유지하며 삽입: O(n)
* 같은 우선순위면 먼저 온 쪽이 앞 (안정성, FIFO 유지) */
int pq_enqueue(PQueue *pq, const char *name, int priority) {
PNode *node = malloc(sizeof(PNode));
if (node == NULL) return 0;
snprintf(node->name, sizeof(node->name), "%s", name);
node->priority = priority;
/* 삽입 위치 찾기: 나보다 급하거나 같은 사람들 뒤 */
if (pq->head == NULL || priority < pq->head->priority) {
node->next = pq->head; /* 맨 앞에 삽입 */
pq->head = node;
} else {
PNode *cur = pq->head;
while (cur->next != NULL && cur->next->priority <= priority) {
cur = cur->next;
}
node->next = cur->next;
cur->next = node;
}
pq->size++;
return 1;
}
/* 가장 급한 것 꺼내기: 항상 머리에 있으므로 O(1) */
int pq_dequeue(PQueue *pq, char *name_out, int *prio_out) {
if (pq->head == NULL) return 0;
PNode *node = pq->head;
if (name_out != NULL) strcpy(name_out, node->name);
if (prio_out != NULL) *prio_out = node->priority;
pq->head = node->next;
free(node);
pq->size--;
return 1;
}
void pq_free(PQueue *pq) {
PNode *cur = pq->head;
while (cur != NULL) {
PNode *next = cur->next;
free(cur);
cur = next;
}
pq_init(pq);
}
void pq_print(const PQueue *pq) {
printf(" 대기열: ");
for (PNode *cur = pq->head; cur != NULL; cur = cur->next) {
printf("%s(P%d) ", cur->name, cur->priority);
}
printf("\n");
}
int main(void) {
PQueue er; /* 응급실(ER) 대기열 */
pq_init(&er);
printf("=== 응급실 접수 (P1=위급, P3=경증) ===\n");
struct { const char *name; int prio; } arrivals[] = {
{"김경증", 3}, {"이보통", 2}, {"박위급", 1},
{"최경증", 3}, {"정위급", 1},
};
for (size_t i = 0; i < 5; i++) {
printf("접수: %s (P%d)\n", arrivals[i].name, arrivals[i].prio);
pq_enqueue(&er, arrivals[i].name, arrivals[i].prio);
pq_print(&er);
}
printf("\n=== 진료 순서 (접수 순서가 아니다!) ===\n");
char name[24];
int prio;
int order = 1;
while (pq_dequeue(&er, name, &prio)) {
printf("%d번째 진료: %s (P%d)\n", order++, name, prio);
}
printf("\n관찰 포인트:\n");
printf("1. 위급(P1) 환자들이 먼저, 늦게 접수했어도!\n");
printf("2. 같은 우선순위끼리는 접수 순서 유지 (박위급 -> 정위급)\n");
printf("3. 정렬 삽입은 O(n) - 12주차의 힙으로 O(log n)이 된다\n");
pq_free(&er);
return 0;
}
삽입 위치 찾기
if (pq->head == NULL || priority < pq->head->priority) {
node->next = pq->head; /* 맨 앞에 삽입 */
pq->head = node;
} else {
PNode *cur = pq->head;
while (cur->next != NULL && cur->next->priority <= priority) {
cur = cur->next;
}
node->next = cur->next;
cur->next = node;
}
두 경우로 나뉩니다. 리스트가 비었거나 내가 맨 앞 사람보다 급하면(priority 숫자가 작으면) 맨 앞에 끼어듭니다. 아니면 cur 를 앞에서부터 옮기며 “내 다음 사람이 나보다 급하거나 같은 동안” 계속 갑니다. 반복이 끝난 자리의 cur 뒤에 끼어듭니다. 10주차에서 배운 “중간 삽입”과 같은 두 줄(node->next = cur->next; cur->next = node;)입니다.
정위급(P1) 이 접수될 때를 따라가 봅시다. 대기열은 박위급(P1) 이보통(P2) 김경증(P3) 최경증(P3) 입니다.
| 단계 | cur | cur->next 의 우선순위 | 조건 <= 1? |
동작 |
|---|---|---|---|---|
| 맨 앞 검사 | head 는 박위급(1) | 1 < 1 은 거짓 |
맨 앞 삽입 아님 | |
| 반복 1 | 박위급 | 이보통(2) | 2 <= 1 거짓 |
반복 끝 |
| 삽입 | 박위급 뒤, 이보통 앞에 |
결과는 박위급 정위급 이보통 김경증 최경증 입니다. 같은 P1 인 박위급 뒤에 섰습니다.
실행 결과 (priority_queue)
$ ./build/priority_queue
=== 응급실 접수 (P1=위급, P3=경증) ===
접수: 김경증 (P3)
대기열: 김경증(P3)
접수: 이보통 (P2)
대기열: 이보통(P2) 김경증(P3)
접수: 박위급 (P1)
대기열: 박위급(P1) 이보통(P2) 김경증(P3)
접수: 최경증 (P3)
대기열: 박위급(P1) 이보통(P2) 김경증(P3) 최경증(P3)
접수: 정위급 (P1)
대기열: 박위급(P1) 정위급(P1) 이보통(P2) 김경증(P3) 최경증(P3)
=== 진료 순서 (접수 순서가 아니다!) ===
1번째 진료: 박위급 (P1)
2번째 진료: 정위급 (P1)
3번째 진료: 이보통 (P2)
4번째 진료: 김경증 (P3)
5번째 진료: 최경증 (P3)
관찰 포인트:
1. 위급(P1) 환자들이 먼저, 늦게 접수했어도!
2. 같은 우선순위끼리는 접수 순서 유지 (박위급 -> 정위급)
3. 정렬 삽입은 O(n) - 12주차의 힙으로 O(log n)이 된다
접수 순서는 김경증, 이보통, 박위급, 최경증, 정위급이었는데 진료 순서는 완전히 다릅니다. 그리고 같은 P3 인 김경증과 최경증은 접수 순서대로입니다. 이 성질을 안정성(stability) 이라고 하고, 15주차 정렬에서 다시 중요하게 다룹니다.
실험: <= 를 < 로 바꾸면?
안정성을 만드는 것은 반복 조건의 <= 딱 한 글자입니다. < 로 바꾸면 “나보다 엄격히 급한 사람 뒤”까지만 가서, 같은 우선순위인 사람 앞에 끼어듭니다.
$ ./pq_lt | sed -n '/진료 순서/,/5번째/p'
=== 진료 순서 (접수 순서가 아니다!) ===
1번째 진료: 박위급 (P1)
2번째 진료: 정위급 (P1)
3번째 진료: 이보통 (P2)
4번째 진료: 최경증 (P3)
5번째 진료: 김경증 (P3)
4번째와 5번째가 뒤집혔습니다. 최경증이 김경증보다 늦게 접수했는데 먼저 진료받습니다. 우선순위가 같으면 늦게 온 사람이 새치기하는 응급실이 된 것입니다. 박위급과 정위급은 왜 안 바뀌었을까요? 정위급이 접수될 때 head 가 박위급(P1)이고 1 < 1 은 거짓이라 맨 앞 삽입은 아니고, 반복문에서 cur->next 는 이보통(2)이라 2 < 1 도 거짓이라 바로 멈춰서 결국 박위급 뒤에 들어갑니다. 즉 < 버전은 head 바로 뒤에서만 우연히 안정적이고, 그 뒤부터는 불안정합니다. 한 글자 차이가 이렇게 미묘합니다.
O(n) 삽입이 아쉽다면 다음 주를 기대하세요. 12주차의 힙(heap) 이 같은 우선순위 큐를 O(log n) 으로 만듭니다.
2.5 생산자-소비자: 실무에서 큐가 사는 곳
실무에서 큐가 가장 많이 쓰이는 자리는 속도가 다른 두 작업 사이의 완충재입니다. 네트워크 카드는 패킷이 몰아쳐 들어와도 처리 프로그램은 자기 속도로 하나씩 꺼내 갑니다. 그 사이에 큐(버퍼)가 있습니다. 키보드 입력 버퍼(2주차 scanf 의 그 버퍼), 프린터 스풀러, 대형 서비스의 메시지 큐(Kafka, RabbitMQ)가 모두 이 구조입니다.
만드는 쪽을 생산자(producer), 꺼내 쓰는 쪽을 소비자(consumer) 라고 부릅니다. examples/producer_consumer.c 는 8칸짜리 원형 버퍼를 두고, 세 가지 상황을 시뮬레이션합니다. 진짜 생산자-소비자는 두 작업이 동시에 돌지만(20주차 멀티스레딩에서 만듭니다), 여기서는 한 턴에 생산자가 n 개를 넣고 소비자가 m 개를 빼는 식으로 번갈아 돕니다.
#define BUFFER_SIZE 8
/* 원형 배열 큐 = 유한 버퍼 */
typedef struct {
int data[BUFFER_SIZE];
int front;
int count;
/* 통계 */
int produced;
int consumed;
int dropped; /* 버퍼가 가득 차서 버린 개수 */
} Buffer;
/* 생산자: 이번 턴에 n개 생산 시도 */
void producer(Buffer *b, int n, int *next_item) {
for (int i = 0; i < n; i++) {
if (buffer_put(b, *next_item)) {
b->produced++;
(*next_item)++;
} else {
b->dropped++; /* 가득 차면 버린다 (혹은 기다려야 함) */
}
}
}
/* 소비자: 이번 턴에 n개 소비 시도 */
void consumer(Buffer *b, int n) {
int item;
for (int i = 0; i < n; i++) {
if (buffer_get(b, &item)) {
b->consumed++;
}
/* 비어 있으면 그냥 넘어간다 (놀게 됨) */
}
}
buffer_put 과 buffer_get 은 2.2 의 enqueue, dequeue 와 같은 코드입니다(전체는 소스 파일을 보세요). 생산자는 버퍼가 가득 차면 데이터를 버리고 dropped 를 셉니다. 소비자는 버퍼가 비면 그 턴에 놉니다.
실행 결과 (producer_consumer)
$ ./build/producer_consumer
=== 시나리오 1: 생산(2/턴) == 소비(2/턴), 균형 ===
턴 1: 버퍼[........] 0/8
턴 2: 버퍼[........] 0/8
턴 3: 버퍼[........] 0/8
턴 4: 버퍼[........] 0/8
턴 5: 버퍼[........] 0/8
-> 버퍼가 거의 비어 있는 채로 흘러간다. 이상적!
=== 시나리오 2: 생산(3/턴) > 소비(1/턴), 과부하 ===
턴 1: 버퍼[.##.....] 2/8
턴 2: 버퍼[..####..] 4/8
턴 3: 버퍼[#..#####] 6/8
턴 4: 버퍼[###.####] 7/8 (버림: 1)
턴 5: 버퍼[####.###] 7/8 (버림: 3)
턴 6: 버퍼[#####.##] 7/8 (버림: 5)
-> 버퍼가 가득 차고 데이터가 버려진다! (백프레셔 필요)
=== 시나리오 3: 몰아치는 트래픽, 버퍼가 완충 ===
턴 1 (생산 6): 버퍼[..####..] 4/8
턴 2 (생산 0): 버퍼[....##..] 2/8
턴 3 (생산 0): 버퍼[........] 0/8
턴 4 (생산 5): 버퍼[###.....] 3/8
턴 5 (생산 0): 버퍼[..#.....] 1/8
턴 6 (생산 0): 버퍼[........] 0/8
-> 평균 생산량(약 1.8/턴) < 소비량(2/턴)이라 버퍼가 폭주를 흡수한다
실무 예: 키보드 입력 버퍼, 네트워크 수신 버퍼, 프린터 스풀러,
메시지 큐(Kafka/RabbitMQ)까지 전부 이 패턴입니다.
(20주차 멀티스레딩에서 '진짜 동시' 버전을 만듭니다)
# 이 찬 칸, . 이 빈 칸입니다. 시나리오 2 의 #..##### 처럼 찬 칸이 배열 끝과 앞에 나뉘어 있는 것은 2.2 에서 본 감김입니다.
세 시나리오가 말하는 것은 하나입니다. 시나리오 2 처럼 평균 생산량이 소비량보다 크면, 버퍼가 아무리 커도 결국 넘칩니다. 8칸이 80칸이 되면 넘치는 시점이 늦춰질 뿐입니다. 반면 시나리오 3 처럼 평균은 소비량 아래인데 순간적으로 몰리는 경우에는 버퍼가 폭주를 흡수합니다. 버퍼는 일시적인 속도 차이를 메우는 장치이지, 근본적인 처리 능력 부족을 해결하지는 못합니다. 시나리오 2 에서 데이터를 버리는 대신 “생산자를 잠시 멈추게” 하는 것을 백프레셔(backpressure) 라고 하며, 20주차에서 조건 변수로 구현합니다.
실험: 시나리오 1 이 전부 0/8 인 이유
시나리오 1 은 매 턴 2개 넣고 2개 빼니 턴이 끝날 때마다 버퍼가 비어 있습니다. 균형이 맞으면 버퍼는 거의 쓰이지 않습니다. producer 와 consumer 의 호출 순서를 바꿔서(소비를 먼저) 돌려 보면 어떻게 될까요? 첫 턴에 소비자가 빈 버퍼에서 2번 헛손질하고, 그다음 생산자가 2개 넣으니 매 턴 끝에 2/8 이 남습니다. 어느 쪽이 먼저 움직이느냐에 따라 “평상시 버퍼 점유량”이 달라지는 것입니다. 직접 바꿔 보세요.
3. 덱 (Deque) — 양쪽이 다 열린 만능 구조
덱(deque) 은 Double-Ended Queue, “양쪽 끝 큐”의 줄임말입니다. “덱”이라고 읽습니다. 스택은 한쪽 끝만, 큐는 넣는 끝과 빼는 끝이 정해져 있었는데, 덱은 양쪽 끝 모두에서 넣고 뺄 수 있습니다. 연산이 네 개입니다.
| 연산 | 하는 일 |
|---|---|
| push_front | 앞에 넣기 |
| push_back | 뒤에 넣기 |
| pop_front | 앞에서 빼기 |
| pop_back | 뒤에서 빼기 |
네 연산이 다 있으니 앞의 두 구조를 흉내 낼 수 있습니다.
push_back과pop_back만 쓰면 → 스택push_back과pop_front만 쓰면 → 큐
그래서 많은 언어의 표준 라이브러리는 덱 하나를 만들어 두고 스택과 큐를 그 위에 얹습니다. C++ 의 std::stack 과 std::queue 가 기본으로 std::deque 를 쓰는 것이 그 예입니다.
3.1 원형 배열로 만든 덱
2.2 의 원형 큐에 “front 를 왼쪽으로 한 칸 옮기는” 연산만 더하면 덱입니다. examples/deque_array.c 입니다.
/*
* deque_array.c - 덱(Deque, 양방향 큐)
* 11주차: 스택, 큐, 덱
*
* 덱(Double-Ended Queue)은 양쪽 끝 모두에서 넣고 뺄 수 있습니다.
* 스택도 되고(한쪽만 쓰면) 큐도 되는(양쪽을 쓰면) 만능 구조입니다.
*
* 원형 배열로 구현하면 네 연산 모두 O(1):
* push_front, push_back, pop_front, pop_back
*
* front를 왼쪽으로 옮길 때 인덱스가 음수가 되지 않게
* (front - 1 + CAP) % CAP 트릭을 쓰는 것이 포인트입니다.
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct {
int *data;
size_t capacity;
size_t front; /* 첫 원소 위치 */
size_t count;
} Deque;
int deque_init(Deque *d, size_t capacity) {
d->data = malloc(capacity * sizeof(int));
if (d->data == NULL) return 0;
d->capacity = capacity;
d->front = 0;
d->count = 0;
return 1;
}
int deque_is_empty(const Deque *d) { return d->count == 0; }
int deque_is_full(const Deque *d) { return d->count == d->capacity; }
/* 앞에 넣기: front를 왼쪽으로 한 칸 (음수 방지 트릭!) */
int deque_push_front(Deque *d, int value) {
if (deque_is_full(d)) return 0;
d->front = (d->front + d->capacity - 1) % d->capacity;
d->data[d->front] = value;
d->count++;
return 1;
}
/* 뒤에 넣기: rear 위치에 쓰기 */
int deque_push_back(Deque *d, int value) {
if (deque_is_full(d)) return 0;
d->data[(d->front + d->count) % d->capacity] = value;
d->count++;
return 1;
}
/* 앞에서 빼기 */
int deque_pop_front(Deque *d, int *out) {
if (deque_is_empty(d)) return 0;
if (out != NULL) *out = d->data[d->front];
d->front = (d->front + 1) % d->capacity;
d->count--;
return 1;
}
/* 뒤에서 빼기 */
int deque_pop_back(Deque *d, int *out) {
if (deque_is_empty(d)) return 0;
if (out != NULL) *out = d->data[(d->front + d->count - 1) % d->capacity];
d->count--;
return 1;
}
void deque_free(Deque *d) {
free(d->data);
d->data = NULL;
d->count = d->capacity = 0;
}
void deque_print(const Deque *d) {
printf("front [");
for (size_t i = 0; i < d->count; i++) {
printf("%d%s", d->data[(d->front + i) % d->capacity],
(i + 1 < d->count) ? " " : "");
}
printf("] back\n");
}
int main(void) {
Deque d;
deque_init(&d, 8);
int value;
printf("=== 양쪽에서 넣기 ===\n");
deque_push_back(&d, 30); /* [30] */
deque_push_back(&d, 40); /* [30 40] */
deque_push_front(&d, 20); /* [20 30 40] */
deque_push_front(&d, 10); /* [10 20 30 40] */
deque_push_back(&d, 50); /* [10 20 30 40 50] */
deque_print(&d);
printf("\n=== 양쪽에서 빼기 ===\n");
deque_pop_front(&d, &value);
printf("pop_front() = %d -> ", value); deque_print(&d);
deque_pop_back(&d, &value);
printf("pop_back() = %d -> ", value); deque_print(&d);
printf("\n=== 덱으로 스택 흉내 (뒤에서만 넣고 빼기) ===\n");
deque_push_back(&d, 99);
deque_pop_back(&d, &value);
printf("push_back(99) 후 pop_back() = %d (LIFO!)\n", value);
printf("\n=== 덱으로 큐 흉내 (뒤로 넣고 앞에서 빼기) ===\n");
deque_push_back(&d, 77);
deque_pop_front(&d, &value);
printf("push_back(77) 후 pop_front() = %d (FIFO!)\n", value);
deque_print(&d);
printf("\n=== 회문(palindrome) 검사: 덱의 고전 응용 ===\n");
const char *words[] = {"level", "hello", "racecar"};
for (int w = 0; w < 3; w++) {
Deque cd;
deque_init(&cd, 32);
for (const char *p = words[w]; *p; p++) {
deque_push_back(&cd, *p);
}
/* 양끝에서 하나씩 빼며 비교 */
int is_pal = 1;
int a, b;
while (cd.count >= 2) {
deque_pop_front(&cd, &a);
deque_pop_back(&cd, &b);
if (a != b) { is_pal = 0; break; }
}
printf(" %-8s : %s\n", words[w], is_pal ? "회문 O" : "회문 X");
deque_free(&cd);
}
deque_free(&d);
return 0;
}
네 연산 중 세 개는 이미 아는 것입니다. push_back 은 원형 큐의 enqueue, pop_front 는 dequeue 와 같고, pop_back 은 마지막 원소 data[(front + count - 1) % cap] 을 읽고 count 만 줄입니다(배열 스택의 pop 처럼 값을 지우지 않습니다). 새로운 것은 push_front 하나입니다.
3.2 앞에 넣기와 음수 인덱스 함정
int deque_push_front(Deque *d, int value) {
if (deque_is_full(d)) return 0;
d->front = (d->front + d->capacity - 1) % d->capacity;
d->data[d->front] = value;
d->count++;
return 1;
}
앞에 넣으려면 front 를 왼쪽으로 한 칸 옮긴 뒤 그 자리에 씁니다. 그런데 front 가 0 이면 왼쪽은 어디일까요? 원형이니 배열의 마지막 칸(capacity - 1)입니다. 그래서 “1 을 빼고 %” 로 쓰고 싶어집니다.
d->front = (d->front - 1) % d->capacity; /* 이렇게 쓰면? */
3주차에서 배운 정수 나눗셈 규칙을 떠올리세요. C 의 % 결과는 왼쪽 피연산자의 부호를 따릅니다. front 가 int 0 이면 (0 - 1) % 8 은 7 이 아니라 -1 입니다. 직접 확인해 봤습니다.
$ ./neg
int : (front - 1) % 8 = -1
int : (front + 8 - 1) % 8 = 7
size_t : f - 1 = 18446744073709551615
size_t : (f - 1) % 8 = 7
int 로는 -1 이 나와서 data[-1] 을 쓰게 됩니다. 4주차에서 본 범위 밖 접근입니다. 그래서 정석은 먼저 capacity 를 더해서 음수가 될 수 없게 만든 뒤 % 를 취하는 것입니다. (0 + 8 - 1) % 8 = 7. front 가 3 이면 (3 + 8 - 1) % 8 = 10 % 8 = 2 로, 더한 8 이 % 에서 다시 사라집니다. 이 트릭은 원형 버퍼를 쓰는 모든 코드에 나옵니다.
그런데 이 예제의 front 는 size_t 입니다. 위 출력의 셋째 줄처럼 size_t 0 에서 1 을 빼면 음수가 아니라 18446744073709551615 로 감아 돕니다. 그리고 넷째 줄, % 8 을 하니 7 이 나왔습니다. 그럼 capacity 를 안 더해도 되는 걸까요?
우연입니다. 2의 64제곱은 8 로 나누어떨어지기 때문에 (2^64 - 1) % 8 = 7 이 된 것뿐입니다. 용량을 5 로 바꾸면 이렇게 됩니다.
$ ./neg5
(f - 1) % cap = 0 <- 4 여야 하는데
(f + cap - 1) % cap = 4
용량이 2의 거듭제곱이 아니면 틀린 답이 나옵니다. “테스트에서는 됐는데 용량을 바꾸니 깨지는” 전형적인 버그입니다. capacity 를 더하는 방식은 int 든 size_t 든, 용량이 몇이든 항상 맞습니다.
3.3 실행 결과 (deque_array)
$ ./build/deque_array
=== 양쪽에서 넣기 ===
front [10 20 30 40 50] back
=== 양쪽에서 빼기 ===
pop_front() = 10 -> front [20 30 40 50] back
pop_back() = 50 -> front [20 30 40] back
=== 덱으로 스택 흉내 (뒤에서만 넣고 빼기) ===
push_back(99) 후 pop_back() = 99 (LIFO!)
=== 덱으로 큐 흉내 (뒤로 넣고 앞에서 빼기) ===
push_back(77) 후 pop_front() = 20 (FIFO!)
front [30 40 77] back
=== 회문(palindrome) 검사: 덱의 고전 응용 ===
level : 회문 O
hello : 회문 X
racecar : 회문 O
“양쪽에서 넣기”를 따라가 봅시다. push_back(30), push_back(40) 으로 [30 40], 그다음 push_front(20), push_front(10) 으로 앞에 붙어 [10 20 30 40], 마지막 push_back(50) 으로 [10 20 30 40 50] 입니다. 앞에 넣은 것이 앞에, 뒤에 넣은 것이 뒤에 있습니다.
“큐 흉내” 줄에서 77 을 넣고 pop_front 를 했더니 77 이 아니라 20 이 나왔습니다. 당연합니다. 큐는 먼저 들어온 것이 먼저 나오니, 뒤에 77 을 붙여도 앞에 있던 20 이 나옵니다. 그다음 상태 [30 40 77] 을 보면 77 이 맨 뒤에 잘 붙어 있습니다.
회문 검사: 왜 덱인가
level 처럼 거꾸로 읽어도 같은 낱말을 회문(palindrome) 이라고 합니다. 검사하는 방법은 양 끝에서 한 글자씩 꺼내 비교하는 것입니다. 앞에서도 빼고 뒤에서도 빼야 하니 스택도 큐도 아닌 덱의 문제입니다.
"level": l e v e l
↑ ↑ pop_front → l, pop_back → l 같다
e v e
↑ ↑ pop_front → e, pop_back → e 같다
v 하나 남았으니 (count < 2) 끝. 회문!
"hello": h e l l o
↑ ↑ pop_front → h, pop_back → o 다르다 → 회문 아님
글자 수가 홀수면 가운데 하나가 남는데, 비교할 짝이 없으니 while (cd.count >= 2) 조건으로 넘깁니다. 4주차에서 문자열을 배열 인덱스로 뒤집던 것과 결과는 같지만, “양 끝에서 하나씩”이라는 생각을 자료구조가 그대로 표현해 준다는 것이 다릅니다.
deque_push_back(&cd, *p) 에서 *p 는 char 인데 덱은 int 를 저장합니다. 2주차에서 배운 대로 char 는 int 로 자동 변환되니 문제없습니다. 글자를 정수로 저장했다가 정수끼리 비교하는 것입니다.
4. 매크로와 제네릭 프로그래밍
이번 주의 마지막 주제는 자료구조가 아니라 매크로입니다. 왜 여기서 배울까요? 지금까지 만든 Stack 은 int 만 담습니다. double 스택이 필요하면 코드를 통째로 복사해서 int 를 double 로 바꿔야 합니다. 10주차에서는 void * 로 이 문제를 풀었는데, 그 방식은 잘못된 타입을 넣어도 컴파일러가 모릅니다. 매크로는 다른 답을 줍니다. 그런데 매크로는 잘못 쓰면 정말 이상한 버그를 만들기 때문에, 먼저 함정부터 직접 밟아 봅니다.
4.1 매크로는 텍스트 치환이다
1주차 7절에서 #include 가 “파일을 그 자리에 붙여 넣는” 전처리기 지시였던 것을 기억하시나요? #define 도 같은 전처리기가 처리합니다. 컴파일러가 코드를 읽기 전에, 매크로 이름을 정의된 텍스트로 글자 그대로 바꿔치기합니다. 함수처럼 생겼지만 함수가 아닙니다. 이 차이가 모든 함정의 원인입니다. examples/macro_basics.c 입니다.
/*
* macro_basics.c - 함수형 매크로의 함정과 안전한 작성법
* 11주차: 스택, 큐, 덱
*
* 매크로는 "컴파일 전에 일어나는 텍스트 치환"입니다.
* 함수와 비슷해 보이지만 전혀 다르게 동작해서 함정이 많습니다.
* 자료구조 라이브러리를 만들 때 매크로를 쓰게 되므로
* (다음 예제 generic_macro.c) 함정부터 확실히 익힙니다.
*/
#include <stdio.h>
/* 함정 1: 괄호 없는 매크로 */
#define SQUARE_BAD(x) x * x
#define SQUARE_GOOD(x) ((x) * (x))
/* 함정 2: 인자를 두 번 평가하는 매크로 */
#define MAX_NAIVE(a, b) ((a) > (b) ? (a) : (b))
/* 함정 3: 여러 문장 매크로 - do { } while (0) 패턴으로 해결 */
#define SWAP_BAD(a, b, tmp) tmp = a; a = b; b = tmp
#define SWAP_GOOD(a, b, tmp) do { tmp = a; a = b; b = tmp; } while (0)
/* 유용한 도구: #은 문자열화, ##은 토큰 붙이기 */
#define PRINT_EXPR(expr) printf(" %-12s = %d\n", #expr, (expr))
#define MAKE_GETTER(field) \
int get_##field(void) { return field; }
static int score = 42;
MAKE_GETTER(score) /* int get_score(void) { return score; } 가 생성됨 */
int main(void) {
printf("=== 함정 1: 괄호를 빼먹으면 ===\n");
/* SQUARE_BAD(3 + 1) -> 3 + 1 * 3 + 1 = 7 (16이 아니라!) */
printf("SQUARE_BAD(3 + 1) = %d <- 기대는 16인데!\n", SQUARE_BAD(3 + 1));
printf("SQUARE_GOOD(3 + 1) = %d\n", SQUARE_GOOD(3 + 1));
printf("이유: 텍스트 치환이라 3 + 1 * 3 + 1 이 되어버림\n");
printf("\n=== 함정 2: 부작용 있는 인자의 이중 평가 ===\n");
int i = 5, j = 5;
int r1 = MAX_NAIVE(i++, 3); /* i++가 두 번 평가된다! */
printf("MAX_NAIVE(i++, 3): 결과=%d, i=%d <- i가 7?! (두 번 증가)\n", r1, i);
int r2 = (j > 3) ? j : 3; /* 함수라면 j는 한 번만 평가 */
j++;
printf("함수 방식 : 결과=%d, j=%d <- 정상\n", r2, j);
printf("교훈: 매크로 인자에 ++/--/함수호출을 넣지 말 것!\n");
printf("\n=== 함정 3: if와 여러 문장 매크로 ===\n");
int a = 1, b = 2, tmp;
/* SWAP_BAD를 if 뒤에 쓰면?
* if (조건) tmp = a; <- 여기까지만 if에 묶임!
* a = b; b = tmp; <- 조건과 무관하게 항상 실행!
* do-while(0)로 감싸면 한 문장처럼 동작한다 */
if (a < b)
SWAP_GOOD(a, b, tmp); /* 세미콜론도 자연스럽다 */
printf("SWAP_GOOD 후: a=%d, b=%d\n", a, b);
printf("\n=== # 연산자: 식을 문자열로 ===\n");
PRINT_EXPR(1 + 2 * 3);
PRINT_EXPR((1 + 2) * 3);
PRINT_EXPR(10 % 3);
printf("\n=== ## 연산자: 이름 생성 ===\n");
printf("MAKE_GETTER(score)가 만든 함수: get_score() = %d\n", get_score());
printf("\n안전 수칙 요약:\n");
printf("1. 인자와 전체를 모두 괄호로: ((x) * (x))\n");
printf("2. 부작용 있는 식을 인자로 넣지 않기\n");
printf("3. 여러 문장은 do { } while (0)\n");
printf("4. 웬만하면 함수를 쓰고, 매크로는 함수로 안 되는 곳에만\n");
return 0;
}
$ ./build/macro_basics
=== 함정 1: 괄호를 빼먹으면 ===
SQUARE_BAD(3 + 1) = 7 <- 기대는 16인데!
SQUARE_GOOD(3 + 1) = 16
이유: 텍스트 치환이라 3 + 1 * 3 + 1 이 되어버림
=== 함정 2: 부작용 있는 인자의 이중 평가 ===
MAX_NAIVE(i++, 3): 결과=6, i=7 <- i가 7?! (두 번 증가)
함수 방식 : 결과=5, j=6 <- 정상
교훈: 매크로 인자에 ++/--/함수호출을 넣지 말 것!
=== 함정 3: if와 여러 문장 매크로 ===
SWAP_GOOD 후: a=2, b=1
=== # 연산자: 식을 문자열로 ===
1 + 2 * 3 = 7
(1 + 2) * 3 = 9
10 % 3 = 1
=== ## 연산자: 이름 생성 ===
MAKE_GETTER(score)가 만든 함수: get_score() = 42
안전 수칙 요약:
1. 인자와 전체를 모두 괄호로: ((x) * (x))
2. 부작용 있는 식을 인자로 넣지 않기
3. 여러 문장은 do { } while (0)
4. 웬만하면 함수를 쓰고, 매크로는 함수로 안 되는 곳에만
4.2 함정 1: 괄호 누락
SQUARE_BAD(3 + 1) 이 16 이 아니라 7 입니다. 전처리기가 실제로 무엇을 만들었는지 1주차의 gcc -E 로 볼 수 있습니다.
$ gcc -E examples/macro_basics.c | grep "SQUARE_BAD(3 + 1) ="
printf("SQUARE_BAD(3 + 1) = %d <- 기대는 16인데!\n", 3 + 1 * 3 + 1);
x * x 의 x 자리에 3 + 1 이 글자 그대로 들어가서 3 + 1 * 3 + 1 이 됐습니다. 3주차의 우선순위대로 곱셈이 먼저라 3 + 3 + 1 = 7 입니다. 함수였다면 3 + 1 이 먼저 계산돼 4 가 넘어갔을 텐데, 매크로는 계산하지 않고 글자를 옮깁니다.
SQUARE_GOOD 은 ((x) * (x)) 로 인자마다 괄호, 전체도 괄호입니다. 인자 괄호는 위 문제를 막고, 전체 괄호는 2 * SQUARE(3) 처럼 매크로 바깥에서 곱해질 때 2 * (9) 가 되도록 보호합니다.
4.3 함정 2: 이중 평가
int r1 = MAX_NAIVE(i++, 3); /* i++가 두 번 평가된다! */
i 가 5 였는데 실행 후 7 입니다. 한 번 증가해야 할 것이 두 번 됐습니다. 전개 결과를 보면 이유가 보입니다.
$ gcc -E examples/macro_basics.c | grep "int r1 ="
int r1 = ((i++) > (3) ? (i++) : (3));
a 가 두 번 등장하니 i++ 도 두 번 들어갑니다. 조건 (i++) > (3) 에서 한 번(값 5, i 는 6), 참이라서 결과 (i++) 에서 또 한 번(값 6, i 는 7). 그래서 결과는 6, i 는 7 입니다. 괄호를 완벽히 쳐도 막을 수 없는 함정입니다. 매크로 이름이 대문자인 것은 관례이자 경고 표지판입니다. “이건 함수가 아니니 인자에 ++, --, 함수 호출처럼 부작용이 있는 식을 넣지 마라.”
4.4 함정 3: 여러 문장과 if
#define SWAP_BAD(a, b, tmp) tmp = a; a = b; b = tmp
세 문장짜리 매크로입니다. 이것을 if 뒤에 쓰면 어떻게 될까요? 소스 파일은 안전한 SWAP_GOOD 만 실행하니, SWAP_BAD 를 if 뒤에 쓴 실험 파일을 따로 만들어 돌려 봤습니다. a = 5, b = 2 라 a < b 가 거짓이니 교환이 일어나지 않아야 합니다.
int a = 5, b = 2, tmp;
if (a < b)
SWAP_BAD(a, b, tmp);
printf("a=%d, b=%d\n", a, b);
$ gcc -Wall -Wextra -std=c11 swapbad.c -o swapbad
swapbad.c:6:24: warning: macro expands to multiple statements [-Wmultistatement-macros]
6 | SWAP_BAD(a, b, tmp);
| ^~~
swapbad.c:5:5: note: some parts of macro expansion are not guarded by this ‘if’ clause
5 | if (a < b)
| ^~
$ ./swapbad
a=2, b=32766
a 는 2 가 됐고 b 는 32766 이라는 쓰레기입니다. 전개 결과를 보면 이유가 명확합니다.
$ gcc -E swapbad.c | grep -A1 "if (a < b)"
if (a < b)
tmp = a; a = b; b = tmp;
if 는 첫 문장 tmp = a; 만 묶습니다. 조건이 거짓이라 tmp = a 는 건너뛰지만, a = b; b = tmp; 는 조건과 무관하게 항상 실행됩니다. 그래서 a 에 b 의 2 가 들어가고, b 에는 한 번도 값을 받지 못한 tmp 의 쓰레기(1주차 10절의 초기화 안 된 변수)가 들어갔습니다. 다행히 GCC 13 은 -Wall 에 포함된 -Wmultistatement-macros 로 “매크로가 여러 문장으로 펼쳐지는데 일부만 if 에 묶인다”고 경고해 줍니다. 경고를 읽는 습관이 여기서도 빛을 발합니다.
해결책이 SWAP_GOOD 의 do { ... } while (0) 입니다. 세 문장을 do { } 로 감싸면 하나의 문장이 되고, 뒤의 while (0) 은 한 번만 실행하고 끝난다는 뜻이라 반복문이 아닙니다. 왜 그냥 { ... } 로 감싸지 않을까요? if (x) { ... }; 처럼 매크로 뒤에 붙는 세미콜론이 { } 뒤에서는 빈 문장이 되어 else 를 붙일 수 없게 됩니다. do { } while (0) 은 끝에 세미콜론을 요구하기 때문에 SWAP_GOOD(a, b, tmp); 라고 자연스럽게 쓸 수 있고 else 도 이어집니다. 리눅스 커널 소스에 수천 번 나오는 관용구입니다.
4.5 # 과 ## : 매크로만 할 수 있는 일
함정만 있으면 매크로를 쓸 이유가 없습니다. 함수로는 불가능한 일 두 가지가 있습니다.
#define PRINT_EXPR(expr) printf(" %-12s = %d\n", #expr, (expr))
#expr 은 인자를 문자열로 바꿉니다. PRINT_EXPR(1 + 2 * 3) 은 "1 + 2 * 3" 이라는 글자와 그 계산 결과 7 을 함께 찍습니다. 함수는 자기가 받은 인자가 원래 어떤 식이었는지 알 수 없지만, 전처리기는 글자를 보고 있으니 할 수 있습니다. 디버그 출력에 아주 유용합니다.
#define MAKE_GETTER(field) \
int get_##field(void) { return field; }
MAKE_GETTER(score) /* int get_score(void) { return score; } 가 생성됨 */
## 은 양쪽 토큰을 붙여서 새 이름을 만듭니다. get_##field 에 score 가 들어가면 get_score 라는 함수 이름이 됩니다. 함수 정의를 통째로 만들어 내는 것입니다. 줄 끝의 \ 는 “매크로가 다음 줄로 이어진다”는 표시입니다. 이 ## 이 다음 절의 핵심 도구입니다.
4.6 매크로 제네릭: 타입별 코드 찍어내기
10주차 void * 방식의 약점을 다시 봅시다. vector_push(&v, &x) 에 int 를 넣기로 한 벡터에 double 을 넣어도 컴파일은 됩니다. 실행 중에 이상한 값이 나오고 나서야 압니다. ## 을 쓰면 다른 길이 열립니다. 타입마다 스택 코드를 통째로 생성하는 것입니다. examples/generic_macro.c 입니다.
/*
* generic_macro.c - 매크로로 만드는 타입 안전 제네릭 스택
* 11주차: 스택, 큐, 덱
*
* 10주차의 void* 제네릭은 강력하지만 약점이 있습니다:
* 잘못된 타입을 넣어도 컴파일러가 못 잡습니다 (런타임에 터짐).
*
* 다른 접근: 매크로로 "타입별 코드를 찍어내기".
* DEFINE_STACK(int)라고 쓰면 int 전용 스택 코드가 통째로 생성됩니다.
* 타입이 틀리면 컴파일 에러 -> 타입 안전!
* (C++ 템플릿의 조상님 같은 기법입니다)
*
* 덤으로 C11의 _Generic으로 타입별 분기도 배웁니다.
*/
#include <stdio.h>
#include <stdlib.h>
/* 타입 T 전용 스택을 통째로 생성하는 매크로
* - ##로 이름을 붙인다: Stack_int, stack_int_push, ...
* - 백슬래시(\)로 여러 줄 매크로 작성
*/
#define DEFINE_STACK(T) \
typedef struct { \
T *data; \
size_t size; \
size_t capacity; \
} Stack_##T; \
\
static void stack_##T##_init(Stack_##T *s) { \
s->data = NULL; \
s->size = 0; \
s->capacity = 0; \
} \
\
static int stack_##T##_push(Stack_##T *s, T value) { \
if (s->size == s->capacity) { \
size_t cap = (s->capacity == 0) ? 4 : s->capacity*2; \
T *tmp = realloc(s->data, cap * sizeof(T)); \
if (tmp == NULL) return 0; \
s->data = tmp; \
s->capacity = cap; \
} \
s->data[s->size++] = value; \
return 1; \
} \
\
static int stack_##T##_pop(Stack_##T *s, T *out) { \
if (s->size == 0) return 0; \
*out = s->data[--s->size]; \
return 1; \
} \
\
static void stack_##T##_free(Stack_##T *s) { \
free(s->data); \
stack_##T##_init(s); \
}
/* 여기서 int 스택과 double 스택 코드가 실제로 생성된다! */
DEFINE_STACK(int)
DEFINE_STACK(double)
/* C11 _Generic: 인자 타입에 따라 다른 코드를 고르는 컴파일 타임 스위치 */
#define TYPE_NAME(x) _Generic((x), \
int: "int", \
double: "double", \
char: "char", \
char *: "char *", \
default: "알 수 없는 타입")
#define PRINT_VALUE(x) _Generic((x), \
int: print_int, \
double: print_double, \
char *: print_string)(x)
void print_int(int x) { printf("정수: %d\n", x); }
void print_double(double x) { printf("실수: %f\n", x); }
void print_string(char *x) { printf("문자열: %s\n", x); }
int main(void) {
printf("=== DEFINE_STACK: 타입별 스택 찍어내기 ===\n");
Stack_int si;
stack_int_init(&si);
for (int i = 1; i <= 3; i++) stack_int_push(&si, i * 100);
int iv;
printf("Stack_int : ");
while (stack_int_pop(&si, &iv)) printf("%d ", iv);
printf("\n");
stack_int_free(&si);
Stack_double sd;
stack_double_init(&sd);
stack_double_push(&sd, 1.5);
stack_double_push(&sd, 2.5);
double dv;
printf("Stack_double: ");
while (stack_double_pop(&sd, &dv)) printf("%.1f ", dv);
printf("\n");
stack_double_free(&sd);
/* stack_int_push(&si, "문자열"); <- 컴파일 에러! 타입 안전! */
printf("\n잘못된 타입을 push하면? void* 방식과 달리 '컴파일 에러'!\n");
printf("(런타임에 터지는 것보다 백만 배 낫다)\n");
printf("\n=== C11 _Generic: 컴파일 타임 타입 스위치 ===\n");
int n = 42;
double d = 3.14;
char *s = "hello";
printf("n의 타입: %s\n", TYPE_NAME(n));
printf("d의 타입: %s\n", TYPE_NAME(d));
printf("s의 타입: %s\n", TYPE_NAME(s));
printf("\n같은 매크로가 타입에 맞는 함수를 고른다:\n");
PRINT_VALUE(n);
PRINT_VALUE(d);
PRINT_VALUE(s);
printf("\n두 제네릭 기법 비교:\n");
printf("- void* 방식(10주차): 코드 한 벌, 런타임 크기 계산, 타입 검사 없음\n");
printf("- 매크로 방식(오늘) : 타입별 코드 생성, 타입 안전, 바이너리 커짐\n");
printf("상황에 맞게 고르는 것이 엔지니어링입니다.\n");
return 0;
}
DEFINE_STACK 의 몸통은 1.2 의 stack_array.c 와 같은 코드입니다. 다른 점은 int 가 있던 자리마다 T 가 있고, 이름마다 ##T 가 붙어 있다는 것뿐입니다. DEFINE_STACK(int) 한 줄을 쓰면 전처리기가 T 를 int 로, Stack_##T 를 Stack_int 로, stack_##T##_push 를 stack_int_push 로 바꿔서 구조체 하나와 함수 네 개를 만들어 냅니다. 정말 그런지 gcc -E 로 봅시다.
$ gcc -E examples/generic_macro.c | grep "} Stack_int;" | sed 's/; /;\n/g' | head -5
typedef struct { int *data;
size_t size;
size_t capacity;
} Stack_int;
static void stack_int_init(Stack_int *s) { s->data = ...
매크로는 한 줄로 펼쳐지기 때문에 보기 좋게 세미콜론마다 줄을 나눴습니다. Stack_int 라는 구조체와 stack_int_init 함수가 진짜로 생겨났습니다. 우리는 이 코드를 한 글자도 직접 쓰지 않았습니다.
실행 결과 (generic_macro)
$ ./build/generic_macro
=== DEFINE_STACK: 타입별 스택 찍어내기 ===
Stack_int : 300 200 100
Stack_double: 2.5 1.5
잘못된 타입을 push하면? void* 방식과 달리 '컴파일 에러'!
(런타임에 터지는 것보다 백만 배 낫다)
=== C11 _Generic: 컴파일 타임 타입 스위치 ===
n의 타입: int
d의 타입: double
s의 타입: char *
같은 매크로가 타입에 맞는 함수를 고른다:
정수: 42
실수: 3.140000
문자열: hello
두 제네릭 기법 비교:
- void* 방식(10주차): 코드 한 벌, 런타임 크기 계산, 타입 검사 없음
- 매크로 방식(오늘) : 타입별 코드 생성, 타입 안전, 바이너리 커짐
상황에 맞게 고르는 것이 엔지니어링입니다.
실험: 잘못된 타입을 넣으면 정말 컴파일러가 잡을까?
소스에 주석으로 막아 둔 줄 stack_int_push(&si, "문자열"); 의 주석을 풀고 컴파일해 봤습니다.
$ gcc -Wall -Wextra -std=c11 gm_bad.c -o gm_bad
gm_bad.c: In function ‘main’:
gm_bad.c:103:25: warning: passing argument 2 of ‘stack_int_push’ makes integer from pointer without a cast [-Wint-conversion]
103 | stack_int_push(&si, "문자열");
| ^~~~~~~~
| |
| char *
gm_bad.c:35:49: note: expected ‘int’ but argument is of type ‘char *’
35 | static int stack_##T##_push(Stack_##T *s, T value) { \
| ^
gm_bad.c:59:1: note: in expansion of macro ‘DEFINE_STACK’
59 | DEFINE_STACK(int)
| ^~~~~~~~~~~~
“int 를 기대했는데 char * 를 줬다”고 정확히 잡아냅니다. 심지어 그 함수가 DEFINE_STACK 매크로에서 생성됐다는 것까지 알려 줍니다. 소스 파일의 주석은 “컴파일 에러”라고 했는데 실제로는 경고입니다. GCC 13 은 이 경우를 경고로 처리하고 실행 파일을 만듭니다(GCC 14 부터는 오류입니다). 하지만 1주차부터 지켜 온 “경고 0개” 원칙대로라면 이 코드는 통과하지 못합니다. void * 방식이었다면 아무 말 없이 문자열의 주소를 정수로 잘라 넣었을 것입니다.
C11 _Generic: 타입에 따라 고르는 스위치
#define TYPE_NAME(x) _Generic((x), \
int: "int", \
double: "double", \
char: "char", \
char *: "char *", \
default: "알 수 없는 타입")
_Generic 은 C11 에 들어온 키워드로, 인자의 타입을 보고 목록에서 하나를 고릅니다. 3주차의 switch 와 비슷한데, 값이 아니라 타입으로 분기하고, 실행 중이 아니라 컴파일할 때 결정됩니다. 전개 결과를 보면 이렇습니다.
$ gcc -E examples/generic_macro.c | grep -o 'printf("n의 타입: %s\\n", _Generic[^;]*;'
printf("n의 타입: %s\n", _Generic((n), int: "int", double: "double", char: "char", char *: "char *", default: "알 수 없는 타입"));
n 이 int 이니 컴파일러는 "int" 만 남기고 나머지를 버립니다. PRINT_VALUE(x) 는 한 걸음 더 나가서 함수 이름을 고른 뒤 (x) 로 호출합니다. 같은 PRINT_VALUE 를 썼는데 정수, 실수, 문자열에 맞는 함수가 각각 불렸습니다. C 표준 라이브러리의 <tgmath.h> 가 이 방식으로 sqrt 하나로 float, double, long double 을 다 처리합니다.
두 제네릭의 트레이드오프
void * 방식 (10주차) |
매크로 방식 (이번 주) | |
|---|---|---|
| 코드 크기 | 한 벌 | 타입 수만큼 생성 (바이너리가 커짐) |
| 타입 검사 | 없음. 실행 중에 사고 | 컴파일 타임. 경고나 오류 |
| 속도 | 원소 크기를 실행 중에 계산, memcpy |
타입이 고정이라 일반 코드와 같음 |
| 디버깅 | 쉬움 | 매크로 전개라 오류 메시지가 길어짐 |
| 쓰는 곳 | qsort, bsearch 같은 표준 함수 |
성능이 중요한 컨테이너 라이브러리 |
어느 쪽이 낫다고 할 수 없습니다. 상황에 맞게 고르는 것이 엔지니어링입니다. C++ 의 템플릿은 매크로 방식의 후손입니다.
4.7 X-매크로: 목록을 한 곳에서만 관리하기
마지막 매크로 기법입니다. 에러 코드가 있다고 합시다. 코드마다 (1) enum 상수, (2) 이름 문자열(디버그 출력용), (3) 설명 문자열, (4) 숫자 코드가 필요합니다. 순진하게 쓰면 같은 목록을 네 번 쓰게 됩니다. 에러를 하나 추가할 때 네 곳을 고쳐야 하고, 하나라도 빠뜨리거나 순서가 어긋나면 “ERR_TIMEOUT 인데 설명은 ‘메모리 부족'” 같은 버그가 납니다. 8주차의 열거형 절에서 이 문제를 잠깐 언급했습니다.
X-매크로는 목록을 딱 한 번 적고, X 라는 매크로의 정의를 바꿔 가며 그 목록을 여러 모양으로 펼쳐냅니다. examples/xmacro.c 입니다.
/*
* xmacro.c - X-매크로 패턴
* 11주차: 스택, 큐, 덱
*
* "같은 목록을 여러 곳에서 반복해야 하는" 문제의 우아한 해결책입니다.
*
* 예: 에러 코드마다 (1) enum 상수, (2) 이름 문자열, (3) 설명이 필요할 때.
* 목록을 세 번 쓰면 하나 추가할 때마다 세 곳을 고쳐야 하고,
* 하나라도 빠뜨리면 버그입니다.
*
* X-매크로: 목록을 "한 번만" 정의하고, X의 정의를 바꿔가며
* 같은 목록을 여러 형태로 펼쳐냅니다.
*/
#include <stdio.h>
/* ==================== 목록은 여기 딱 한 번! ==================== */
/* 새 에러를 추가하려면 이 표에 한 줄만 추가하면 끝 */
#define ERROR_LIST \
X(ERR_NONE, "성공", 0) \
X(ERR_NOT_FOUND, "찾을 수 없음", 404) \
X(ERR_PERMISSION, "권한 없음", 403) \
X(ERR_OUT_OF_MEM, "메모리 부족", 507) \
X(ERR_TIMEOUT, "시간 초과", 408)
/* ==================== 펼치기 1: enum 생성 ==================== */
#define X(name, desc, code) name,
typedef enum {
ERROR_LIST
ERROR_COUNT /* 자동으로 개수까지! */
} ErrorCode;
#undef X
/* ==================== 펼치기 2: 이름 문자열 배열 ==================== */
#define X(name, desc, code) #name,
static const char *error_names[] = {
ERROR_LIST
};
#undef X
/* ==================== 펼치기 3: 설명 배열 ==================== */
#define X(name, desc, code) desc,
static const char *error_descs[] = {
ERROR_LIST
};
#undef X
/* ==================== 펼치기 4: 숫자 코드 배열 ==================== */
#define X(name, desc, code) code,
static const int error_codes[] = {
ERROR_LIST
};
#undef X
/* 이제 세 배열과 enum이 "자동으로 항상 동기화"됩니다 */
/* 화면 폭 기준 왼쪽 정렬 (한글은 2칸). %-14s 는 바이트를 세서 한글이 섞이면 어긋난다 */
static void print_padded(const char *s, int width) {
int cells = 0;
for (const unsigned char *p = (const unsigned char *)s; *p; p++) {
if ((*p & 0xC0) != 0x80) cells += (*p >= 0x80) ? 2 : 1;
}
printf("%s", s);
for (; cells < width; cells++) putchar(' ');
}
const char *error_to_string(ErrorCode e) {
if (e < 0 || e >= ERROR_COUNT) return "???";
return error_names[e];
}
int main(void) {
printf("=== X-매크로가 생성한 에러 표 ===\n\n");
print_padded("enum 이름", 16); putchar(' ');
print_padded("설명", 14); printf(" 코드\n");
printf("------------------------------------------\n");
for (int i = 0; i < ERROR_COUNT; i++) {
print_padded(error_names[i], 16); putchar(' ');
print_padded(error_descs[i], 14); printf(" %d\n", error_codes[i]);
}
printf("\n총 %d개 (ERROR_COUNT도 자동 계산)\n", ERROR_COUNT);
printf("\n=== 사용 예 ===\n");
ErrorCode e = ERR_NOT_FOUND;
printf("함수가 %s(%d)를 반환했다면:\n", error_to_string(e), e);
printf(" 사용자 메시지: \"%s\" (HTTP %d)\n",
error_descs[e], error_codes[e]);
printf("\nX-매크로의 힘:\n");
printf("1. 목록을 딱 한 곳에서 관리 (Single Source of Truth)\n");
printf("2. enum/문자열/코드가 어긋날 수 없다\n");
printf("3. 실전: 리눅스 커널, SQLite 등에서 광범위하게 사용\n");
return 0;
}
펼쳐지는 과정
ERROR_LIST 는 X(...) 다섯 개가 나열된 덩어리입니다. 그 자체로는 X 가 무엇인지 정해져 있지 않습니다. 쓰는 쪽에서 X 를 정의한 뒤 ERROR_LIST 를 쓰면, 다섯 줄이 그 정의대로 바뀝니다. 그리고 #undef X 로 정의를 지워서 다음에 다른 뜻으로 다시 정의할 수 있게 합니다. 실제 전개 결과입니다.
$ gcc -E examples/xmacro.c | grep -A3 "^typedef enum"
typedef enum {
ERR_NONE, ERR_NOT_FOUND, ERR_PERMISSION, ERR_OUT_OF_MEM, ERR_TIMEOUT,
ERROR_COUNT
} ErrorCode;
$ gcc -E examples/xmacro.c | grep -A2 "error_names\[\] ="
static const char *error_names[] = {
"ERR_NONE", "ERR_NOT_FOUND", "ERR_PERMISSION", "ERR_OUT_OF_MEM", "ERR_TIMEOUT",
};
첫 번째 펼치기에서 X(name, desc, code) 는 name, 이 되어 enum 상수 다섯 개가 나열됐습니다. 두 번째에서는 #name, 이 되어 4.5 의 # 으로 이름이 문자열이 됐습니다. 같은 ERROR_LIST 에서 나왔으니 enum 의 순서와 문자열 배열의 순서가 어긋날 수가 없습니다. ERROR_COUNT 는 enum 의 마지막에 붙어서 자동으로 개수(5)가 됩니다. 8주차에서 배운 “enum 은 0 부터 차례로 번호를 매긴다”는 성질 덕분입니다.
print_padded 는 8주차 student_manager 와 4주차 grade_manager 에서 쓴 것과 같은 도구입니다. %-14s 는 바이트를 세기 때문에 한글(3바이트, 화면 2칸)이 섞이면 표가 어긋납니다. UTF-8 에서 이어지는 바이트(10xxxxxx 꼴)는 건너뛰고 첫 바이트만 세되, 아스키가 아니면 2칸으로 칩니다.
실행 결과 (xmacro)
$ ./build/xmacro
=== X-매크로가 생성한 에러 표 ===
enum 이름 설명 코드
------------------------------------------
ERR_NONE 성공 0
ERR_NOT_FOUND 찾을 수 없음 404
ERR_PERMISSION 권한 없음 403
ERR_OUT_OF_MEM 메모리 부족 507
ERR_TIMEOUT 시간 초과 408
총 5개 (ERROR_COUNT도 자동 계산)
=== 사용 예 ===
함수가 ERR_NOT_FOUND(1)를 반환했다면:
사용자 메시지: "찾을 수 없음" (HTTP 404)
X-매크로의 힘:
1. 목록을 딱 한 곳에서 관리 (Single Source of Truth)
2. enum/문자열/코드가 어긋날 수 없다
3. 실전: 리눅스 커널, SQLite 등에서 광범위하게 사용
직접 해 보기: ERROR_LIST 에 X(ERR_BAD_INPUT, "잘못된 입력", 400) 한 줄을 추가하고 다시 컴파일해 보세요. enum, 이름 배열, 설명 배열, 코드 배열, ERROR_COUNT 가 전부 저절로 따라옵니다. 이것이 한 곳에서만 관리(Single Source of Truth) 의 힘입니다. 리눅스 커널과 SQLite 의 소스 곳곳에서 이 패턴을 볼 수 있습니다.
5. 실습 프로젝트
이번 주 자료구조를 실제로 조립해 봅니다. 세 프로젝트 모두 projects/ 에 있고 make 로 함께 빌드됩니다. 코드 전체는 파일을 열어 보고, 여기서는 자료구조가 어떻게 쓰였는지가 드러나는 부분만 짚습니다.
프로젝트 1: 후위 표기법 계산기 (postfix_calc.c)
스택의 가장 유명한 실전 응용입니다. 1주차에서 “컴파일러가 코드를 어떻게 번역하는지” 봤는데, 컴파일러가 3 + 4 * 2 같은 식을 계산 순서대로 바꾸는 방법이 바로 이것입니다. K&R 교과서 4장의 역폴란드 계산기도 같은 원리입니다.
왜 후위 표기법인가
우리가 쓰는 3 + 4 * 2 는 연산자가 숫자 사이에 있어서 중위(infix) 표기법이라고 합니다. 사람에게는 익숙하지만 컴퓨터에는 골칫거리입니다. 왼쪽부터 읽으면 3 + 4 를 먼저 계산하고 싶어지는데, 실제로는 * 가 먼저이기 때문입니다. 우선순위와 괄호를 매번 따져야 합니다.
같은 식을 3 4 2 * + 로 쓰면 어떨까요? 연산자가 피연산자 뒤에 오는 후위(postfix) 표기법입니다. 이 표기법에는 괄호도 우선순위도 없습니다. 왼쪽부터 읽다가 연산자를 만나면 바로 앞의 두 수에 적용하면 끝입니다. 계산 순서가 표기 자체에 녹아 있습니다. 컴퓨터는 이런 걸 좋아합니다.
계산기는 두 단계로 동작합니다.
- 중위 → 후위 변환 (셔팅야드 알고리즘, 연산자 스택 사용)
- 후위 표기법 계산 (숫자 스택 사용)
1단계: 셔팅야드 알고리즘
이름은 기차 조차장(shunting yard)에서 왔습니다. 열차 칸을 옆 선로에 잠시 빼 두었다가 순서를 바꿔 내보내는 곳이죠. 연산자를 스택에 잠시 빼 두었다가 우선순위에 맞게 내보냅니다. 규칙은 네 가지입니다.
- 숫자: 바로 출력
(: push):(가 나올 때까지 pop 해서 출력.(는 버림- 연산자: 스택 위에 우선순위가 같거나 높은 연산자가 있으면 먼저 pop 해서 출력한 뒤, 자신을 push
/* 연산자 우선순위: 클수록 먼저 계산 */
int precedence(char op) {
switch (op) {
case '+': case '-': return 1;
case '*': case '/': return 2;
default: return 0; /* '(' 등 */
}
}
( 의 우선순위가 0 인 것이 요령입니다. 연산자를 push 할 때 스택 위의 ( 는 우선순위 0 이라 절대 먼저 나가지 않고, ) 를 만날 때까지 스택에 남아 괄호 안의 연산자들을 보호합니다.
3 + 4 * 2 를 따라가 봅시다. 스택은 왼쪽이 바닥입니다.
| 읽은 것 | 동작 | 연산자 스택 | 출력 |
|---|---|---|---|
3 |
출력 | 3 |
|
+ |
스택 비었으니 push | + |
3 |
4 |
출력 | + |
3 4 |
* |
스택 위 +(1) 이 *(2) 보다 낮으니 그냥 push |
+ * |
3 4 |
2 |
출력 | + * |
3 4 2 |
| 끝 | 남은 연산자 전부 pop | 3 4 2 * + |
* 가 + 보다 위에 쌓였다가 먼저 나옵니다. 그래서 출력에서 * 가 + 앞에 옵니다. 이번엔 괄호가 있는 (3 + 4) * 2 입니다.
| 읽은 것 | 동작 | 연산자 스택 | 출력 |
|---|---|---|---|
( |
push | ( |
|
3 |
출력 | ( |
3 |
+ |
스택 위 ((0) 은 낮으니 push |
( + |
3 |
4 |
출력 | ( + |
3 4 |
) |
( 까지 pop: + 출력, ( 버림 |
3 4 + |
|
* |
스택 비었으니 push | * |
3 4 + |
2 |
출력 | * |
3 4 + 2 |
| 끝 | pop | 3 4 + 2 * |
괄호 덕분에 + 가 * 보다 먼저 출력됐습니다. 코드에서 이 규칙이 그대로 보입니다.
} else if (strchr("+-*/", c) != NULL) {
/* 스택 위의 같거나 높은 우선순위 연산자를 먼저 출력 */
while (!os_is_empty(&ops) &&
precedence(os_peek(&ops)) >= precedence(c)) {
char op;
os_pop(&ops, &op);
char s[2] = {op, '\0'};
EMIT(s);
}
os_push(&ops, c);
i++;
}
>= 의 = 가 중요합니다. 10 - 2 - 3 처럼 같은 우선순위가 이어질 때, 새 - 를 만나면 스택의 - 를 먼저 내보내야 (10 - 2) - 3 = 5 가 됩니다. > 로 쓰면 10 - (2 - 3) = 11 이 되어 틀립니다. 이것을 왼쪽 결합이라고 하고, 3주차에서 본 “같은 우선순위는 왼쪽부터”가 바로 이 규칙입니다.
EMIT 은 4절에서 배운 do { } while (0) 매크로입니다. 출력 버퍼에 토큰과 공백을 붙이는 다섯 줄을 여섯 군데에서 반복하지 않으려고 썼고, 함수 안에서 #define 하고 끝에서 #undef 해서 범위를 좁혔습니다.
2단계: 후위 표기법 계산
숫자 스택 하나면 됩니다. 숫자는 push, 연산자를 만나면 두 개 pop 해서 계산하고 결과를 push 합니다.
if (strlen(tok) == 1 && strchr("+-*/", tok[0]) != NULL) {
double b, a; /* 순서 주의: b가 먼저 나온다! */
if (!ns_pop(&nums, &b) || !ns_pop(&nums, &a)) {
return 0; /* 피연산자 부족 */
}
double r;
switch (tok[0]) {
case '+': r = a + b; break;
case '-': r = a - b; break;
case '*': r = a * b; break;
case '/':
if (b == 0.0) {
fprintf(stderr, "오류: 0으로 나눌 수 없습니다\n");
return 0;
}
r = a / b;
break;
default: return 0;
}
ns_push(&nums, r);
}
3 4 2 * + 를 계산해 봅시다.
| 토큰 | 동작 | 숫자 스택 |
|---|---|---|
3 |
push | 3 |
4 |
push | 3 4 |
2 |
push | 3 4 2 |
* |
pop → b=2, pop → a=4, 4×2=8 push | 3 8 |
+ |
pop → b=8, pop → a=3, 3+8=11 push | 11 |
| 끝 | 하나 남았으니 결과 11 |
이 계산기의 최다 빈출 버그가 pop 순서입니다. 10 2 - 에서 먼저 pop 되는 것은 2 입니다. 스택은 LIFO 니까 나중에 넣은 2 가 먼저 나옵니다. 그래서 먼저 pop 한 값을 b(오른쪽 피연산자), 나중에 pop 한 값을 a(왼쪽)에 넣고 a - b 를 계산해야 8 이 나옵니다. 순서를 뒤집어 b - a 로 쓰면 뺄셈과 나눗셈이 전부 틀립니다. 덧셈과 곱셈은 순서가 바뀌어도 결과가 같아서 이 버그가 덧셈 테스트만으로는 안 드러납니다.
계산이 끝났을 때 스택에 정확히 하나가 남아야 올바른 식입니다. 두 개 이상 남으면 연산자가 모자란 것이고(3 4), pop 할 것이 없으면 연산자가 많은 것입니다(1 +).
실행 결과 (postfix_calc)
$ ./build/postfix_calc
후위 표기법 계산기
==================
중위: 3 + 4 * 2
후위: 3 4 2 * +
결과: 11
중위: (3 + 4) * 2
후위: 3 4 + 2 *
결과: 14
중위: 10 - 2 - 3
후위: 10 2 - 3 -
결과: 5
중위: 100 / 4 / 5
후위: 100 4 / 5 /
결과: 5
중위: 2 * (3 + 4 * (5 - 1))
후위: 2 3 4 5 1 - * + *
결과: 38
중위: 3.5 + 1.5
후위: 3.5 1.5 +
결과: 5
중위: 7 / 0
후위: 7 0 /
오류: 0으로 나눌 수 없습니다
-> 계산 오류!
중위: 3 + * 4
후위: 3 4 * +
-> 계산 오류!
중위: (3 + 4
-> 문법 오류!
직접 계산: ./postfix_calc "수식"
후위 표기 계산기
표로 추적한 두 식이 정확히 그 후위식으로 나왔습니다. 세 오류 사례도 봅시다.
7 / 0: 변환은 되지만 계산에서b == 0.0을 잡아 거부합니다. “오류: 0으로 나눌 수 없습니다”는stderr로 나가고 나머지는stdout이라, 9주차에서 배운 대로 파이프로 파일에 저장하면 이 줄만 순서가 달라질 수 있습니다.3 + * 4: 변환기는 연산자가 연달아 나온 것을 문법 오류로 잡지 않고3 4 * +를 만들어 냅니다. 대신 계산기가+를 처리하려다 pop 할 것이 하나뿐이라 “피연산자 부족”으로 거부합니다. 앞 단계가 놓친 것을 뒤 단계가 잡은 셈입니다.(3 + 4: 끝까지 읽었는데 스택에(가 남아 있으니 변환기가 “짝 없는(“로 거부합니다. 1.4 의 괄호 검사와 같은 논리입니다.
실험: 직접 식을 넣어 보기
명령줄 인자로 식을 주면 그것만 계산합니다(5주차의 argc, argv).
$ ./build/postfix_calc "10 - 2"
중위: 10 - 2
후위: 10 2 -
결과: 8
$ ./build/postfix_calc "2 ^ 3"
중위: 2 ^ 3
-> 문법 오류!
$ ./build/postfix_calc "3 4"
중위: 3 4
후위: 3 4
-> 계산 오류!
$ ./build/postfix_calc "8 / (4 - 4)"
중위: 8 / (4 - 4)
후위: 8 4 4 - /
오류: 0으로 나눌 수 없습니다
-> 계산 오류!
10 - 2 가 8 이면 pop 순서가 맞는 것입니다. ^ 는 strchr("+-*/", c) 에 없어서 “모르는 문자”로 문법 오류가 납니다. 3 4 는 스택에 둘이 남아 계산 오류입니다. 8 / (4 - 4) 는 괄호 안이 0 이 되어 실행 중에야 잡힙니다.
확장 아이디어: ^(거듭제곱) 추가. 우선순위 3 이고 오른쪽 결합이라(2 ^ 3 ^ 2 = 2 ^ 9) >= 대신 > 를 써야 합니다. 그리고 단항 마이너스(-3 + 5), 변수 지원.
프로젝트 2: 작업 스케줄러 (task_scheduler.c)
운영체제의 CPU 스케줄러 축소판입니다. 이번 주 자료구조 두 개를 조합합니다.
- 멀티레벨 우선순위 큐: 우선순위(높음 1, 보통 2, 낮음 3)마다 큐를 하나씩. 2.4 의 정렬 삽입 대신 큐 3개를 배열로 두고, 꺼낼 때 높은 큐부터 봅니다. 우선순위 종류가 몇 개 안 될 때 흔히 쓰는 방식입니다.
- 라운드 로빈: 작업은 한 턴에 최대 3초(타임 슬라이스)만 실행하고, 못 끝내면 자기 큐의 뒤로 돌아갑니다. 큐가 FIFO 라서 같은 우선순위끼리 공평하게 돌아가며 실행됩니다.
/* 우선순위별 큐: 배열 인덱스가 우선순위 (멀티레벨 큐) */
#define LEVELS 3
typedef struct {
Task *head[LEVELS]; /* 우선순위 1..3 -> 인덱스 0..2 */
Task *tail[LEVELS];
int count;
} Scheduler;
/* 다음 실행할 작업 꺼내기: 가장 높은 우선순위 큐의 머리 */
Task *sched_next(Scheduler *s) {
for (int lv = 0; lv < LEVELS; lv++) {
if (s->head[lv] != NULL) {
Task *t = s->head[lv];
s->head[lv] = t->next;
if (s->head[lv] == NULL) s->tail[lv] = NULL;
t->next = NULL;
s->count--;
return t;
}
}
return NULL;
}
sched_next 는 2.3 의 dequeue 를 세 큐 중 비어 있지 않은 첫 큐에 적용한 것입니다. if (s->head[lv] == NULL) s->tail[lv] = NULL; 이 있죠? 2.3 에서 실험한 그 단골 버그를 여기서도 막고 있습니다. 노드를 free 하지 않고 돌려주는 점이 dequeue 와 다릅니다. 못 끝낸 작업은 sched_requeue 로 같은 큐의 꼬리에 다시 붙여야 하니까요.
실행 결과 (task_scheduler)
$ ./build/task_scheduler
작업 스케줄러 (타임 슬라이스 = 3)
=====================================
=== 작업 등록 ===
등록: 백업 (우선순위 3, 필요 시간 6)
등록: 컴파일 (우선순위 2, 필요 시간 5)
등록: 알림전송 (우선순위 1, 필요 시간 2)
등록: 로그정리 (우선순위 3, 필요 시간 3)
등록: 긴급패치 (우선순위 1, 필요 시간 4)
=== 실행 (선점형 라운드 로빈) ===
[t= 2] 알림전송 실행 2초 (남음 0) -> 완료! (대기 0턴)
대기열: [높음] 긴급패치(4남음) [보통] 컴파일(5남음) [낮음] 백업(6남음) 로그정리(3남음)
[t= 5] 긴급패치 실행 3초 (남음 1) -> 미완료, 대기열 뒤로
대기열: [높음] 긴급패치(1남음) [보통] 컴파일(5남음) [낮음] 백업(6남음) 로그정리(3남음)
[t= 6] 긴급패치 실행 1초 (남음 0) -> 완료! (대기 1턴)
대기열: [보통] 컴파일(5남음) [낮음] 백업(6남음) 로그정리(3남음)
[t= 9] 컴파일 실행 3초 (남음 2) -> 미완료, 대기열 뒤로
대기열: [보통] 컴파일(2남음) [낮음] 백업(6남음) 로그정리(3남음)
[t=11] 컴파일 실행 2초 (남음 0) -> 완료! (대기 3턴)
대기열: [낮음] 백업(6남음) 로그정리(3남음)
[t=14] 백업 실행 3초 (남음 3) -> 미완료, 대기열 뒤로
대기열: [낮음] 로그정리(3남음) 백업(3남음)
[t=17] 로그정리 실행 3초 (남음 0) -> 완료! (대기 6턴)
대기열: [낮음] 백업(3남음)
[t=20] 백업 실행 3초 (남음 0) -> 완료! (대기 6턴)
대기열: (비어 있음)
총 실행 시간: 20초
관찰 포인트:
1. 우선순위 1(알림전송, 긴급패치)이 등록 순서와 무관하게 먼저
2. 긴급패치(4초)는 슬라이스(3초)에 잘려 두 턴에 나눠 실행
3. 낮은 우선순위(백업)는 높은 것들이 끝나야 차례가 온다
(실제 OS는 굶주림(starvation) 방지를 위해 에이징을 쓴다)
우선순위 작업 스케줄러
세 가지를 관찰하세요.
- 백업이 가장 먼저 등록됐지만 가장 늦게 끝납니다. 우선순위 3 이라 위 두 큐가 빌 때까지 차례가 안 옵니다. 6턴이나 기다렸습니다. 실제 OS 라면 이렇게 굶는 작업의 우선순위를 시간이 갈수록 올려 주는 에이징(aging) 을 씁니다.
- 긴급패치는 4초짜리인데 슬라이스가 3초라
t=5에 잘리고, 큐 뒤로 갔다가t=6에 나머지 1초를 마칩니다. 이때 “높음” 큐에 자기 혼자라 바로 다시 실행됐습니다. t=14에서 백업이 잘려 큐 뒤로 가자, 대기열이로그정리 백업순서로 바뀌었습니다. 라운드 로빈이 같은 우선순위끼리 순서를 돌리는 모습입니다.
이름 열이 반듯한 데는 이유가 있습니다. printf("%-8s", 이름) 으로 찍으면 4주차와 8주차에서 봤듯이 바이트를 세기 때문에 백업(6바이트)과 알림전송(12바이트)의 폭이 달라져 열이 흔들립니다. 그래서 이 예제는 화면 칸 수를 세는 print_padded 함수를 씁니다(4.7절의 xmacro 와 같은 함수).
확장 아이디어: 에이징(대기 턴이 일정 이상이면 한 단계 위 큐로 옮기기), 작업 도착 시각(중간에 새 작업이 들어오는 상황), 평균 대기 시간 통계.
프로젝트 3: 브라우저 히스토리 (browser_history.c)
들어가며의 첫 질문으로 돌아갑니다. 뒤로 가기와 앞으로 가기의 정체는 스택 두 개입니다.
현재: blog.com
back 스택: [news.com, google.com] ← 뒤로 가면 여기서 pop
forward 스택: [ ] ← 앞으로 가면 여기서 pop
규칙은 세 가지입니다.
- 새 페이지 방문: 현재 페이지를 back 에 push 하고, forward 를 전부 비웁니다.
- 뒤로: 현재 페이지를 forward 에 push 하고, back 에서 pop 한 것이 현재가 됩니다.
- 앞으로: 현재 페이지를 back 에 push 하고, forward 에서 pop 한 것이 현재가 됩니다.
첫 규칙의 “forward 를 비운다”가 익숙한 그 동작입니다. 뒤로 갔다가 다른 페이지로 새로 가면, 원래 있던 앞으로 가기 기록이 사라지죠. 코드로는 한 줄입니다.
void browser_visit(Browser *b, const char *url) {
if (b->current[0] != '\0') {
us_push(&b->back, b->current); /* 현재를 back에 보관 */
}
us_clear(&b->forward); /* 앞으로 기록은 무효! */
snprintf(b->current, sizeof(b->current), "%s", url);
printf("방문: %s\n", b->current);
}
이 스택은 1.3 의 연결 리스트 스택인데, 원소가 int 가 아니라 문자열입니다. URL 은 길이가 제각각이라 노드마다 malloc 으로 딱 맞게 잡습니다(4주차의 문자열 복사, 7주차의 동적 할당).
typedef struct SNode {
char *url;
struct SNode *next;
} SNode;
int us_push(UrlStack *s, const char *url) {
SNode *node = malloc(sizeof(SNode));
if (node == NULL) return 0;
node->url = malloc(strlen(url) + 1);
if (node->url == NULL) {
free(node);
return 0;
}
strcpy(node->url, url);
node->next = s->top;
s->top = node;
s->size++;
return 1;
}
malloc 을 두 번 합니다. 노드 하나, 문자열 하나. 그래서 해제도 두 번입니다. 두 번째 malloc 이 실패하면 첫 번째 것을 되돌려야 하는 것도 보세요. 7주차에서 배운 “할당 실패 시 앞서 잡은 것 정리”입니다. strlen(url) + 1 의 + 1 은 4주차의 \0 자리입니다.
실행 결과 (browser_history)
대화형 프로그램이라 명령을 파이프로 넣어 돌렸습니다. > 뒤는 프로그램의 프롬프트이고, 실제 터미널에서는 그 뒤에 여러분이 친 명령이 보입니다.
$ printf 'v google.com\nv news.com\nv blog.com\nb\nb\nf\nv other.com\ns\nq\n' | ./build/browser_history
브라우저 히스토리 시스템 (h: 도움말)
=====================================
> 방문: google.com
> 방문: news.com
> 방문: blog.com
> 뒤로 -> news.com
> 뒤로 -> google.com
> 앞으로 -> news.com
> 방문: other.com
> 현재: other.com
back (2개): news.com google.com
forward (0개): (없음)
> 브라우저 종료
순서대로 따라가 봅시다.
| 명령 | 현재 | back (top 이 왼쪽) | forward |
|---|---|---|---|
v google.com |
google.com | ||
v news.com |
news.com | google.com | |
v blog.com |
blog.com | news.com google.com | |
b |
news.com | google.com | blog.com |
b |
google.com | news.com blog.com | |
f |
news.com | google.com | blog.com |
v other.com |
other.com | news.com google.com | (비움) ← blog.com 이 사라졌다 |
마지막 줄이 핵심입니다. news.com 에서 앞으로 가면 blog.com 이었는데, 대신 other.com 을 새로 방문하자 forward 가 비워져 blog.com 으로 갈 길이 없어졌습니다. us_clear(&b->forward) 한 줄의 결과입니다.
빈 스택에서 pop 하려 하면 어떻게 될까요? 이번 주 내내 지킨 규칙대로 거부합니다.
$ printf 'b\nf\nx\nv a.com\ns\nq\n' | ./build/browser_history
...
> 뒤로 갈 페이지가 없습니다
> 앞으로 갈 페이지가 없습니다
> 알 수 없는 명령: x (h: 도움말)
> 방문: a.com
> 현재: a.com
back (0개): (없음)
forward (0개): (없음)
> 브라우저 종료
종료할 때 두 스택을 모두 비우니 누수가 없습니다. make memcheck 가 이 프로그램을 포함해 동적 할당을 쓰는 다섯 프로그램을 Valgrind 로 검사합니다. 이번 주 전부 ERROR SUMMARY: 0 errors, in use at exit: 0 bytes 입니다.
확장 아이디어: 히스토리 최대 개수 제한. back 이 100개를 넘으면 가장 오래된 것(스택의 바닥)을 버려야 하는데, 스택은 바닥을 건드릴 수 없습니다. 양쪽 끝을 다루는 3절의 덱이 답입니다. 그 밖에 방문 횟수 통계, 9주차 파일 입출력으로 히스토리를 파일에 저장하고 불러오기.
6. 자주 하는 실수와 함정
이번 주에 직접 일으켜 본 것들입니다. 각 항목의 절 번호로 돌아가면 실제 화면이 있습니다.
- 빈 스택이나 큐에서 pop. (1.2)
size_t가 0 에서 1 을 빼면 18446744073709551615 로 감아 돌아 범위 밖을 읽습니다. 모든 pop 과 dequeue 는 성공 여부를 반환값으로 알리고, 부르는 쪽은 반환값을 확인합니다.while (stack_pop(&s, &v))가 관용구입니다. -
리스트 스택 push 의 두 줄 순서. (1.3)
s->top = node를 먼저 하면node->next = s->top이 자기 자신을 가리켜 무한 고리가 됩니다. “새 노드가 먼저 기존 것을 붙잡고, 그다음 머리를 옮긴다.” -
연결 리스트 큐의 tail 정리 누락. (2.3) 마지막 노드를 dequeue 할 때 tail 도
NULL로. 안 하면 다음 enqueue 가 해제된 메모리에 쓰고, 그냥 실행하면 아무 일 없는 것처럼 보입니다. Valgrind 와 AddressSanitizer 가 43번째 줄을 짚어 줍니다. -
원형 버퍼에서
%빼먹기. (2.2)data[5]에 쓴 값이 바로 뒤의front를 덮어써서front=60이 됐습니다. AddressSanitizer 도 구조체 안의 넘침은 못 잡습니다. 인덱스 계산마다% CAPACITY. -
음수 모듈로. (3.2)
(front - 1) % cap은int면 -1,size_t면 용량이 2의 거듭제곱일 때만 우연히 맞습니다.(front + cap - 1) % cap으로. -
가득 참과 빈 것 구분. (2.2)
front == rear만으로는 둘이 같아 보입니다.count를 따로 두거나 한 칸을 비워 둡니다. -
후위 계산의 피연산자 순서. (프로젝트 1) 먼저 pop 한 것이 오른쪽 피연산자입니다. 덧셈만 테스트하면 이 버그가 안 보이니
10 - 2로 확인하세요. -
매크로 인자에 부작용. (4.3)
MAX(i++, 3)은i를 두 번 늘립니다. 대문자 이름은 “부작용 넣지 말 것”이라는 표지판입니다. -
여러 문장 매크로를
if뒤에. (4.4) 첫 문장만if에 묶이고 나머지는 항상 실행됩니다.do { } while (0)으로 감싸고,-Wmultistatement-macros경고를 무시하지 마세요. -
한글이 섞인 표에
%-8s. (프로젝트 2, 4.7) 바이트를 세서 열이 어긋납니다. 화면 칸 수를 세는 함수를 쓰거나, 4주차처럼 직접 공백을 맞춥니다.
마치며
이번 주에 배운 것을 한 줄씩 정리하면 이렇습니다.
- 스택: LIFO. 한쪽 끝만 쓰니 push 와 pop 이 O(1). 동적 배열의
size가 곧 top. 괄호 검사, 함수 호출, 실행 취소, 뒤로 가기. - 큐: FIFO. 원형 배열은
%로 감아 돌고,count로 가득 참을 구분. 리스트 큐는 head 와 tail, 그리고 마지막 dequeue 의 tail 정리. 버퍼와 대기열의 자료구조. - 우선순위 큐: 급한 순서. 정렬 삽입은 O(n), 안정성은
<=한 글자. 다음 주 힙으로 O(log n). - 덱: 양쪽이 열려 스택도 큐도 됨. 앞에 넣을 때
(front + cap - 1) % cap. - 매크로: 텍스트 치환. 괄호, 이중 평가, 여러 문장이라는 세 함정.
#과##으로 함수가 못 하는 일을 하고,DEFINE_STACK(T)로 타입 안전한 코드를 찍어내며, X-매크로로 목록을 한 곳에만 둔다.
지난주의 벽돌(배열, 리스트)로 이번 주에 방 세 개(스택, 큐, 덱)를 지었고, 그 방으로 계산기, 스케줄러, 브라우저를 만들었습니다. 자료구조를 배운다는 것은 이런 것입니다. 아래층이 튼튼하면 위층은 조립입니다. 그리고 이번 주에 가장 많이 한 일은 새 코드를 쓰는 것이 아니라, 잘 되는 코드를 일부러 망가뜨려 보는 것이었습니다. % 를 빼고, tail = NULL 을 지우고, 두 줄의 순서를 바꾸고, <= 를 < 로 고쳐 봤습니다. 버그가 어떻게 생기는지 손으로 만들어 본 사람은 그 버그를 다시 만들지 않습니다.
다음 주는 드디어 2차원으로 갑니다. 한 줄로 서 있던 데이터가 가지를 치기 시작하는 트리(tree) 입니다. 오늘 만든 스택이 트리 순회에서, 우선순위 큐가 힙에서 그대로 다시 등장합니다.
체크리스트
각 항목을 설명할 수 있으면 체크합니다.
- [ ] push, pop, peek 를 배열과 리스트 두 방식으로 구현할 수 있다
- [ ] 배열 스택에서
size가 개수이자 다음 자리인 이유를 안다 - [ ] 빈 스택 pop 을 반환값으로 거부하게 만들었고, 검사를 빼면 무슨 일이 나는지 안다
- [ ] 리스트 스택 push 의 두 줄 순서를 바꾸면 왜 무한 고리가 되는지 그림으로 설명할 수 있다
- [ ] 괄호 검사가 왜 큐가 아니라 스택 문제인지
([)]로 설명할 수 있다 - [ ] 함수 호출 스택과 스택 오버플로(종료 코드 139)를 설명할 수 있다
- [ ] 재귀를 명시적 스택과 반복문으로 바꿀 수 있다는 것을 이해했다
- [ ] 원형 큐의 front, count, rear 를 표로 추적할 수 있다
- [ ]
%를 빼면 옆 멤버를 덮어쓰는 것을 확인했고, 왜 AddressSanitizer 가 못 잡는지 안다 - [ ] 리스트 큐의 tail 정리를 빼고 Valgrind 로 해제 후 사용을 잡아 봤다
- [ ] 우선순위 큐의 정렬 삽입과 안정성(
<=)을 이해했다 - [ ] 버퍼가 일시적 폭주는 흡수하지만 평균 초과는 못 막는 이유를 안다
- [ ] 덱의 음수 방지 트릭
(i + cap - 1) % cap을 쓸 수 있고,size_t에서도 필요한 이유를 안다 - [ ] 매크로 3대 함정(괄호, 이중 평가, 여러 문장)을
gcc -E로 확인해 봤다 - [ ]
do { } while (0)패턴의 목적을 설명할 수 있다 - [ ]
DEFINE_STACK같은 코드 생성 매크로를 읽을 수 있고, 잘못된 타입을 넣었을 때의 경고를 봤다 - [ ] X-매크로가 해결하는 문제(목록 중복)를 알고, 항목 하나를 추가해 봤다
- [ ] 세 프로젝트를 빌드하고
make memcheck로 누수 0 을 확인했다 - [ ] (도전) 계산기에
^연산자를, 히스토리에 개수 제한을 추가해 봤다
참고 자료
- The C Programming Language (K&R) 4.3절 — 역폴란드 계산기. 이번 주 프로젝트 1의 원조입니다.
- Shunting yard algorithm (Wikipedia)
- cppreference — _Generic
- X Macro (Wikipedia)
- 다음 주차: 12주차 트리 구조 구현 (이진 탐색 트리, AVL, 힙)