Module 8: Basic ADTS (Queue Data Structures) (Week 5)

8.1 Queue
A Queue is an abstract data structure and a linear list of elements in which
deletion can take place only at one end, called the Front, and insertions can
take place only at the other end, called the Rear. The term “front” and “rear”
are used in describing a linear list only when it is implemented as a queue.
Queue is also called first-in-first-out (FIFO) lists since the first element in a
queue will be the first element out of the queue. In other words, the order in
which elements enters a queue is the order in which they leave. This contrasts
with stacks, which are last-in first-out (LIFO) lists.

Queue can also be defined as the list or collection in which the insertion is
done from one end known as the rear end or the tail of the queue, whereas
the deletion is done from another end known as the front end or the head of
the queue.

Queue abounds in everyday life. A real-world example of queue can be a

single-lane one-way road, where the vehicle enters first, exits first.

Other real-world examples of Queues are:

▪ Queues at the ticket windows and bus-stops.
▪ The automobiles waiting to pass through an intersection form a queue,
in which the first car in line is the first car through;

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 1 of 20

 ▪ the people waiting in line at a bank form a queue, where the first person
in line is the first person to be waited on; and so on.
▪ The ticket queue outside a cinema hall, where the person who enters
first in the queue gets the ticket first, and the last person enters in the
queue gets the ticket at last. Similar approach is followed in the queue
in data structure.
▪ An important example of a queue in computer science occurs in a
timesharing system, in which programs with the same priority form a
queue white waiting to be executed.

8.2 Types of Queues

There are four different types of queues that are listed as follows:
▪ Simple Queue or Linear Queue:
▪ Circular Queue
▪ Priority Queue
▪ Double Ended Queue (or Deque)

8.2.1 Simple Queue or Linear Queue

In Linear Queue, an insertion takes place from one end while the deletion
occurs from another end. The end at which the insertion takes place is known
as the rear end, and the end at which the deletion takes place is known as
front end. It strictly follows the FIFO rule.

The major drawback of using a Linear Queue is that insertion is done only
from the rear end. If the first three elements are deleted from the Queue, we
cannot insert more elements even though the space is available in a Linear
Queue. In this case, the linear Queue shows the overflow condition as the rear
is pointing to the last element of the Queue.

8.2.2 Circular Queue

In Circular Queue, all the nodes are represented as circular. It is similar to
the linear Queue except that the last element of the queue is connected to the
first element. It is also known as Ring Buffer, as all the ends are connected to
another end. The representation of circular queue is shown in the below image
-

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 2 of 20

The drawback that occurs in a linear queue is overcome by using the circular
queue. If the empty space is available in a circular queue, the new element
can be added in an empty space by simply incrementing the value of rear. The
main advantage of using the circular queue is better memory utilization.

8.2.3 Priority Queue

It is a special type of queue in which every element in the queue has a priority
associated with it. Suppose some elements occur with the same priority, they
will be arranged according to the FIFO principle. The representation of priority
queue is shown in the below image.

Insertion in priority queue takes place based on the arrival, while deletion in
the priority queue occurs based on the priority. Priority queue is mainly used
to implement the CPU scheduling algorithms.

8.2.4 Double Ended Queue (or Deque)

In Deque (Double Ended Queue), insertion and deletion can be done from both
ends of the queue either from the front or rear. It means that we can insert
and delete elements from both front and rear ends of the queue. The
representation of the deque is shown in the below image:

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 3 of 20

8.3 Representation of Queues
As in Stacks, a queue can also be implemented using Arrays, Linked-lists,
Pointers and Structures. For the sake of simplicity, we shall implement
queues using one-dimensional array.

8.3.1 Array Representation of Queues

We can easily represent queue by using linear arrays. There are two variables
i.e., front and rear, that are implemented in the case of every queue. Front
and rear variables point to the position from where insertions and deletions
are performed in a queue. Initially, the value of front and queue is -1 which
represents an empty queue. Array representation of a queue containing 5
elements along with the respective values of front and rear, is shown in the
figure below.

The above figure shows the queue of characters forming the English word
"HELLO". Since, no deletion is performed in the queue till now, therefore the
value of front remains -1. However, the value of rear increases by one every
time an insertion is performed in the queue. After inserting an element into
the queue shown in the above figure, the queue will look like Figure below.
The value of rear will become 5 while the value of front remains same.

