[DSA] Queue

1. Queue là gì?

Queue là một cấu trúc dữ liệu dạng hàng đợi trong lập trình, có các tính chất giống như một hàng đợi thực tế. Một queue bao gồm một tập hợp các phần tử và các phép toán sau:

• Enqueue: Thêm một phần tử vào cuối queue.
• Dequeue: Xóa phần tử đầu tiên của queue.
• Front: Lấy phần tử đầu tiên của queue mà không xóa nó.
• Rear: Lấy phần tử cuối cùng của queue mà không xóa nó.
• IsEmpty: Kiểm tra xem queue có rỗng hay không.
• IsFull: Kiểm tra xem queue đã đầy hay chưa.

Queue thường được sử dụng để lưu trữ và xử lý các phần tử theo thứ tự mà chúng được thêm vào. Queue được sử dụng rộng rãi trong các ứng dụng thực tế như xử lý các tác vụ trong hệ thống máy tính, quản lý các tác vụ đang chờ đợi, xử lý các yêu cầu từ người dùng, v.v.

2. Các phép toán trên Queue

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

#define MAX_SIZE 100

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

//Thêm một phần tử vào cuối queue.

void enqueue(Queue *q, int item) {
    if (q->rear == MAX_SIZE - 1) {
        printf("Queue overflow\n");
    } else {
        if (q->front == -1) {
            q->front = 0;
        }
        q->rear++;
        q->items[q->rear] = item;
    }
}

//Xóa phần tử đầu tiên của queue.

int dequeue(Queue *q) {
    int item;
    if (q->front == -1 || q->front > q->rear) {
        printf("Queue underflow\n");
        return -1;
    } else {
        item = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1;
        }
        return item;
    }
}

//Lấy phần tử đầu tiên của queue mà không xóa nó.

int front(Queue *q) {
    if (q->front == -1) {
        printf("Queue is empty\n");
        return -1;
    } else {
        return q->items[q->front];
    }
}

//Lấy phần tử cuối cùng của queue mà không xóa nó.

int rear(Queue *q) {
    if (q->rear == -1) {
        printf("Queue is empty\n");
        return -1;
    } else {
        return q->items[q->rear];
    }
}

//Kiểm tra xem queue có rỗng hay không.

int isEmpty(Queue *q) {
    if (q->rear == -1) {
        return 1;
    } else {
        return 0;
    }
}

//Kiểm tra xem queue đã đầy hay chưa.

int isFull(Queue *q) {
    if (q->rear == MAX_SIZE - 1) {
        return 1;
    } else {
        return 0;
    }
}

//Hàm main để test các phương thức

int main() {
    Queue q;
    q.front = -1;
    q.rear = -1;

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    printf("Front element: %d\n", front(&q));
    printf("Rear element: %d\n", rear(&q));

    printf("Dequeued element: %d\n", dequeue(&q));
    printf("Dequeued element: %d\n", dequeue(&q));

    printf("Front element: %d\n", front(&q));
    printf("Rear element: %d\n", rear(&q));

    return 0;
}

3. Ứng dụng sử dụng Queue

Ứng dụng: Simulating a printer queue (Mô phỏng hàng đợi máy in)

Trong ứng dụng này, chúng ta sử dụng một queue để mô phỏng một hàng đợi máy in. Mỗi công việc cần được in sẽ được thêm vào queue và được in ra khi đến lượt của nó. Nếu có nhiều công việc cùng được đưa vào queue, chúng sẽ được xử lý theo thứ tự đến trước thì in trước.

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

#define MAX_SIZE 100

typedef struct {
    int jobNumber;
    int numOfPages;
} PrintJob;

typedef struct {
    PrintJob items[MAX_SIZE];
    int front;
    int rear;
} PrinterQueue;

void enqueue(PrinterQueue *q, PrintJob job) {
    if (q->rear == MAX_SIZE - 1) {
        printf("Printer queue is full\n");
    } else {
        if (q->front == -1) {
            q->front = 0;
        }
        q->rear++;
        q->items[q->rear] = job;
        printf("Added job %d with %d pages to the printer queue\n", job.jobNumber, job.numOfPages);
    }
}

PrintJob dequeue(PrinterQueue *q) {
    PrintJob job;
    if (q->front == -1 || q->front > q->rear) {
        printf("Printer queue is empty\n");
        job.jobNumber = -1;
        job.numOfPages = -1;
        return job;
    } else {
        job = q->items[q->front];
        q->front++;
        if (q->front > q->rear) {
            q->front = q->rear = -1;
        }
        printf("Printing job %d with %d pages\n", job.jobNumber, job.numOfPages);
        return job;
    }
}

int main() {
    PrinterQueue q;
    q.front = -1;
    q.rear = -1;

    PrintJob job1 = {1, 10};
    PrintJob job2 = {2, 5};
    PrintJob job3 = {3, 20};
    PrintJob job4 = {4, 7};

    enqueue(&q, job1);
    enqueue(&q, job2);
    enqueue(&q, job3);
    enqueue(&q, job4);

    printf("\n");

    dequeue(&q);
    dequeue(&q);
    dequeue(&q);
    dequeue(&q);

    return 0;
}
Trong đó, chúng ta định nghĩa kiểu dữ liệu PrintJob để lưu trữ thông tin về một công việc cần in, bao gồm số hiệu công việc và số trang cần in. Chúng ta cũng định nghĩa kiểu dữ liệu PrinterQueue bằng cách sử dụng một struct, trong đó có một mảng các PrintJob và hai biến front và rear để lưu trữ chỉ số của phần tử đầu tiên và phần tử cuối cùng trong queue