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

Hàng đợi vòng (circular queue) trong C, C++

Trong bài học này, bạn sẽ cài đặt hàng đợi theo nguyên tắc vào trước, ra trước bằng mảng vòng trong C và std::queue trong C++.

Giới thiệu

Hàng đợi (queue) hoạt động theo nguyên tắc vào trước, ra trước (FIFO). Nếu cài đặt bằng mảng thông thường, mỗi lần lấy phần tử ra ta phải dịch các phần tử còn lại lên. Hàng đợi vòng (circular buffer) khắc phục điều này bằng cách quay vòng chỉ số và tái sử dụng những vị trí đã được giải phóng.

Những điểm quan trọng

Xác định những điều kiện luôn phải đúng (invariant) của cấu trúc dữ liệu trước khi viết các thao tác.
Xử lý đầy đủ các trường hợp rỗng, đầy và cấp phát bộ nhớ thất bại.
Đánh giá cả độ phức tạp lẫn cách quản lý vùng nhớ của từng thao tác.

Xem cách hoạt động

Enqueue và dequeue để thấy các phần tử rời đi đúng theo thứ tự chúng đến.

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

Kết quả khi chạy

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

Kết quả khi chạy

So sánh C và C++

Hàng đợi trong C lưu vị trí đầu hàng head và số phần tử size. Vị trí của phần tử mới được tính bằng phép chia lấy dư (head + size) % 4, nên khi đến cuối mảng, chỉ số tự quay về đầu. Trong C++, std::queue là một bộ chuyển đổi container (container adapter) cung cấp sẵn các thao tác front, push và pop.

Dữ liệu (struct) và các thao tác thường tách rời, bộ nhớ được cấp phát và giải phóng thủ công.

C++

Class và container có thể tự bảo vệ tính đúng đắn của dữ liệu và tự quản lý tài nguyên.

Bài tập mở rộng

Hãy chạy cả hai phiên bản, sau đó thử thay đổi code để quan sát sự khác biệt về mức độ an toàn mà mỗi ngôn ngữ mang lại.

Thêm kiểm thử cho trạng thái rỗng và khi đạt giới hạn dung lượng.
Viết phần giải phóng bộ nhớ và kiểm tra rò rỉ bộ nhớ.
So sánh độ phức tạp với container tương ứng của thư viện chuẩn.

Luyện tập với thử thách

Áp dụng kiến thức của bài học này để giải một bài toán thực tế. Mỗi thử thách chạy ngay trên trình duyệt, có kiểm thử tức thì và AI nhận xét.

Course Schedule Order Order courses so every prerequisite comes first. Khó

Tất cả thử thách