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

Cấu trúc dữ liệu Stack

Stack chỉ thao tác ở top: push thêm, pop xóa và peek đọc phần tử mới nhất.

Cấu trúc dữ liệu Stack là gì?

Stack chỉ thao tác ở top: push thêm, pop xóa và peek đọc phần tử mới nhất.

Cài đặt operation last-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++

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);
}
Output dự kiến
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();
}
Output dự kiến
20

So sánh C và C++

C fixed-capacity phải kiểm tra overflow/underflow; std::stack quản lý capacity qua underlying container.

C

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.