Cấu trúc dữ liệu trong C/C++

Circular Queue

Circular buffer tái sử dụng vị trí đã lấy ra thay vì dịch toàn bộ phần tử.

Circular Queue là gì?

Circular buffer tái sử dụng vị trí đã lấy ra thay vì dịch toàn bộ phần tử.

Cài đặt xử lý first-in, first-out.

Điểm quan trọng

Xác định invariant trước khi cài đặt operation.
Xử lý trường hợp rỗng, đầy và cấp phát thất bại.
Đánh giá đồng thời complexity và ownership.

Code ví dụ bằng C và C++

Chạy code →

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);
}

Output dự kiến

C++

Chạy code →

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();
}

Output dự kiến

So sánh C và C++

Queue C theo dõi head và size rồi wrap bằng modulo; std::queue cung cấp front, push và pop.

Struct và operation thường tách rời, cấp phát được quản lý thủ công.

C++

Class và container có thể bảo vệ invariant và tự quản lý tài nguyên.

Bài tập mở rộng

Chạy cả hai phiên bản rồi thay đổi để quan sát khác biệt về bảo đảm của từng ngôn ngữ.

Thêm test cho trạng thái rỗng và capacity boundary.
Cài đặt cleanup rồi kiểm tra memory leak.
So sánh complexity với standard container.