Hàng đợi (Queue) là một cấu trúc dữ liệu hoạt động theo nguyên lý "Vào trước - Ra trước" (First In - First Out). Việc triển khai hàng đợi bằng danh sách liên kết (Linked List) giúp tối ưu hóa bộ nhớ do không yêu cầu các ô nhớ liên tiếp và có thể mở rộng kích thước linh hoạt. Dưới đây là hướng dẫn chi tiết cách xây dựng một Linked Queue trong ngôn ngữ C.

1. Định nghĩa cấu trúc dữ liệu

Chúng ta cần hai thành phần chính: một nút (Node) để lưu trữ dữ liệu và một cấu trúc quản lý hàng đợi chứa con trỏ đến đầu (head) và cuối (tail) hàng đợi.

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

typedef int DataType;

// Định nghĩa cấu trúc của một nút trong hàng đợi
typedef struct QNode {
    DataType data;
    struct QNode *next;
} QNode;

// Cấu trúc quản lý hàng đợi
typedef struct {
    QNode *front; // Con trỏ trỏ đến đầu hàng đợi
    QNode *rear;  // Con trỏ trỏ đến cuối hàng đợi
    int length;   // Số lượng phần tử hiện tại
} LinkedQueue;

2. Khởi tạo hàng đợi

Hàm này cấp phát bộ nhớ cho cấu trúc điều khiển và thiết lập các giá trị ban đầu.

LinkedQueue* initQueue() {
    LinkedQueue *q = (LinkedQueue*)malloc(sizeof(LinkedQueue));
    if (q == NULL) return NULL;
    
    q->front = NULL;
    q->rear = NULL;
    q->length = 0;
    return q;
}

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

Kiểm tra trạng thái hàng đợi

Hàm kiểm tra xem hàng đợi có rỗng hay không và hàm trả về kích thước hiện tại.

int isEmpty(LinkedQueue *q) {
    if (q == NULL || q->front == NULL) return 1;
    return 0;
}

int getQueueSize(LinkedQueue *q) {
    return (q != NULL) ? q->length : -1;
}

Thêm phần tử (Enqueue)

Thêm một phần tử mới vào cuối hàng đợi.

int enqueue(LinkedQueue *q, DataType val) {
    if (q == NULL) return 0;

    QNode *newNode = (QNode*)malloc(sizeof(QNode));
    if (newNode == NULL) return 0;

    newNode->data = val;
    newNode->next = NULL;

    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    q->length++;
    return 1;
}

Xóa phần tử (Dequeue)

Loại bỏ phần tử ở đầu hàng đợi và giải phóng bộ nhớ của nút đó.

int dequeue(LinkedQueue *q) {
    if (q == NULL || isEmpty(q)) return 0;

    QNode *temp = q->front;
    q->front = q->front->next;

    // Nếu sau khi xóa, hàng đợi trống thì cập nhật lại rear
    if (q->front == NULL) {
        q->rear = NULL;
    }

    free(temp);
    q->length--;
    return 1;
}

Lấy giá trị đầu và cuối

Truy xuất dữ liệu mà không làm thay đổi cấu trúc hàng đợi.

DataType peekFront(LinkedQueue *q) {
    if (isEmpty(q)) exit(EXIT_FAILURE);
    return q->front->data;
}

DataType peekRear(LinkedQueue *q) {
    if (isEmpty(q)) exit(EXIT_FAILURE);
    return q->rear->data;
}

4. Giải phóng bộ nhớ

Khi không còn sử dụng, cần xóa toàn bộ các nút và bản thân cấu trúc hàng đợi để tránh rò rỉ bộ nhớ.

void destroyQueue(LinkedQueue *q) {
    if (q == NULL) return;
    
    QNode *current = q->front;
    while (current != NULL) {
        QNode *next = current->next;
        free(current);
        current = next;
    }
    free(q);
}

5. Kiểm thử chương trình

Dưới đây là ví dụ cách sử dụng các hàm đã xây dựng để vận hành hàng đợi.

int main() {
    LinkedQueue *myQueue = initQueue();

    enqueue(myQueue, 10);
    enqueue(myQueue, 20);
    enqueue(myQueue, 30);

    printf("Kich thuoc hien tai: %d\n", getQueueSize(myQueue));
    printf("Phan tu dau: %d\n", peekFront(myQueue));
    printf("Phan tu cuoi: %d\n", peekRear(myQueue));

    dequeue(myQueue);
    printf("Sau khi dequeue, phan tu dau moi: %d\n", peekFront(myQueue));

    destroyQueue(myQueue);
    return 0;
}

Việc triển khai hàng đợi bằng danh sách liên kết đòi hỏi lập trình viên phải quản lý con trỏ cẩn thận, đặc biệt là trong các thao tác thêm và xóa phần tử để đảm bảo tính toàn vẹn của dữ liệu và tránh lỗi truy cập bộ nhớ.