Khái niệm và nguyên lý cơ bản

Ngăn xếp (stack) là một cấu trúc dữ liệu tuyến tính hoạt động theo nguyên tắc "vào sau - ra trước" (LIFO - Last In, First Out). Các thao tác chèn và xóa phần tử chỉ xảy ra ở một đầu gọi là đỉnh ngăn xếp (top). Đầu còn lại được gọi là đáy (bottom). Khi ngăn xếp không chứa phần tử nào, ta gọi là ngăn xếp rỗng.

Ví dụ thực tiễn

• Chồng bát đĩa: Bát mới rửa luôn được đặt lên trên cùng (push), và khi lấy bát cũng chỉ lấy từ trên xuống (pop)
• Lịch sử duyệt web: Khi nhấn nút "Back" trên trình duyệt, trang mới nhất sẽ được đóng trước

Các thao tác cơ bản

• Push: Thêm phần tử vào đỉnh ngăn xếp
• Pop: Xóa phần tử khỏi đỉnh ngăn xếp
• Top: Lấy giá trị phần tử ở đỉnh ngăn xếp
• IsEmpty: Kiểm tra ngăn xếp có rỗng không

Lựa chọn cấu trúc底层

Ngăn xếp có thể được cài đặt bằng mảng (danh sách tuần tự) hoặc danh sách liên kết. Tuy nhiên, sử dụng mảng mang lại hiệu suất tốt hơn do các thao tác thêm/xóa đều có độ phức tạp O(1).

Cài đặt bằng ngôn ngữ C

File khai báo (stack.h)

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

typedef int ElementType;
typedef struct {
    ElementType* data;
    int topIndex;
    int capacity;
} Stack;

// Khởi tạo và giải phóng
void InitStack(Stack* s);
void FreeStack(Stack* s);

// Thao tác cơ bản
void Push(Stack* s, ElementType value);
void Pop(Stack* s);
ElementType Top(const Stack* s);
bool IsEmpty(const Stack* s);
int Size(const Stack* s);

File triển khai (stack.c)

#include "stack.h"

void InitStack(Stack* s) {
    s->data = NULL;
    s->topIndex = 0;
    s->capacity = 0;
}

void FreeStack(Stack* s) {
    if (s->data) free(s->data);
    s->data = NULL;
    s->topIndex = s->capacity = 0;
}

void Push(Stack* s, ElementType value) {
    assert(s);
    
    if (s->topIndex == s->capacity) {
        int newCapacity = s->capacity == 0 ? 4 : s->capacity * 2;
        ElementType* newData = (ElementType*)realloc(s->data, newCapacity * sizeof(ElementType));
        
        if (!newData) {
            perror("Không đủ bộ nhớ");
            exit(EXIT_FAILURE);
        }
        
        s->data = newData;
        s->capacity = newCapacity;
    }
    
    s->data[s->topIndex++] = value;
}

void Pop(Stack* s) {
    assert(s && !IsEmpty(s));
    s->topIndex--;
}

ElementType Top(const Stack* s) {
    assert(s && !IsEmpty(s));
    return s->data[s->topIndex - 1];
}

bool IsEmpty(const Stack* s) {
    return s->topIndex == 0;
}

int Size(const Stack* s) {
    return s->topIndex;
}

Ứng dụng phổ biến

• Quản lý bộ nhớ trong quá trình thực thi chương trình
• Xử lý biểu thức toán học và chuyển đổi giữa các dạng biểu thức
• Hỗ trợ chức năng "Undo-Redo" trong các ứng dụng chỉnh sửa
• Phân tích cú pháp trong các trình biên dịch