Hàng đợi ưu tiên là một loại hàng đợi trong đó các phần tử được chèn hoặc xóa theo mức độ ưu tiên được chỉ định cho chúng trong đó mức độ ưu tiên là một giá trị số nguyên có thể nằm trong khoảng từ 0-10 trong đó 0 hiển thị phần tử có mức độ ưu tiên cao nhất và 10 hiển thị phần tử có mức độ ưu tiên thấp nhất. Có hai quy tắc được tuân theo để triển khai hàng đợi ưu tiên -
- Dữ liệu hoặc phần tử có mức độ ưu tiên cao nhất sẽ được thực thi trước dữ liệu hoặc phần tử có mức độ ưu tiên thấp nhất.
- Nếu hai phần tử có cùng mức độ ưu tiên, chúng sẽ được thực thi theo trình tự mà chúng được thêm vào danh sách.
Có nhiều cấu trúc dữ liệu có sẵn có thể được sử dụng để triển khai hàng đợi ưu tiên như Ngăn xếp, Hàng đợi và Danh sách được liên kết. Trong bài viết này, chúng tôi đang giải thích cấu trúc dữ liệu hàng đợi. Có hai cách có thể được sử dụng để triển khai hàng đợi ưu tiên như -
- Duy trì hàng đợi cho nhiều mức độ ưu tiên trong một mảng duy nhất
Một cách để triển khai hàng đợi ưu tiên là duy trì một hàng đợi cho mỗi mức độ ưu tiên. Chúng ta có thể lưu trữ nhiều hàng đợi này trong một mảng duy nhất mà mỗi hàng đợi sẽ có hai con trỏ, tức là Front và Rear. Trong hàng đợi, Con trỏ phía trước được sử dụng để chèn phần tử vào hàng đợi và nó được tăng lên 1 bất cứ khi nào phần tử được chèn vào và một con trỏ khác ở phía sau được sử dụng để xóa hoặc loại bỏ phần tử khỏi hàng đợi được giảm đi 1 bất cứ khi nào phần tử bị xóa khỏi hàng đợi. Cuối cùng, thông qua vị trí của hai con trỏ, chúng ta cũng có thể xác định số phần tử trong hàng đợi.
- Trong kiểu biểu diễn này, chúng ta cần dịch chuyển các con trỏ để tạo không gian cho việc chèn các phần tử mới, điều này sẽ làm cho nó trở nên phức tạp cả về thời gian và không gian.
- Duy trì hàng đợi cho từng mức độ ưu tiên trong một mảng duy nhất
Trong loại phương pháp này, chúng tôi tạo mũi tên riêng cho từng phần tử. Mọi hàng đợi được triển khai dưới dạng một mảng tròn và có hai biến con trỏ. I.e. Trước và sau. Tương tự như vậy, phần tử có số thứ tự ưu tiên được chèn vào hàng đợi tương ứng nếu chúng ta muốn xóa một phần tử khỏi hàng đợi thì phần tử đó phải là phần tử từ hàng đợi có mức ưu tiên cao nhất. Số nguyên có mức độ ưu tiên thấp nhất cho biết mức độ ưu tiên cao nhất (0).
Lưu ý - Nếu kích thước của mỗi hàng đợi bằng nhau thì chúng ta có thể tạo một mảng hai chiều thay vì tạo nhiều mảng một chiều.
Thuật toán cho thao tác chèn vào hàng đợi ưu tiên
insert(queue, data, priority) If(queue->Rear[priority] = MAX-1 AND queue->Front[priority] = 0) OR (queue->Rear[priority] +1 =queue->Front[priority]) Print Overflow End IF queue->Rear[priority - 1] = MAX-1 Set queue->Rear[priority - 1] = 0 Else Set queue->Rear[priority] = queue->Rear[priority - 1] +1 End Set queue->CQueue[priority - 1] [queue->Rear[priority - 1] = data IF queue->Front[priority - 1] = -1 Set queue->Front[priority - 1] = 0 End
Thuật toán cho thao tác chèn vào hàng đợi ưu tiên
delete(queue) Set flag = 0, priority = 0 While priority <= MAX-1 IF NOT queue->Front[priority] = -1 Set flag = 1 Set value = queue->CQueue[priority][queue->Front[priority]] IF queue->Front[priority] = queue->Rear[priority] Set queue->Front[priority] = queue->Rear[priority] = -1 Else IF queue->Front[priority] = MAX-1 Set queue->Front[priority] = 0 Else Set queue->Front[priority] = queue->Front[priority] + 1 End End Break End Set priority = priority + End If flag = 0 Print underflow Else Return value End