Priority Queue

Regular queue follows a First In First Out (FIFO) order to insert and remove an item. Whatever goes in first, comes out first. However, in a priority queue, an item with the highest priority comes out first. Therefore, the FIFO pattern is no longer valid.

Every item in the priority queue is associated with a priority. It does not matter in which order we insert the items in the queue, the item with higher priority must be removed before the item with the lower priority. If the two items have the same priorities, the order of removal is undefined and it depends upon the implementation.

The real world example of a priority queue would be a line in a bank where there is a special privilege for disabled and old people. The disabled people have the highest priority followed by elderly people and the normal person has the lowest priority.

Priority queue: Enqueue operation

// insert an item at the appropriate position of the
// queue so that the queue is always ordered

void enqueue(int item) {
        // Check if the queue is full
        if (n == MAX_SIZE - 1) {
                printf("%s\n", "ERROR: Queue is full");
                return;
        }

        int i = n - 1;
        while (i >= 0 && item < queue[i]) {
                queue[i + 1] = queue[i];
                i--;
        }
        queue[i + 1] = item;
        n++;
}

Priority queue: Dequeue operation

// remove the last element in the queue
int dequeue() {
        int item;
        // Check if the queue is empty
        if (n == 0) {
                printf("%s\n", "ERROR: Queue is empty");
                return ;
        }
        item = queue[n - 1];
        n = n - 1;
        return item;
}