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

Cấu trúc dữ liệu stack (ngăn xếp) trong C, C++

Trong bài học này, bạn sẽ cài đặt các thao tác của stack theo nguyên tắc vào sau, ra trước bằng mảng cố định trong C và std::stack trong C++.

Giới thiệu

Stack (ngăn xếp) chỉ cho phép thao tác ở đỉnh: push thêm phần tử mới vào đỉnh, pop lấy phần tử ở đỉnh ra, còn peek xem phần tử ở đỉnh mà không lấy ra. Stack hoạt động theo nguyên tắc vào sau, ra trước (LIFO), giống như một chồng sách.

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

Push và pop để thấy phần tử vào sau cùng luôn ra trước tiên.

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

C
Chạy code →
main.c
#include <stdio.h>

typedef struct {
    int data[8];
    int size;
} Stack;

int push(Stack *stack, int value) {
    if (stack->size == 8) return 0;
    stack->data[stack->size++] = value;
    return 1;
}

int pop(Stack *stack, int *value) {
    if (stack->size == 0) return 0;
    *value = stack->data[--stack->size];
    return 1;
}

int main(void) {
    Stack stack = {{0}, 0};
    int value;
    push(&stack, 10);
    push(&stack, 20);
    pop(&stack, &value);
    printf("%d\n", value);
}
Kết quả khi chạy
20
C++
Chạy code →
main.cpp
#include <iostream>
#include <stack>

int main() {
    std::stack<int> values;
    values.push(10);
    values.push(20);
    std::cout << values.top() << '\n';
    values.pop();
}
Kết quả khi chạy
20

So sánh C và C++

Phiên bản C dùng mảng cố định 8 phần tử, nên phải kiểm tra trường hợp stack đã đầy khi push (tràn ngăn xếp) và trường hợp stack rỗng khi pop. Trong C++, std::stack tự quản lý dung lượng thông qua container bên dưới và cung cấp cùng các thao tác push, pop, top theo nguyên tắc LIFO.

C

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.

Tất cả thử thách