Quản lý bộ nhớ và cấu trúc dữ liệu

Tổng quan về Memory Layout

Bộ nhớ trong chương trình được tổ chức thành các vùng khác nhau, mỗi vùng có mục đích và đặc điểm riêng:

+-------------------+ Địa chỉ cao (0xFFFFFFFF)
|      Stack        | ← LIFO, tự động quản lý
|        ↓          |   (biến cục bộ, tham số)
|                   |
|   Free Memory     |
|                   |
|        ↑          |
|      Heap         | ← Cấp phát động
+-------------------+
|   Static/Global   | ← Biến toàn cục, static
+-------------------+
|   Code Segment    | ← Mã chương trình
+-------------------+ Địa chỉ thấp (0x00000000)

---

Vùng nhớ Stack

Stack là vùng nhớ được quản lý tự động, hoạt động theo nguyên tắc LIFO (Last In, First Out).

Đặc điểm của Stack

• Tự động quản lý: Hệ thống tự động cấp phát và giải phóng bộ nhớ
• Tốc độ cao: Rất nhanh, chỉ cần di chuyển con trỏ stack pointer
• Kích thước hạn chế: Thường từ 1-8MB (tùy hệ thống)
• An toàn: Không có memory leak
• Cấu trúc LIFO: Phần tử cuối cùng được thêm vào sẽ được lấy ra đầu tiên

Stack được sử dụng để lưu trữ:

• Biến cục bộ (local variables)
• Tham số hàm (function parameters)
• Địa chỉ trả về (return addresses)
• Thanh ghi được lưu trữ khi gọi hàm

Ví dụ hoạt động của Stack:

void function3() {
    int z = 30;  // z được push vào stack
    printf("In function3: z = %d\n", z);
}  // z được pop khỏi stack

void function2() {
    int y = 20;  // y được push vào stack
    function3(); // địa chỉ trả về được push
    printf("In function2: y = %d\n", y);
}  // y được pop khỏi stack

void function1() {
    int x = 10;  // x được push vào stack
    int arr[100]; // mảng 400 bytes được push
    function2();  // địa chỉ trả về được push
    printf("In function1: x = %d\n", x);
}  // x và arr được pop khỏi stack

int main() {
    function1();
    return 0;
}

Minh họa Stack Operations:

Bước 1: Gọi function1()
Stack: [main_vars][return_addr][x=10][arr[100]]

Bước 2: Gọi function2() từ function1()  
Stack: [main_vars][return_addr][x=10][arr[100]][return_addr][y=20]

Bước 3: Gọi function3() từ function2()
Stack: [main_vars][return_addr][x=10][arr[100]][return_addr][y=20][return_addr][z=30]

Bước 4: function3() kết thúc
Stack: [main_vars][return_addr][x=10][arr[100]][return_addr][y=20]

Bước 5: function2() kết thúc  
Stack: [main_vars][return_addr][x=10][arr[100]]

Bước 6: function1() kết thúc
Stack: [main_vars]

Stack Overflow

Stack Overflow xảy ra khi stack đầy do:

// Đệ quy vô hạn
void recursiveFunction() {
    int localVar = 42;
    recursiveFunction(); // Không có điều kiện dừng!
}

// Mảng quá lớn
void hugeArray() {
    int bigArray[10000000]; // 40MB - vượt quá stack size!
}

---

Vùng nhớ Heap

Heap là vùng nhớ dành cho việc cấp phát bộ nhớ động (dynamic memory allocation).

Đặc điểm của Heap

• Quản lý thủ công: Lập trình viên phải tự cấp phát và giải phóng
• Tốc độ chậm hơn: Phải tìm kiếm vùng trống phù hợp
• Kích thước lớn: Giới hạn bởi bộ nhớ hệ thống (RAM + Virtual Memory)
• Linh hoạt: Có thể cấp phát bất kỳ kích thước nào
• Rủi ro: Memory leak nếu không giải phóng đúng cách

Heap được sử dụng để:

• Cấp phát bộ nhớ động cho objects
• Mảng có kích thước không biết trước
• Cấu trúc dữ liệu lớn (trees, graphs)
• Objects có lifetime dài hơn scope của function

Ví dụ sử dụng Heap:

#include <stdlib.h>
#include <stdio.h>

void heapExample() {
    // Cấp phát bộ nhớ động trên heap
    int *ptr = malloc(sizeof(int) * 1000);  // 4000 bytes

    if (ptr == NULL) {
        printf("Không thể cấp phát bộ nhớ!\n");
        return;
    }

    // Sử dụng bộ nhớ
    for (int i = 0; i < 1000; i++) {
        ptr[i] = i * i;
    }

    // In một số giá trị
    printf("ptr[100] = %d\n", ptr[100]);

    // QUAN TRỌNG: Phải giải phóng bộ nhớ
    free(ptr);
    ptr = NULL; // Tránh dangling pointer
}

