C/C++ 자료 구조

원형 Queue

Circular buffer는 요소를 이동하지 않고 빈 위치를 재사용합니다.

원형 Queue이란?

Circular buffer는 요소를 이동하지 않고 빈 위치를 재사용합니다.

First-in-first-out 처리를 구현합니다.

중요한 점

연산 전에 invariant를 정의하세요.
비어 있음, 가득 참, 할당 실패를 처리하세요.
시간 복잡도와 ownership을 함께 평가하세요.

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를 modulo로 관리하고 std::queue는 front, push, pop을 제공합니다.

구조체와 연산이 분리되고 할당이 명시적입니다.

C++

Class와 container가 invariant와 resource를 관리합니다.

연습 문제

두 버전을 실행하고 수정하여 각 언어의 보장을 관찰하세요.

빈 상태와 용량 경계를 테스트하세요.
Cleanup을 구현하고 leak을 확인하세요.
Standard container와 비교하세요.