🌱 Cấu trúc dữ liệu: Queue - Priority Queue
Ở những bài viết trước, mình đã cùng mọi người tìm hiểu về cấu trúc dữ liệu Queue, cách triển khai Linear Queue, Circular Queue và sử dụng trong bài toán thực tế.
Các bạn có thể xem lại các bài viết / video tại đây
Bài viết này, chúng ta sẽ tiếp tục tìm hiểu về một biến thể khác của Queue, đó là Priority Queue, tức là một Queue, nhưng các phần tử bên trong sẽ sắp xếp dựa theo thứ tự ưu tiên.
👉 Bài toán đặt ra
Hiện tại mình đang viết một chương trình hệ điều hành RTOS cho vi điều khiển (single core), và mong muốn quản lý các task của MCU này.
Vấn đề đặt ra là tại một thời điểm, có thể có nhiều task cần được phục vụ, nhưng MCU chỉ có một core, nên tại một thời điểm chỉ phục vụ được 1 task duy nhất. Chính vì vậy, khi các task vụ cần được phục vụ cùng đến, chúng sẽ cần phải "xếp hàng"
➜ Đó chính là lợi thế để có thể sử dụng Queue, cấu trúc dữ liệu hoạt động theo kiểu "xếp hàng" - First In First Out.
Với bài toán này, chúng ta cần thêm 1 yếu tố nữa, đó chính là mức độ ưu tiên, bởi vì các task của RTOS thường đi kèm với mức độ ưu tiên, các task có mức ưu tiên cao hơn sẽ cần phải được thực hiện trước, trong khi các task có mức ưu tiên thấp hơn sẽ phải đợi.
Chẳng hạn có 3 task đang xếp hàng đợi trong queue, với mức ưu tiên lần lượt là 1, 2, 3,
thì có 1 task mới (task 4) với mức ưu tiên là 2, cũng đến và "xếp hàng" (như hình bên dưới).
Dễ thấy, với trường hợp này Task 4 có mức ưu tiên cao hơn Task 1, nên nó sẽ phải đứng trước Task 1. Trong khi đó, Task 4 có mưu ưu tiên bằng Task 2, nhưng đến sau Task 2, nên nó sẽ phải đứng sau Task 2 (như trong hình vẽ).
Với 2 bài toán về Linear Queue và Circular Queue, chúng ta chỉ giải quyết được vấn đề về mặt sắp xếp các sự kiện, Khi thêm phần tử vào Queue, chúng ta kiểm tra và sắp xếp lại các phần tử của Queue nữa.
➜ Priority Queue sẽ giúp chúng ta giải quyết vấn đề này!
👉 Khái niệm và đặc điểm của Priority Queue
Priority Queue là một cấu trúc dữ liệu mà các phần tử được quản lý sẽ có “độ ưu tiên” khác nhau gắn với từng phần tử. Phần tử có thứ tự ưu tiên cao hơn trong Priority Queue sẽ được xếp lên trước và truy vấn trước.
Đơn giản hơn, Priority Queue là một cấu trúc cho phép nó tự động sắp xếp các phần tử của nó dựa theo mức độ ưu tiên.
Một Priority Queue sẽ có các chức năng cơ bản sau:
- Thêm một phần tử vào Queue (Push hoặc EnQueue) - Việc thêm sẽ đồng nghĩa với việc kiểm tra mức độ ưu tiên của phần tử mới, và sắp xếp nó đúng vị trị.
- Sau khi thêm, phần tử có ưu tiên cao hơn sẽ đứng trước phần tử có ưu tiên thấp hơn.
- Nếu 2 phần tử có mức ưu tiên bằng nhau, phần tử đến trước sẽ đứng trước.
- Khi lấy phần tử khỏi Queue (Pop hoặc DeQueue) - Lấy ra phần tử ở đầu, tức là phần tử có mức độ ưu tiên cao nhất.
👉 Triển khai Priority Queue
💬 Triển khai kiểu dữ liệu
Dễ thấy, Priority Queue triển khai tương đối giống Queue, chỉ thêm một thông số về mức độ ưu tiên của mỗi phần tử.
Ở bài toán này, mình sẽ sử dụng base từ Circular Queue để tối ưu về mặt thời gian khi push phần tử vào Queue.
💬 Thao tác Push phần tử vào Queue
Đây là trường hợp chính và khó triển khai nhất của Priority Queue. Khi một phần tử được thêm vào Priority Queue, có trường hợp xảy ra:
- Queue chưa đầy
Trường hợp này thì phần tử mới sẽ được thêm vào queue, và cần được đặt đúng vị trí của nó - tức là đứng trước các phần tử có độ ưu tiên thấp hơn nó, và đứng sau những phần tử có độ ưu tiên lớn hơn hoặc bằng nó (Trường hợp độ ưu tiên bằng nhau là do phần tử mới này đến sau). - Queue đã đầy, và phần tử push có độ ưu tiên lớn hơn độ ưu tiên thấp nhất
Trường hợp này, phần tử cần thêm cũng sẽ được push vào Queue, và phần tử cuối hiện tại của Queue sẽ bị đẩy ra ngoài. - Queue đã đầy, phần tử push có độ ưu tiên nhỏ hơn hoặc bằng độ ưu tiên thấp nhất
Trường hợp này, phần tử cần thêm sẽ không được push. Queue giữ nguyên trạng thái ban đầu.
💬 Thao tác Pop phần tử khỏi Queue
Việc pop các phần tử khỏi Priority Queue cũng tương tự như việc pop phần tử khỏi Circular Queue. Ở đây chúng ta sẽ pop ra phần tử có mức ưu tiên cao nhất để xử lý.
👉 Video triển khai Priority Queue
>>>= Follow ngay =<<<
Để nhận được những bài học miễn phí mới nhất nhé 😊
Chúc các bạn học tập tốt 😊
0 Nhận xét