Giải thích cấu trúc dữ liệu hàng đợi (Queue) tuyến tính trong C

Cấu trúc dữ liệu là tập hợp dữ liệu được tổ chức có cấu trúc. Chia làm 2 loại:

Cấu trúc tuyến tính (Linear): Dữ liệu tổ chức theo trình tự. Ví dụ: mảng, cấu trúc, stack, queue, danh sách liên kết.
Cấu trúc phi tuyến tính (Nonlinear): Dữ liệu tổ chức phân cấp. Ví dụ: cây, đồ thị, tập hợp, bảng.

Hàng đợi (Queue)

Queue là cấu trúc dữ liệu tuyến tính, chèn (insert) tại cuối (rear) và xóa (delete) tại đầu (front).

Thứ tự Queue tuân theo nguyên tắc FIFO - First In First Out (Vào trước ra trước).

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

Insert (Enqueue) - Thêm phần tử vào hàng đợi.
Delete (Dequeue) - Xóa phần tử khỏi hàng đợi.

Điều kiện đặc biệt

Queue Overflow: Thêm vào hàng đợi đã đầy.
Queue Underflow: Xóa từ hàng đợi rỗng.

Thuật toán

Insertion (Enqueue)

Kiểm tra tràn: if (r == n) printf("Queue overflow")
Chèn: q[r] = item; r++;

Deletion (Dequeue)

Kiểm tra rỗng: if (f == r) printf("Queue underflow")
Xóa: item = q[f]; f++;

Display

Kiểm tra rỗng: if (f == r) printf("Queue is empty")
In từ f đến r: for(i=f; i



Chương trình mẫu: Triển khai Queue bằng mảng vòng (Circular Queue)
#include <limits.h>
#include <stdio.h>
#include <stdlib.h>

struct Queue {
    int front, rear, size;
    unsigned capacity;
    int* array;
};

struct Queue* createQueue(unsigned capacity) {
    struct Queue* queue = (struct Queue*)malloc(sizeof(struct Queue));
    queue->capacity = capacity;
    queue->front = queue->size = 0;
    queue->rear = capacity - 1;
    queue->array = (int*)malloc(queue->capacity * sizeof(int));
    return queue;
}

int isFull(struct Queue* queue) {
    return (queue->size == queue->capacity);
}

int isEmpty(struct Queue* queue) {
    return (queue->size == 0);
}

void Enqueue(struct Queue* queue, int item) {
    if (isFull(queue)) return;
    queue->rear = (queue->rear + 1) % queue->capacity;
    queue->array[queue->rear] = item;
    queue->size = queue->size + 1;
    printf("%d entered into queue\n", item);
}

int Dequeue(struct Queue* queue) {
    if (isEmpty(queue)) return INT_MIN;
    int item = queue->array[queue->front];
    queue->front = (queue->front + 1) % queue->capacity;
    queue->size = queue->size - 1;
    return item;
}

int front(struct Queue* queue) {
    if (isEmpty(queue)) return INT_MIN;
    return queue->array[queue->front];
}

int rear(struct Queue* queue) {
    if (isEmpty(queue)) return INT_MIN;
    return queue->array[queue->rear];
}

int main() {
    struct Queue* queue = createQueue(1000);
    Enqueue(queue, 100);
    Enqueue(queue, 200);
    Enqueue(queue, 300);
    Enqueue(queue, 400);
    printf("%d is deleted element from queue\n\n", Dequeue(queue));
    printf("1st item in queue is %d\n", front(queue));
    printf("last item in queue %d\n", rear(queue));
    return 0;
}


Kết quả chạy
100 entered into queue
200 entered into queue
300 entered into queue
400 entered into queue
100 is deleted element from queue
1st item in queue is 200
last item in queue 400