// Ví dụ với struct
typedef struct {
    char name[50];
    int age;
    float salary;
} Employee;

Employee* createEmployee(const char* name, int age, float salary) {
    Employee* emp = malloc(sizeof(Employee));
    if (emp != NULL) {
        strcpy(emp->name, name);
        emp->age = age;
        emp->salary = salary;
    }
    return emp; // Trả về pointer, object vẫn tồn tại trên heap
}

void useEmployee() {
    Employee* emp = createEmployee("John Doe", 30, 50000.0);

    if (emp != NULL) {
        printf("Employee: %s, Age: %d, Salary: %.2f\n", 
               emp->name, emp->age, emp->salary);
        free(emp); // Giải phóng bộ nhớ
    }
}

Memory Leak và Dangling Pointer:

// MEMORY LEAK - Rò rỉ bộ nhớ
void memoryLeak() {
    int *ptr = malloc(sizeof(int) * 100);
    // Quên gọi free(ptr) - Memory leak!
    // Bộ nhớ không được trả lại cho hệ thống
}

// DANGLING POINTER - Con trỏ lơ lửng
void danglingPointer() {
    int *ptr = malloc(sizeof(int));
    *ptr = 42;
    free(ptr);
    // ptr vẫn trỏ đến vùng nhớ đã giải phóng

    printf("%d\n", *ptr); // NGUY HIỂM! Undefined behavior

    ptr = NULL; // Nên gán NULL sau free
}

---

LIFO (Last In, First Out) - Stack

Stack là cấu trúc dữ liệu hoạt động theo nguyên tắc LIFO - phần tử cuối cùng được thêm vào sẽ được lấy ra đầu tiên.

Minh họa Stack Operations:

Stack rỗng:  []

Push 10:     [10]     ← Top
Push 20:     [20]     ← Top
             [10]

Push 30:     [30]     ← Top  
             [20]
             [10]

Pop():       [20]     ← Top (lấy ra 30)
             [10]

Pop():       [10]     ← Top (lấy ra 20)

Pop():       []       (lấy ra 10)

Implement Stack bằng Array:

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int top;
} Stack;

// Khởi tạo stack
void initStack(Stack* s) {
    s->top = -1;
}

// Kiểm tra stack rỗng
int isEmpty(Stack* s) {
    return s->top == -1;
}

// Kiểm tra stack đầy
int isFull(Stack* s) {
    return s->top == MAX_SIZE - 1;
}

// Push element vào stack
int push(Stack* s, int value) {
    if (isFull(s)) {
        printf("Stack overflow!\n");
        return 0;
    }
    s->data[++s->top] = value;
    return 1;
}

// Pop element từ stack
int pop(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack underflow!\n");
        return -1;
    }
    return s->data[s->top--];
}

// Peek top element
int peek(Stack* s) {
    if (isEmpty(s)) {
        printf("Stack is empty!\n");
        return -1;
    }
    return s->data[s->top];
}

Ứng dụng của Stack (LIFO):

1. Call Stack - Quản lý lời gọi hàm
2. Undo/Redo operations - Hoàn tác thao tác
3. Expression evaluation - Tính toán biểu thức
4. DFS (Depth-First Search) - Duyệt đồ thị theo chiều sâu
5. Browser history - Lịch sử trình duyệt
6. Parsing - Phân tích cú pháp

Ví dụ ứng dụng - Kiểm tra dấu ngoặc:

int isValidParentheses(char* str) {
    Stack s;
    initStack(&s);

    for (int i = 0; str[i] != '\0'; i++) {
        char ch = str[i];

        // Push opening brackets
        if (ch == '(' || ch == '[' || ch == '{') {
            push(&s, ch);
        }
        // Check closing brackets
        else if (ch == ')' || ch == ']' || ch == '}') {
            if (isEmpty(&s)) return 0; // Unmatched closing

            char top = pop(&s);
            if ((ch == ')' && top != '(') ||
                (ch == ']' && top != '[') ||
                (ch == '}' && top != '{')) {
                return 0; // Mismatched
            }
        }
    }

    return isEmpty(&s); // All brackets should be matched
}

// Test
printf("%d\n", isValidParentheses("()[]{}"));     // 1 (valid)
printf("%d\n", isValidParentheses("([{}])"));     // 1 (valid)  
printf("%d\n", isValidParentheses("([)]"));       // 0 (invalid)

---

FIFO (First In, First Out) - Queue

Queue là cấu trúc dữ liệu hoạt động theo nguyên tắc FIFO - phần tử đầu tiên được thêm vào sẽ được lấy ra đầu tiên.

Minh họa Queue Operations:

Queue rỗng:  []

Enqueue 10:  [10]
             ↑
           Front/Rear

Enqueue 20:  [10][20]
             ↑    ↑
           Front Rear

