Double Ended Queue (Deque)
It is also a homogeneous list of elements in which insertion and deletion
operations are performed from both the ends.
That is, we can insert elements from the rear end or from the front ends.
Hence it is called double-ended queue. It is commonly referred as a Deque.
There are two types of Deque. These two types are due to the restrictions put
to perform either the insertions or deletions only at one end.
Double Ended Queue (Deque)
There are:
◦ Input-restricted Deque.
◦ Output-restricted Deque.
Bellow show a figure a empty Deque Q[5] which can accommodate five
elements.
deletion insertion
insertion deletion
Q[0] Q[1] Q[2] Q[3] Q[4]
Fig: A Deque
Double Ended Queue (Deque)
■ There are:
■ Input-restricted Deque: An input restricted
Deque restricts the insertion of the elements at
one end only, the deletion of elements can be
done at both the end of a queue.
deletion 10 20 30 40 50 insertion
deletion
Q[0] Q[1] Q[2] Q[3] Q[4]
F R
Fig: A representation of an input-restricted Deque
Double Ended Queue (Deque)
■ There are:
■ Output-restricted Deque: on the contrary, an
Output-restricted Deque, restricts the deletion
of elements at one end only, and allows
insertion to be done at both the ends of a
Deque.
insertion 10 20 30 40 50 insertion
deletion
Q[0] Q[1] Q[2] Q[3] Q[4]
F R
Fig: A representation of an Output-restricted
Double Ended Queue (Deque)
■ The programs for input-restricted Deque and
output-restricted Deque would be similar to the
previous program of Deque except for a small
difference.
■ The program for the input-restricted Deque would
not contain the function addqatbeg().
■ Similarly the program for the output-restricted
Deque would not contain the function delatbeg().
Priority Queue
A priority queue is a collection of elements where the elements are stored
according to their priority levels.
The order in which the elements should get added or removed is decided by
the priority or the element.
Following rules are applied to maintain a priority queue.
◦ The element with a higher priority is processes before any element of lower
priority.
Priority Queue
◦ If there are elements with same priority, then the element added first in the queue
would get processed
Here, smallest number that is most highest priority and greater number that is
less priority.
Priority queues are used for implementing job scheduling by the operating
system.
Where jobs with higher priorities are to be processed first.
Another application of priority queue is simulation systems where priority
corresponds to event times.
Applications of Queues
Round robin technique for processor scheduling is implemented using queues.
All types of customer service (like railway ticket reservation) center
software’s are designed using queues to store customers information.
Printer server routines are designed using queues. A number of users share a
printer using printer server the printer server then spools all the jobs from all
the users, to the server’s hard disk in a queue. From here jobs are printed
one-by-one according to their number in the queue.