After deleting an element, the value of front will increase from -1 to 0 and the
queue will look something like Figure below.

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 4 of 20

8.3.2 Linked List Representation of Queues
Due to the drawbacks of array implementation, it cannot be used for the large-
scale applications where the queues are implemented. Another alternative to
the array implementation is linked list implementation of queue. In a linked
queue, each node of the queue consists of two parts i.e., data part and the
link part. Each element of the queue points to its immediate next element in
the memory. In the linked queue, there are two pointers maintained in the
memory i.e., front pointer and rear pointer. The front pointer contains the
address of the starting element of the queue while the rear pointer contains
the address of the last element of the queue. Insertion and deletions are
performed at rear and front end respectively. If front and rear both are NULL,
it indicates that the queue is empty.

The storage requirement of linked representation of a queue with n elements

is o(n) while the time requirement for operations is O(1). The linked
representation of queue is shown in the figure below.

8.4 Queue Operations

Unlike Arrays and Stack, elements in the queue cannot be operated from
their respective locations. They can only be operated at two data pointers,
front and rear. Also, these operations involve standard procedures like
initializing or defining data structure, utilizing it, and then wholly erasing it
from memory. The two fundamental operations of a Queue are Enqueue and
Dequeue.

(a) Enqueue: The Enqueue operation is used to insert the element at the
rear end of the queue. It returns void.

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 5 of 20

 (b) Dequeue: It performs the deletion from the front-end of the queue. It
also returns the element which has been removed from the front-end.
It returns an integer value.

Other operations are:

(a) Peek(): This is the third operation that returns the element, which is
pointed by the front pointer in the queue but does not delete it.
(b) isFull(): It shows the overflow condition when the queue is completely
full.
(c) isEmpty(): It shows the underflow condition when the Queue is
empty, i.e., no elements are in the Queue.
(d) initialize(): creates/initializes the stack (i.e. create an empty Stack)

8.4.1 Insertion operation: enqueue()

The enqueue() is a data manipulation operation that is used to insert
elements into the stack. The following steps should be followed to insert
(enqueue) data element into a queue -

Step 1: Check if the queue is full.

Step 2: If the queue is full, Overflow error.
Step 3: If the queue is not full, increment the rear pointer to point to
the next available empty space.
Step 4: Add the data element to the queue location where the rear is
pointing.
Step 5: Here, you have successfully added 7, 2, and -9.

The working of enqueue operation is illustrated below:

The algorithm for an enqueue () operation using an Array is shown below:

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 6 of 20

 Algorithm: ENQUEUE (QUEUE, MAXSIZE, FRONT, REAR,COUNT,
ITEM)
[This algorithm inserts an element ITEM into a circular queue.]
1. [QUEUE already filled?]
If COUNT = MAXSIZE then: [ COUNT is number of values in the
QUEUE]
Write: OVERFLOW, and Return.
2. [Find new value of REAR.]
If COUNT= 0, then: [Queue initially empty.]
Set FRONT= 0 and REAR = 0
Else: if
REAR = MAXSIZE - 1, then:
Set REAR = 0
Else:
Set REAR = REAR+1.
[End of If Structure.]
3. Set QUEUE[REAR] = ITEM. [This insert new element.]
4. COUNT=COUNT+1 [ Increment to Counter.]
5. Return.

8.4.2 Deletion Operation: dequeue()

The dequeue() is a data manipulation operation that is used to remove
elements from the stack. The following steps should be followed to remove
data from the queue:

Step 1: Check if the queue is empty.

Step 2: If the queue is empty, Underflow error.
Step 3: If the queue is not empty, access the data where the front
pointer is pointing.
Step 4: Increment front pointer to point to the next available data
element.
Step 5: Here, you have removed 7, 2, and -9 from the queue data
structure.

The working of enqueue operation is illustrated below:

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 7 of 20

The algorithm for an enqueue () operation using an Array is shown below:
Algorithm: DEQUEUE(QUEUE, MAXSIZE, FRONT, REAR,COUNT,
ITEM)
[This procedure deletes an element from a queue and assigns it to the
variable ITEM.]
1. [QUEUE already empty?]
If COUNT= 0, then:
Write: UNDERFLOW, and Return.
2. Set ITEM = QUEUE[FRONT].
3. Set COUNT = COUNT -1
4. [Find new value of FRONT.]
If COUNT = 0, then: [There was one element and has been deleted]
Set FRONT= -1, and REAR = -1.
Else if
FRONT= MAXSIZE, then: [Circular, so set Front = 0 ]
Set FRONT = 0
Else:
Set FRONT:=FRONT+1.
[End of If structure.]
5. Return ITEM