Enqueue 30:  [10][20][30]
             ↑         ↑
           Front      Rear

Dequeue:     [20][30]     (lấy ra 10)
             ↑    ↑
           Front Rear

Dequeue:     [30]         (lấy ra 20)
             ↑
           Front/Rear

Dequeue:     []           (lấy ra 30)

Implement Queue bằng Array (Circular Queue):

#define MAX_SIZE 100

typedef struct {
    int data[MAX_SIZE];
    int front;
    int rear;
    int size;
} Queue;

// Khởi tạo queue
void initQueue(Queue* q) {
    q->front = 0;
    q->rear = -1;
    q->size = 0;
}

// Kiểm tra queue rỗng
int isEmptyQueue(Queue* q) {
    return q->size == 0;
}

// Kiểm tra queue đầy
int isFullQueue(Queue* q) {
    return q->size == MAX_SIZE;
}

// Enqueue - thêm element vào cuối queue
int enqueue(Queue* q, int value) {
    if (isFullQueue(q)) {
        printf("Queue overflow!\n");
        return 0;
    }

    q->rear = (q->rear + 1) % MAX_SIZE; // Circular
    q->data[q->rear] = value;
    q->size++;
    return 1;
}

// Dequeue - lấy element từ đầu queue
int dequeue(Queue* q) {
    if (isEmptyQueue(q)) {
        printf("Queue underflow!\n");
        return -1;
    }

    int value = q->data[q->front];
    q->front = (q->front + 1) % MAX_SIZE; // Circular
    q->size--;
    return value;
}

// Peek front element
int front(Queue* q) {
    if (isEmptyQueue(q)) {
        printf("Queue is empty!\n");
        return -1;
    }
    return q->data[q->front];
}

Ứng dụng của Queue (FIFO):

1. Hàng đợi in ấn - Print queue
2. Buffer trong streaming - Video/Audio buffering
3. BFS (Breadth-First Search) - Duyệt đồ thị theo chiều rộng
4. Task scheduling - Xếp hàng công việc
5. Handling requests - Web server requests
6. Simulation - Mô phỏng hàng đợi

Ví dụ ứng dụng - BFS Algorithm:

#include <stdbool.h>

// Graph representation (adjacency list)
typedef struct Node {
    int vertex;
    struct Node* next;
} Node;

typedef struct {
    Node* head;
} AdjList;

typedef struct {
    int V; // số đỉnh
    AdjList* array;
} Graph;

void BFS(Graph* graph, int startVertex) {
    bool visited[graph->V];
    for (int i = 0; i < graph->V; i++)
        visited[i] = false;

    Queue q;
    initQueue(&q);

    // Bắt đầu từ startVertex
    visited[startVertex] = true;
    enqueue(&q, startVertex);

    printf("BFS traversal: ");

    while (!isEmptyQueue(&q)) {
        int currentVertex = dequeue(&q);
        printf("%d ", currentVertex);

        // Duyệt tất cả đỉnh kề
        Node* temp = graph->array[currentVertex].head;
        while (temp) {
            int adjVertex = temp->vertex;
            if (!visited[adjVertex]) {
                visited[adjVertex] = true;
                enqueue(&q, adjVertex);
            }
            temp = temp->next;
        }
    }
    printf("\n");
}

---

So sánh Stack vs Heap

Aspect	Stack	Heap
Quản lý	Tự động	Thủ công
Tốc độ	Rất nhanh	Chậm hơn
Kích thước	Hạn chế (MB)	Lớn (GB)
Allocation	Compile time	Runtime
Deallocation	Tự động	Manual (free/delete)
Memory leak	Không	Có thể xảy ra
Fragmentation	Không	Có thể xảy ra
Thread safety	Thread-specific	Shared

So sánh LIFO vs FIFO

Aspect	LIFO (Stack)	FIFO (Queue)
Nguyên tắc	Last In, First Out	First In, First Out
Insertion	Top (push)	Rear (enqueue)
Deletion	Top (pop)	Front (dequeue)
Use cases	Undo/Redo, Call stack	Print queue, BFS
Memory pattern	Người cuối đến, ra trước	Người đầu đến, ra trước
Real-world analogy	Chồng đĩa	Hàng đợi ngân hàng

---

Best Practices

Stack Management:

• Tránh mảng quá lớn trên stack
• Kiểm soát độ sâu đệ quy để tránh stack overflow
• Sử dụng heap cho data structures lớn

Heap Management:

• Luôn luôn free() sau malloc()
• Set pointer = NULL sau free()
• Kiểm tra return value của malloc()
• Sử dụng valgrind để detect memory leaks

Data Structure Choice:

• Stack (LIFO) cho: Function calls, expression parsing, undo operations
• Queue (FIFO) cho: Task scheduling, BFS, buffering, request handling

Nhớ rằng: Hiểu rõ memory management và data structures là nền tảng của lập trình hiệu quả và an toàn!