Dequeue & Priority Queue
Dequeue
• A Double Ended Queue is a linear list in which insertions and
deletions are made to or from either end of the structure.
• There are two variations
• Input restricted dequeue
• Output restricted dequeue
• Input Restricted:
• Allows insertions from only one end
• Output Restricted:
• Allows deletions from only one end
Deque Operations
A deque provides operations for both ends:
• Add to the front: Insert an element at the front (left end).
• Add to the rear: Insert an element at the back (right end).
• Remove from the front: Remove an element from the front (left end).
• Remove from the rear: Remove an element from the back (right end).
Priority Queue
• A queue in which we are able to insert items or remove items from
any position based on priority is called priority queue.
• A priority queue is a type of queue that arranges elements based on
their priority values.
• Elements with higher priority values are typically retrieved or
removed before elements with lower priority values.
• Each element has a priority value associated with it.
• When we add an item, it is inserted in a position based on its priority
value.
• Priority queues are often used in real-time systems, where the
order in which elements are processed is not simply based on
the fact who came first (or inserted first), but based on priority.
• Properties of Priority Queue
• So, a priority Queue is an extension of the queue with the following
properties.
• Every item has a priority associated with it.
• An element with high priority is dequeued before an element with low
priority.
• If two elements have the same priority, they are served according to
their order in the queue.
Example:an element with a maximum ASCII
value will have the highest priority.
How is Priority assigned to the
elements in a Priority Queue?
• In a priority queue, generally, the value of an element is
considered for assigning the priority.
• For example, the element with the highest value is assigned
the highest priority and the element with the lowest value is
assigned the lowest priority. The reverse case can also be used
i.e., the element with the lowest value can be assigned the
highest priority. Also, the priority can be assigned according to
our needs.
Types of Priority Queue:
• 1) Ascending Order Priority Queue
• As the name suggests, in ascending order priority queue, the
element with a lower priority value is given a higher priority in
the priority list. For example, if we have the following elements
in a priority queue arranged in ascending order like 4,6,8,9,10.
Here, 4 is the smallest number, therefore, it will get the highest
priority in a priority queue and so when we dequeue from this
type of priority queue, 4 will remove from the queue and
dequeue returns 4.
• 2) Descending order Priority Queue
• It will remove the element with the highest priority first.