8.5 Deque
Deque or Double-ended Queue (pronounced as ‘deck’ or ‘dequeue’) is
abstract data structure in which insertion and deletion can be done from both
ends of the queue either from the front or rear. It means that we can insert
and delete elements from both front and rear ends of the queue. Deque can

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 8 of 20

be used as a palindrome checker to read string from both ends, and then the
string would be the same.

Deque can be used both as stack and queue as it allows the insertion and
deletion operations on both ends. Deque can be considered as stack because
stack follows the LIFO (Last In First Out) principle in which insertion and
deletion can be performed only from one end. And in deque, it is possible to
perform both insertion and deletion from one end, and Deque does not follow
the FIFO principle. The representation of the deque is shown in the Figure
below:

There are two types of deque that are discussed as follows -

(a) Input restricted deque: In input restricted queue, insertion operation

can be performed at only one end, while deletion can be performed from
both ends.

(b) Output restricted deque: In output restricted queue, deletion

operation can be performed at only one end, while insertion can be
performed from both ends.

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 9 of 20

8.5.1 Representation of Deque in memory
The Deque can be implemented using either a circular queue or a doubly-
linked list. The circular queue implementation of the deque is the most
straightforward approach to implement a double-ended queue. A circular
queue is an extended version of a linear queue as it follows the First In First
Out principle with the exception that it connects the last node of a queue to
its first, by forming a circular link. Hence, it is also called a Ring Buffer. The
illustration of a circular queue below shows the connectivity between the
queue’s first and last node.

Additionally, a circular queue manages memory efficiently because of its

circular link. If the rear pointer has reached the maxsize of a queue, it will
again arrive at the beginning of a queue. Bringing the rear node to the
beginning of a queue is called circular incrementation. The image given below
shows how to achieve circular incrementation
.

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 10 of 20

8.5.2 Deque Operations
The following operations can be applied on a Deque data structure:
▪ Insertion at front
▪ Insertion at rear
▪ Deletion at front
▪ Deletion at rear

The peek () operations can be performed along side along with the operations
listed above. Through peek operation, we can get the deque's front and rear
elements of the deque. So, in addition to the above operations, the following
operations are also supported in deque:

▪ Get the front item from the deque

▪ Get the rear item from the deque
▪ Check whether the deque is full or not (isFull ())
▪ Checks whether the deque is empty or not (isEmpty ())

8.5.2.1 Insertion at front/ enqueue_Front()

In this operation, the element is inserted from the front end of the queue.
Before implementing the operation, we first have to check whether the queue
is full or not. If the queue is not full, then the element can be inserted from
the front end by using the conditions below:

▪ If the queue is empty, both rear and front are initialized with 0. Now,
both will point to the first element.
▪ Otherwise, check the position of the front if the front is less than 1 (front
< 1), then reinitialize it by front = n - 1, i.e., the last index of the array.

The diagram below shows insertion at the front of Dequeue take places.

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 11 of 20

The algorithm for Insertion at front is given below:

