Ngăn xếp và hàng đợi là hai cấu trúc tuyến tính đặc biệt, khác với danh sách thông thường cho phép chèn/xóa tại bất kỳ vị trí nào, cả hai chỉ cho phép thao tác tại các đầu cố định.

Ngăn xếp (Stack) tuân theo nguyên tắc FIFO ngược — LIFO (Last In, First Out): phần tử được thêm vào cuối cùng sẽ được lấy ra đầu tiên. Trong một ngăn xếp:

• Đỉnh ngăn xếp (top): vị trí duy nhất cho phép chèn (push) và loại bỏ (pop).
• Đáy ngăn xếp (bottom): đầu cố định, không thay đổi trong suốt vòng đời.

Dựa trên cách quản lý bộ nhớ và hướng mở rộng, ngăn xếp có thể phân loại thành: ngăn xếp tăng khi rỗng (empty-increasing), giảm khi rỗng (empty-decreasing), tăng khi đầy (full-increasing), hoặc giảm khi đầy (full-decreasing).

Khai báo cấu trúc ngăn xếp tuần tự

typedef int Element;
typedef struct {
    Element *buffer;
    size_t capacity;
    size_t size;
} ArrayStack;

Hàm khởi tạo ngăn xếp động

ArrayStack* stack_create(size_t max_size) {
    if (max_size == 0) return NULL;

    ArrayStack* s = malloc(sizeof(ArrayStack));
    if (!s) return NULL;

    s->capacity = max_size;
    s->size = 0;
    s->buffer = malloc(max_size * sizeof(Element));
    if (!s->buffer) {
        free(s);
        return NULL;
    }
    return s;
}

Kiểm tra trạng thái

int stack_is_full(const ArrayStack* s) {
    return s->size >= s->capacity;
}

int stack_is_empty(const ArrayStack* s) {
    return s->size == 0;
}

Thao tác chèn và loại bỏ

int stack_push(ArrayStack* s, Element val) {
    if (stack_is_full(s)) return -1;
    s->buffer[s->size++] = val;
    return 0;
}

Element stack_pop(ArrayStack* s) {
    if (stack_is_empty(s)) return -1;
    return s->buffer[--s->size];
}

Ngăn xếp liên kết đơn

Sử dụng danh sách liên kết với thao tác đầu danh sách làm đỉnh ngăn xếp:

#include "list.h"
#include <stdio.h>

typedef struct {
    struct list_head link;
    int value;
} StackNode;

int main() {
    struct list_head head;
    INIT_LIST_HEAD(&head);

    // Đẩy 5 phần tử vào ngăn xếp (đầu danh sách)
    for (int i = 1; i <= 5; ++i) {
        StackNode* node = malloc(sizeof(StackNode));
        node->value = i;
        list_add(&node->link, &head);
    }

    // Pop lần lượt: in giá trị rồi giải phóng
    struct list_head *pos, *tmp;
    list_for_each_safe(pos, tmp, &head) {
        StackNode* n = list_entry(pos, StackNode, link);
        printf("%d ", n->value);
        list_del(pos);
        free(n);
    }
    printf("\n");
    return 0;
}

Hàng đợi liên kết đơn

Hàng đợi tuân theo nguyên tắc FIFO (First In, First Out). Thêm vào cuối (tail), lấy từ đầu (head):

#include "list.h"
#include <stdio.h>

typedef struct {
    struct list_head link;
    int payload;
} QueueNode;

int main() {
    struct list_head queue;
    INIT_LIST_HEAD(&queue);

    // Enqueue 5 phần tử bằng cách chèn vào đuôi
    for (int i = 1; i <= 5; ++i) {
        QueueNode* qn = malloc(sizeof(QueueNode));
        qn->payload = i;
        list_add_tail(&qn->link, &queue);
    }

    // Dequeue: lấy từ đầu danh sách
    struct list_head *it, *next;
    list_for_each_safe(it, next, &queue) {
        QueueNode* q = list_entry(it, QueueNode, link);
        printf("%d ", q->payload);
        list_del(it);
        free(q);
    }
    printf("\n");
    return 0;
}