Giới thiệu Priority Queue (Hàng đợi ưu tiên) trong C/C++

Priority Queue là hàng đợi các phần tử được chèn/xóa theo độ ưu tiên (priority - số nguyên 0-10, 0 = ưu tiên cao nhất, 10 = thấp nhất).

Hai quy tắc:

• Phần tử ưu tiên cao thực thi trước ưu tiên thấp.
• Nếu ưu tiên bằng nhau → thực thi theo thứ tự vào hàng (FIFO).

Cấu trúc dữ liệu triển khai: Stack, Queue, Linked List. Bài này giải thích dùng Queue.

Cách 1: Nhiều hàng đợi ưu tiên trong một mảng

Mỗi mức ưu tiên một hàng đợi, lưu trong mảng 2D. Mỗi hàng đợi có 2 con trỏ Front (chèn) và Rear (xóa). Front tăng khi chèn, Rear giảm khi xóa. Vị trí 2 con trỏ cho biết số phần tử.

Nhược điểm: phải dịch con trỏ khi chèn → phức tạp thời gian/không gian.

Cách 2: Hàng đợi riêng cho mỗi ưu tiên (mảng vòng)

Mỗi hàng đợi là mảng vòng (circular array) với Front, Rear. Phần tử ưu tiên p vào hàng p. Xóa phải lấy từ hàng ưu tiên cao nhất (số nguyên nhỏ nhất = 0).

Lưu ý: Nếu các hàng đợi cùng kích thước → dùng một mảng 2D thay vì nhiều mảng 1D.

Thuật toán Insert (Chè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"; return
  if queue->Rear[priority-1] == MAX-1:
     queue->Rear[priority-1] = 0
  else:
     queue->Rear[priority] = queue->Rear[priority-1] + 1
  queue->CQueue[priority-1][queue->Rear[priority-1]] = data
  if queue->Front[priority-1] == -1:
     queue->Front[priority-1] = 0

Thuật toán Delete (Xóa)

delete(queue):
  flag = 0, priority = 0
  while priority <= MAX-1:
    if queue->Front[priority] != -1:
      flag = 1
      value = queue->CQueue[priority][queue->Front[priority]]
      if queue->Front[priority] == queue->Rear[priority]:
        queue->Front[priority] = queue->Rear[priority] = -1
      else:
        if queue->Front[priority] == MAX-1:
          queue->Front[priority] = 0
        else:
          queue->Front[priority]++
      break
    priority++
  if flag == 0: print "Underflow"
  else: return value