Insertion_at_front()
[ The algorithm insert an item at the front of Dequeue

Step-1: [Check for the front position]

if(front<=1)
Print("Cannot add item at the front”);
return;
[Insert at front]
else
front=front-1;
q[front]=no;
[End of if structure]
Step-2: Return

8.5.2.2 Insertion at rear/enqueue_Rear ()

In this operation, the element is inserted from the rear end of the queue. Before
implementing the operation, we first have to check again whether the queue is full or
not. If the queue is not full, then the element can be inserted from the rear end by
using the below conditions -
▪ If the queue is empty, both rear and front are initialized with 0. Now, both will
point to the first element.
▪ Otherwise, increment the rear by 1. If the rear is at last index (or size - 1), then
instead of increasing it by 1, we have to make it equal to 0.

The algorithm for Insertion at the Rear is given below:

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 12 of 20

 Insertion_at_Rear()
[ The algorithm insert an item at the rear of Dequeue

Step-1: [Check for overflow]

if(rear= =MAX)
Print("Queue is Overflow”);
return;
[Insert Element]
else
rear=rear+1;
q[rear]=no;
[end of if -structure]
Step-2: [Set rear and front pointer]
if rear=0
rear=1;
if front=0
front=1;
[end of if -structure]

Step-3: return

8.5.2.3 Deletion at front

In this operation, the element is deleted from the front end of the queue.
Before implementing the operation, we first have to check whether the queue
is empty or not. If the queue is empty, i.e., front = -1, it is the underflow
condition, and we cannot perform the deletion. If the queue is not empty, then
the element can be deleted from the front end by using the conditions below:

▪ If the deque has only one element, set rear = -1 and front = -1.
▪ Else if front is at end (that means front = size - 1), set front = 0.
▪ Else increment the front by 1, (i.e., front = front + 1).

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 13 of 20

The algorithm for Deletion at front is given below:
Deletion_at_Front()
[ The algorithm delete an item at the front of Dequeue

Step-1 [ Check for front pointer]

if front=0
print(" Queue is Underflow”);
return;
[Perform deletion]
else
no=q[front];
print(“Deleted element is”,no);
Step -2: [Set front and rear pointer]
if front=rear
front=0;
rear=0;
else
front=front+1;
Step-3: Return

8.5.2.4 Deletion at rear

In this operation, the element is deleted from the rear end of the queue. Before
implementing the operation, we first have to check whether the queue is
empty or not.
▪ If the queue is empty, i.e., front = -1, it is the underflow condition, and
we cannot perform the deletion.
▪ If the deque has only one element, set rear = -1 and front = -1.
▪ If rear = 0 (rear is at front), then set rear = n - 1.
Else, decrement the rear by 1 (or, rear = rear -1).

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 14 of 20

The algorithm for Deletion at the rear is given below:

Deletion_at_Rear ()
[ The algorithm delete an item at the rear of Dequeue]

Step-1: [Check for the rear pointer]

if rear=0
print (“Cannot delete value at rear end”);
return;
[perform deletion]
else
no=q[rear];
[Check for the front and rear pointer]
[end of if- structure]
Step-2: if front= rear
front=0;
rear=0;
else
rear=rear-1;
print (“Deleted element is”, no);
Step-3: Return

8.5.2.5 Peek () Operation

Through peek operation, we can get the deque's front and rear elements of the
deque.

8.5.2.6 Check empty: isEmpty() Operation

This operation is performed to check whether the deque is empty or not. If
front = -1, it means that the deque is empty.

8.5.2.7 Check full: isFull() Operation

This operation is performed to check whether the deque is full or not. If front
= rear + 1, or front = 0 and rear = n - 1 it means that the deque is full.

8.5.3 Complexity of Deque Operations

The time complexity of all the Dequeue operations is constant i.e., O (1). The
Space complexity of all Dequeue operations O(1) as no extra space is utilized
to access the first value.

8.5.4 Applications of Dequeue

Some of the applications of Dequeue data structure are:
(a) Support for Stack and Queue: Deque can be used as both stack and
queue, as it supports both operations.

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 15 of 20

 (b) Palindrome Checker: A palindrome is a sequence of characters (letters,
digits, or other symbols) that reads the same forward as it does
backward. In other words, a palindrome remains unchanged when its
characters are reversed. The program to check if the given string is
palindrome or not can be implemented using deque in a data structure.
If the string reads the same from both the deque ends, it will consider
it a palindrome.
(c) Multiprocessor Scheduling: When multiple processes are being
executed by multiple processors (CPU, Core) in a system, then that
system utilizes a multiprocessor scheduling algorithm. In this
algorithm, the deque is used by each processor to store different threads
of processes. This algorithm is also called the A-Steal algorithm for
scheduling.
(d) Graph traversal: Deques can be used to implement Breadth-First
Search (BFS) on a graph. BFS uses a queue to keep track of the vertices
to be visited next, and a deque can be used as an alternative to a queue
in this case.
(e) Task scheduler: Deques can be used to implement a task scheduler
that keeps track of tasks to be executed. Tasks can be added to the
back of the deque, and the scheduler can remove tasks from the front
of the deque and execute them.
(f) Multi-level undo/redo functionality: Deques can be used to
implement undo and redo functionality in applications. Each time a
user performs an action, the current state of the application is pushed
onto the deque. When the user undoes an action, the front of the deque
is popped, and the previous state is restored. When the user redoes an
action, the next state is popped from the deque.

8.6 Priority Queues

A Priority queue is an abstract data type that behaves similarly to the normal
queue except that each element has some priority, i.e., the element with the
highest priority would come first in a 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 arc deleted and
processed comes from the following rules:
(a) An element of higher priority is processed before any element of
lower priority.
(b) Two elements with the same priority arc processed according to the
order in which they were added to the queue.

The priority queue supports only comparable elements, which means that the
elements are either arranged in an ascending or descending order.

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 16 of 20

For example, suppose we have some values like 1, 3, 4, 8, 14, 22 inserted in
a priority queue with an ordering imposed on the values is from least to the
greatest. Therefore, the 1 number would be having the highest priority while
22 will be having the lowest priority.

A prototype of a priority queue is a timesharing system: programs of high

priority are processed first, and programs with the same priority form a
standard queue.

The hospital emergency queue is an ideal real-life example of a priority queue.

In this queue of patients, the patient with the most critical situation is the
first in a queue, and the patient who does not need immediate medical
attention will be the last. In this queue, the priority depends on the medical
condition of the patients.

8.6.1 Types of Priority Queue

There are two types of priority queue:
(a) Ascending order Priority Queue: In ascending order priority queue, a
lower priority number is given as a higher priority in a priority. For
example, we take the numbers from 1 to 5 arranged in an ascending
order like 1,2,3,4,5; therefore, the smallest number, i.e., 1 is given as
the highest priority in a priority queue.

(b) Descending order Priority Queue: In descending order priority queue,

a higher priority number is given as a higher priority in a priority. For
example, we take the numbers from 1 to 5 arranged in descending order
like 5, 4, 3, 2, 1; therefore, the largest number, i.e., 5 is given as the
highest priority in a priority queue.

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 17 of 20

8.6.2 Representation of Priority Queue
The Priority queue can be implemented in four ways that include arrays,
linked list, heap data structure and binary search tree.

Among these data structures, heap data structure provides an efficient

implementation of priority queues. A comparative analysis of different
implementations of priority queue is given below.

Implementation Add/Enqueue Remove/Dequeue peek

Arrays O(1) O(n) O(n0
Linked list O(1) O(n) O(n)
Binary heap O(logn) O(logn) O(1)
Binary search tree O(logn) O(logn) O(1)

8.6.3 Priority Queue Operations

The common operations that we can perform on a priority queue are insertion,
deletion and peek.

8.6.3.1 Insert / Enqueue Operation

Whenever an element is inserted into queue, priority queue inserts the item
according to its order. Here we are assuming that data with high value has
low priority.

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 18 of 20

8.6.3.2 Remove / Dequeue Operation
Whenever an element is to be removed from queue, queue get the element
using item count. Once element is removed. Item count is reduced by one.

8.6.3.3 Peeking from the Priority Queue (Find max/min)

Peek operation returns the maximum element from Max Heap or minimum
element from Min Heap without deleting the node.

8.6.3.4 Extract-Max/Min from the Priority Queue

Extract-Max returns the node with maximum value after removing it from a
Max Heap whereas Extract-Min returns the node with minimum value after
removing it from Min Heap.

8.7 Applications of Priority Queue

The following are some of the applications of the priority queue in data
structures:

(a) IP Routing to Find Open Shortest Path First: OSPF is a link-state

routing protocol that is used to find the best path between the source
and the destination router. This protocol works on the principle of
Dijkstra’s shortest path algorithm by using a priority queue to track an
optimal route.
(b) Data Compression in WINZIP / GZIP: The Huffman encoding
algorithm uses a priority queue to maintain the codes for data contents.
They store these codes in a min heap, considering the size of codes as
a parameter to decide the priority.
(c) Implementing the Prim’s algorithm: Prim’s algorithm generates a
minimum spanning tree from an undirected, connected, and weighted
graph. It uses a min priority queue to maintain the order of elements
for generating a minimum spanning tree.

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 19 of 20

 (d) Used to perform the heap sort: When you provide an unsorted array
to this algorithm, it converts it into a sorted array. This algorithm uses
a min priority queue to generate an order of elements.
(e) Load balancing and Interrupt handling: Load balancing fields the
requests from the users and distributes them to different available
servers. Whereas, interrupt handling is a mechanism for handling
interrupts in OS. The priority queue is used to manage requests, and it
interrupts both functionalities simultaneously.

Data Structure and Algorithm (Compiled by Idepefo, F.0) Page 20 of 20