Introduction to priority queue in C/C++

A priority queue is a queue in which elements are inserted or removed according to the priority assigned to them, where priority is an integer value in the range 0-10, where 0 represents the element with the highest priority and 10 Represents the element with the highest priority and the element with the lowest priority. Implementing a priority queue follows two rules:

• The data or element with the highest priority will be executed before the data or element with the lowest priority.
• If two elements have the same priority, they will be executed in the order they were added to the list.

There are a variety of available data structures that can be used to implement priority queues such as stacks, queues, and linked lists. In this article, we will explain queue data structure. There are two methods that can be used to implement a priority queue, for example-

• Maintaining multiple priority queues in a single array

  One method to implement a priority queue Just maintain a queue for each priority. We can store these multiple queues in an array where each queue has two pointers, Front and Rear. In the queue, the Front pointer is used to insert elements into the queue, and it is incremented by 1 every time an element is inserted; the other pointer is the rear pointer, used to delete or remove elements from the queue, and it is decremented every time an element is inserted. 1 is removed from the queue. Finally, from the positions of the two pointers we can also determine the number of elements in the queue.

Note- If each queue has the same size, then instead of creating multiple A one-dimensional array.

Priority queue insertion operation algorithm

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

Algorithm of insertion operation in priority queue

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

The above is the detailed content of Introduction to priority queue in C/C++. For more information, please follow other related articles on the PHP Chinese website!