C/C++ 자료 구조

C와 C++의 원형 큐(circular queue)

이 레슨에서는 C의 원형 배열과 C++의 std::queue로 먼저 들어온 것이 먼저 나가는 큐를 구현합니다.

소개

큐(queue)는 먼저 들어온 것이 먼저 나가는 FIFO 규칙을 따릅니다. 일반 배열을 쓰면 요소를 꺼낼 때마다 남은 요소를 앞으로 옮겨야 합니다. 원형 큐(circular buffer)는 인덱스가 처음으로 돌아가게 하고 빈자리를 다시 써서 이 문제를 해결합니다.

핵심 정리

연산을 작성하기 전에 항상 참이어야 하는 조건(불변식)을 정하세요.
구조가 비어 있을 때, 가득 찼을 때, 메모리 할당에 실패했을 때를 처리하세요.
각 연산의 복잡도와 메모리 관리를 함께 따져 보세요.

동작 원리 보기

enqueue와 dequeue를 해 보면 항목이 들어온 순서대로 나간다는 것을 알 수 있습니다.

C와 C++ 코드 예제

실행 →

main.c

#include <stdio.h>

typedef struct {
    int data[4];
    int head;
    int size;
} Queue;

int push(Queue *queue, int value) {
    if (queue->size == 4) return 0;
    int tail = (queue->head + queue->size) % 4;
    queue->data[tail] = value;
    ++queue->size;
    return 1;
}

int pop(Queue *queue, int *value) {
    if (queue->size == 0) return 0;
    *value = queue->data[queue->head];
    queue->head = (queue->head + 1) % 4;
    --queue->size;
    return 1;
}

int main(void) {
    Queue queue = {{0}, 0, 0};
    int value;
    push(&queue, 7);
    push(&queue, 9);
    pop(&queue, &value);
    printf("%d\n", value);
}

실행 결과

C++

실행 →

main.cpp

#include <iostream>
#include <queue>

int main() {
    std::queue<int> values;
    values.push(7);
    values.push(9);
    std::cout << values.front() << '\n';
    values.pop();
}

실행 결과

C와 C++ 비교

C의 큐는 맨 앞 위치 head와 요소 수 size를 기억합니다. 새 요소의 위치는 나머지 연산 (head + size) % 4로 계산하므로, 배열 끝에 이르면 인덱스가 자동으로 처음으로 돌아갑니다. C++의 std::queue는 front, push, pop 연산을 바로 제공하는 컨테이너 어댑터(container adapter)입니다.

데이터(struct)와 연산이 분리되어 있고, 메모리는 직접 할당하고 해제합니다.

C++

클래스와 컨테이너가 데이터의 일관성을 지키고 자원을 스스로 관리합니다.

연습 문제

두 버전을 모두 실행한 다음 코드를 바꿔 보면서 각 언어가 주는 안전성의 차이를 살펴보세요.

비어 있는 상태와 최대 용량에 이른 순간에 대한 테스트를 추가해 보세요.
메모리 해제 코드를 작성하고 누수가 없는지 확인해 보세요.
표준 라이브러리의 같은 역할을 하는 컨테이너와 복잡도를 비교해 보세요.

챌린지로 연습하기

이 레슨에서 배운 내용으로 실제 문제를 풀어 보세요. 모든 챌린지는 브라우저에서 실행되며 즉시 테스트와 AI 리뷰를 받을 수 있습니다.

Course Schedule Order Order courses so every prerequisite comes first. 어려움

모든 챌린지