Write a note on Dequeue and priority queue

Dequeue or Deque

A deque (double ended queue) is a linear list in which elements can be added or removed at either end but not in the middle.

Representation of Dequeue

• Deque is maintained by a circular array DEQUE with pointers LEFT and RIGHT, which point to the two ends of the deque.
• Figure shows deque with 4 elements maintained in an array with N = 8 memory locations.
• The condition LEFT = NULL will be used to indicate that a deque is empty.

There are two variations of a deque

1. Input-restricted deque is a deque which allows insertions at only one end of the list but allows deletions at both ends of the list.
2. Output-restricted deque is a deque which allows deletions at only one end of the list but allows insertions at both ends of the list.

Priority Queue

A priority queue is a collection of elements such that each element has been assigned a priority and such that the order in which elements are deleted and processed comes from the following rules:
(1) An element of higher priority is processed before any element of lower priority.
(2) Two elements with the same priority are processed according to the order in which they were added to the queue.

Representation of Priority Queue (click here)