Cấu trúc dữ liệu và thuật toán | Hàng đợi (Queue)
1. Cấu trúc dữ liệu hàng đợi và ứng dụng
Hàng đợi là một dạng CTDL mà ở đó thao tác chèn vào sẽ được diễn ra ở một đầu, thường gọi là phía sau hay cuối (back or rear), trong khi phép toán xóa chỉ được thực hiện ở phía còn lại, gọi là phía trước hay đầu (front or head).
Nguyên tắc của hàng đợi: Vào trước ra trước, First-In First-Oout (FIFO)
Giống với ngăn xếp, hàng đợi cũng có 2 cách cài đặt cơ bản là dùng mảng và con trỏ.
Hàng đợi cũng có rất nhiều ứng dụng trong thực tế, ví dụ như là:
- Trong hệ điều hành: hàng đợi xử lý sự kiện, quản lý tiến trình, xử lý các câu lệnh. CPU không thể chạy tất cả các task cùng lúc nên các task sẽ được sắp xếp theo thứ tự ưu tiên lần lượt.
- Web server: một trang web cần phải xử lý vài nghìn files của người dùng nhưng khả năng của trang web chỉ xử lý được 100 files cùng một lúc, lúc này chúng ta cần một hàng đợi để đưa các request vào hàng đợi để chờ xử lý.
- Ứng dụng khi in hoặc upload nhiều ảnh cùng lúc
- Lưu vết trong quá trình tìm kiếm, quay lui, vét cạn,...
- Duyệt đồ thị
2. Cài đặt ngăn xếp sử dụng mảng
Khai báo một struct Queue và viết các hàm tương ứng với các phép toán trên hàng đợi:
- isFull(): kiểm tra hàng đợi đã đầy chưa
- enqueue(): thêm phần từ vào cuối hàng đợi
- dequeue(): lấy phần tử ra khỏi đầu hàng đợi
- getFront(): xem phần tử đầu hàng đợi
- getRear(): xem phần tử ở cuối hàng đợi
Tùy thuộc vào từng bài toán, khi cần thêm những chức năng cụ thể nào cho hàng đợi thì chúng ta có thể viết thêm các hàng tương ứng để công việc được thực hiện một cách dễ dàng hơn.
#define INT_MIN -2147483648 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 = -1; queue->array = (int*) malloc(queue->capacity * sizeof(int)); return queue; } // Kiem tra queue day int isFull(struct Queue* queue){ return (queue->size == queue->capacity); } // Kiem tra queue rong int isEmpty(struct Queue* queue){ return (queue->size == 0); } // Them phan tu vao queue void enqueue(struct Queue* queue, int item){ if(isFull(queue)){ return; } queue->rear = (queue->rear + 1); queue->array[queue->rear] = item; queue->size = queue->size + 1; printf("%d enqueued to 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->size = queue->size - 1; return item; } int getFront(struct Queue* queue){ if(isEmpty(queue)){ return INT_MIN; } return queue->array[queue->front]; } int getRear(struct Queue* queue){ if(isEmpty(queue)){ return INT_MIN; } return queue->array[queue->rear]; } int main(){ struct Queue* queue = createQueue(10); enqueue(queue, 1); enqueue(queue, 2); printf("Top of queue is %d", getFront(queue)); printf("Rear of queue is %d", getRear(queue)); }
3. Cài đặt ngăn xếp sử dụng con trỏ
Với con trỏ thì chúng ta cũng cài đặt tương tự các hàm so với sử dụng mảng.
#include<stdio.h> #include<stdlib.h> struct node { int data; struct node *next; }; struct node *front = NULL, *rear = NULL; void enqueue(int val) { struct node *newNode = malloc(sizeof(struct node)); newNode->data = val; newNode->next = NULL; if(front == NULL && rear == NULL){ front = rear = newNode; } else { rear->next = newNode; rear = newNode; } } void dequeue() { struct node *temp; if(front == NULL) printf("Queue is Empty\n"); else { temp = front; front = front->next; if(front == NULL){ rear = NULL; } free(temp); } } void printList() { struct node *temp = front; while(temp) { printf("%d->",temp->data); temp = temp->next; } printf("NULL\n"); } int main() { enqueue(10); enqueue(20); enqueue(30); printf("Queue :"); printList(); dequeue(); printf("After dequeue the new Queue :"); printList(); dequeue(); printf("After dequeue the new Queue :"); printList(); return 0; }
