UNIT 6 QUEUE

Syllabus
 Basic concept, Queue as Abstract Data Type, Representation of
Queue using Sequential organization, Queue Operations,
Circular Queue and its advantages, Multi-queues, Linked Queue
and Operations. Deque- Basic concept, types (Input restricted
and Output restricted), Priority Queue- Basic concept, types
(Ascending and Descending).
 Queue
 A Queue is a linear data structure that keeps its elements in a
queue.

 We often use queues in our everyday life. For example, queue at

the supermarket, queue at the airport, and so on...

 Queue in data structures is used to develop online food delivery

applications like Domino’s, Swiggy and Zomato? This is because
it serves the purpose of the First-Come-First-Serve strategy of
software development.
 Cont..
 Queues are data structures that follow the First In First Out
(FIFO) i.e. the first element that is added to the queue is the
first one to be removed.
 The basic queue operations are enqueue (insertion) and
dequeue (deletion). Enqueue is done at the rear of the queue
and dequeue is done at the front of the queue.
 The One end is called front Other end is called rear
 Queue Operation or ADT of
5
Queue
 A queue is an object or more specifically an abstract
data structure(ADT) that allows the following
operations:
 Enqueue: Add an element to the end of the queue
 Dequeue: Remove an element from the front of the
queue
 IsEmpty: Check if the queue is empty
 IsFull: Check if the queue is full
 Peek: Get the value of the front of the queue without
removing it
 Queue ADT
6

AbstractDataType queue {
instances
ordered list of elements; one end is the front; the other is the rear;
operations
empty(): Return true if queue is empty, return false
otherwise
size(): Return the number of elements in the queue
front(): Return the front element of queue
back(): Return the back (rear) element of queue
dequeue(): Remove an element from the queue
enqueue(x): Add element x to the queue
} is also possible to represent Queues using
It
1. Array-based representation
2. Linked representation
Array representation
 A queue data structure can be implemented using one dimensional array with
fixed number of data values.

 Just define a one dimensional array of specific size and insert or delete the
values into that array by using FIFO (First In First Out) principle with the
help of variables 'front' and 'rear'.

 Initially both 'front' and 'rear' are set to -1. Whenever, we want to insert a new
value into the queue, increment 'rear' value by one and then insert at that
position.

 Whenever we want to delete a value from the queue, then delete the element
 Linked List representation
 Sometimes the number of elements in the queue is not specified
in the start; thus, a linked list represents a queue of elements.

 In this case, a structure is created having an integer key and a

pointer as its elements. And 2 such structure variables are
created to point the front and queue element of the array.
Queue Operation
 Queue: Array
Implementation
 A queue data structure can be implemented using one
dimensional array.

 The queue implemented using array stores only fixed number

of data values.

 The implementation of queue data structure using array is very

simple.

 Just define a one dimensional array of specific size and insert

or delete the values into that array by using FIFO (First In
First Out) principle with the help of variables 'front' and
'rear'.
 Cont..
11

 Initially both 'front' and 'rear' are set to -1.

 Whenever, we want to insert a new value into the

queue, increment 'rear' value by one and then
insert at that position.

 Whenever we want to delete a value from the

queue, then delete the element which is at 'front'
position and increment 'front' value by one.
 Cont..
12

 Before enqueuing, we check if the queue is already full.

 Before dequeuing, we check if the queue is already empty.

 When enqueuing the first element, we set the value of

FRONT to 0 and increment value of rare by 1 i.e. rear=0.

 When dequeuing the last element, we reset the values of

FRONT and REAR to -1.
 Queue Implementation
13
using Array
 Before we implement actual operations, first follow the below
steps to create an empty queue.
 Step 1 - Include all the header files which are used in the
program and define a constant 'SIZE' with specific value.
 Step 2 - Declare all the user defined functions which are used
in queue implementation.
 Step 3 - Create a one dimensional array with above defined
SIZE (int queue[SIZE])
 Step 4 - Define two integer variables 'front' and 'rear' and
initialize both with '-1'. (int front = -1, rear = -1)
 Step 5 - Then implement main method by displaying menu of
operations list and make suitable function calls to perform
operation selected by the user on queue.
 enQueue(value) - Inserting value into
the queue
14

 In a queue data structure, enQueue() is a function used

to insert a new element into the queue.

 In a queue, the new element is always inserted

at rear position.

 The enQueue() function takes one integer value as a

parameter and inserts that value into the queue.

 We can use the following steps to insert an element into

the queue...
 Cont..
15

 Step 1 - Check whether queue is FULL. (rear == SIZE-1)

 Step 2 - If it is FULL, then display "Queue is FULL!!!

Insertion is not possible!!!" and terminate the function.

 Step 3 - If it is NOT FULL, then increment rear value by one

(rear++) and set queue[rear] = value.
 deQueue() - Deleting a value from the
Queue
16

 In a queue data structure, deQueue() is a function used to

delete an element from the queue.

 In a queue, the element is always deleted from front position.

 The deQueue() function does not take any value as

parameter.

 We can use the following steps to delete an element from the

queue...
 Cont..
17

 Step 1 - Check whether queue is EMPTY. (front == rear)

 Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!

Deletion is not possible!!!" and terminate the function.

 Step 3 - If it is NOT EMPTY, then increment the front value by

one (front ++).
Then display queue[front] as deleted element.
Then check whether both front and rear are equal
(front == rear), if it TRUE, then set both front and rear to '-1'
(front = rear = -1).
 display() - Displays the elements of a
Queue
18
 We can use the following steps to display the elements of a queue...
 Step 1 - Check whether queue is EMPTY. (front == rear)
 Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!" and
terminate the function.
 Step 3 - If it is NOT EMPTY, then define an integer variable 'i' and
set 'i = front+1'.
 Step 4 - Display 'queue[i]' value and increment 'i' value by one (i+
+). Repeat the same until 'i' value reaches to rear (i <= rear)

 Queue using Array

 The complexity of enqueue and dequeue operations in a queue
using an array is O(1).
 Queue using Linked List
19
 The major problem with the queue implemented using an array is, It will work
for an only fixed number of data values.

 That means, the amount of data must be specified at the beginning itself.
Queue using an array is not suitable when we don't know the size of data
which we are going to use.

 A queue data structure can be implemented using a linked list data structure.

 The queue which is implemented using a linked list can work for an unlimited
number of values.

 That means, queue using linked list can work for the variable size of data (No
need to fix the size at the beginning of the implementation). The Queue
implemented using linked list can organize as many data values as we want.
 Cont..
20

 In linked list implementation of a queue, the last

inserted node is always pointed by 'rear' and
the first node is always pointed by 'front'.

In above example, the last inserted node is 50 and it is pointed by 'rear' and the
first inserted node is 10 and it is pointed by 'front'.
The order of elements inserted is 10, 15, 22 and 50.
 Operations
21

 To implement queue using linked list, we need to set the

following things before implementing actual operations.
 Step 1 - Include all the header files which are used in the
program. And declare all the user defined functions.
 Step 2 - Define a 'Node' structure with two
members data and next.
 Step 3 - Define two Node pointers 'front' and 'rear' and
set both to NULL.
 Step 4 - Implement the main method by displaying Menu
of list of operations and make suitable function calls in
the main method to perform user selected operation.
 enQueue(value) - Inserting an element
into the Queue
22

 We can use the following steps to insert a new node into the
queue...
 Step 1 - Create a newNode with given value and set
'newNode → next' to NULL.

 Step 2 - Check whether queue is Empty (rear == NULL)

 Step 3 - If it is Empty then,

set front = newNode and rear = newNode.

 Step 4 - If it is Not Empty then, set rear → next = newNode

and rear = newNode.
 deQueue() - Deleting an Element from
Queue
23

 We can use the following steps to delete a node from the queue...
 Step 1 - Check whether queue is Empty (front == NULL).

 Step 2 - If it is Empty, then display "Queue is Empty!!! Deletion

is not possible!!!" and terminate from the function

 Step 3 - If it is Not Empty then, define a Node pointer 'temp' and

set it to 'front'.

 Step 4 - Then set 'front = front → next' and delete 'temp'

(free(temp)).
 display() - Displaying the elements of
Queue
24

 We can use the following steps to display the elements

(nodes) of a queue...
 Step 1 - Check whether queue is Empty (front == NULL).
 Step 2 - If it is Empty then, display 'Queue is Empty!!!' and
terminate the function.
 Step 3 - If it is Not Empty then, define a Node
pointer 'temp' and initialize with front.
 Step 4 - Display 'temp → data --->' and move it to the next
node. Repeat the same until 'temp' reaches to 'rear' (temp →
next != NULL).
 Step 5 - Finally! Display 'temp → data ---> NULL'.
 Linear Queue Usnig Linked list
 Application of Queues
25

 CPU scheduling, Disk Scheduling

 When data is transferred asynchronously between
two processes.Queue is used for synchronization.
eg: IO Buffers, pipes, file IO, etc
 Handling of interrupts in real-time systems.
 Call Center phone systems uses Queues to hold
people calling them in an order
 Drawback of linear Queue
26

 In a Linear queue, once the queue is completely full,

it's not possible to insert more elements.

 Even if we dequeue the queue to remove some of

the elements, until the queue is reset, no new
elements can be inserted. You must be wondering
why?
 Cont..
27

 When we dequeue any element to remove it

from the queue, we are actually moving
the front of the queue forward, thereby
reducing the overall size of the queue. And we
cannot insert new elements, because
the rear pointer is still at the end of the queue.
 Agenda
28

 Circular Queue
 Implementation circular queue
 Circular Queue
29

 Circular Queue is also a linear data structure, which

follows the principle of FIFO(First In First Out), but
instead of ending the queue at the last position, it
again starts from the first position after the last,
hence making the queue behave like a circular data
structure.

 Circular queue avoids the wastage of space in

a regular queue implementation using arrays.
 What is Circular Queue?
30

 A circular queue is a linear data structure in which the

operations are performed based on FIFO (First In First
Out) principle and the last position is connected back to
the first position to make a circle.
 Graphical representation of a circular queue is as
follows...
 How Circular Queue Works
31

Perform basic enqueue and dequeue operation on circular queue

How to calculate index position of front and rear ??

 Operations on Circular
32
Queue:
 Two pointers called FRONT and REAR are used to keep track
of the first and last elements in the queue.

 When initializing the queue, we set the value of FRONT and

REAR to -1.

 On enqueuing an element, we circularly increase the value

of REAR index and place the new element in the position
pointed to by REAR.

 On dequeuing an element, we return the value pointed to

by FRONT and circularly increase the FRONT index.
33

 Before enqueuing, we check if the queue is already full.

 Before dequeuing, we check if the queue is already

empty.

 When enqueuing the first element, we set the value

of FRONT to 0.

 When dequeuing the last element, we reset the values

of FRONT and REAR to -1.
 How to calculate index position of front and rear ??
34

 rear = (rear + 1) % SIZE;

 front = (front + 1) % SIZE;
 Let see the example to understand rule.
 Lets consider circular queue. Initially queue is empty so
front and rear pointer initially set to -1.
35

 Insert 11. after insertion queue state will be

 Insert 22,33,44 and 55.

 Queue will be like this..
36
37
 Algorithm to insert an element in
circular queue
38

 Step 1: IF (REAR+1)%MAX = FRONT

Write " OVERFLOW "
Goto step 4
[End OF IF]
 Step 2: IF FRONT = -1 and REAR = -1
SET FRONT = REAR = 0
ELSE IF REAR = MAX - 1 and FRONT ! = 0
SET REAR = 0
ELSE
SET REAR = (REAR + 1) % MAX
[END OF IF]
 Step 3: SET QUEUE[REAR] = VAL
 Step 4: EXIT
 Algorithm to delete an element from a
circular queue
39

 To delete an element from the circular queue, we must

check for the three following conditions.
 If front = -1, then there are no elements in the queue and
therefore this will be the case of an underflow condition.
 If there is only one element in the queue, in this case, the
condition rear = front holds and therefore, both are set
to -1 and the queue is deleted completely.
 If front = max -1 then, the value is deleted from the front
end the value of front is set to 0.
 Otherwise, the value of front is incremented by 1 and
then delete the element at the front end.
 Algorithm
40

 Step 1: IF FRONT = -1
Write " UNDERFLOW "
Goto Step 4
[END of IF]
 Step 2: SET VAL = QUEUE[FRONT]
 Step 3: IF FRONT = REAR
SET FRONT = REAR = -1
ELSE
IF FRONT = MAX -1
SET FRONT = 0
ELSE
SET FRONT = (FRONT + 1) % MAX
[END of IF]
[END OF IF] Circular Queue
 Step 4: EXIT
 Difference Between Linear Queue and
Circular Queue
41
 Circular Queue
42
Applications
 CPU scheduling
 Memory management
 Traffic Management

 Circular Queue Complexity

 The complexity of the enqueue and dequeue
operations of a circular queue is O(1) for (array
implementations).
 Agenda
43

 Deque
 Types of Deque
 Operation of Deque
 Double Ended Queue
44

 Double Ended Queue is also a Queue data

structure in which the insertion and deletion
operations are performed at both the ends
(front and rear).

 That means, we can insert at both front and rear

positions and can delete from both front and
rear positions.
 Double Ended Queue can be represented in TWO ways,
those are as follows...
45  Input Restricted Double Ended Queue:
 In input restricted double-ended queue, the insertion operation is
performed at only one end and deletion operation is performed at both
the ends.

 Output Restricted Double Ended Queue

 In output restricted double ended queue, the deletion operation is
performed at only one end and insertion operation is performed at both
the ends.
 Deque Operations
46

 There are four basic operations in usage of

Deque that we will explore:
 Insertion at rear end
 Insertion at front end
 Deletion at front end
 Deletion at rear end
 Insert Elements at Front
47

 First we check if the queue is full. If its not full we

insert an element at front end by following the given
conditions :
 If the queue is empty then intialize front and rear to 0.
Both will point to the first element.
48

 Else we decrement front and insert the element. Since we are

using circular array, we have to keep in mind that if front is
equal to 0 then instead of decreasing it by 1 we make it equal to
SIZE-1.
49
 Insert Elements at back
50

 Again we check if the queue is full. If its not full we insert an

element at back by following the given conditions:
 If the queue is empty then intialize front and rear to 0. Both will point to
the first element.
 Else we increment rear and insert the element. Since we are using
circular array, we have to keep in mind that if rear is equal to SIZE-1
then instead of increasing it by 1 we make it equal to 0.
51
 Delete First Element
52

 In order to do this, we first check if the queue is empty.

If its not then delete the front element by following the
given conditions :
 If only one element is present we once again make front and
rear equal to -1.
 Else we increment front. But we have to keep in mind that if
front is equal to SIZE-1 then instead of increasing it by 1 we
make it equal to 0.
53
 Delete Last Element
54

 Inorder to do this, we again first check if the queue is empty.

If its not then we delete the last element by following the
given conditions :
 If only one element is present we make front and rear equal to -1.
 Else we decrement rear. But we have to keep in mind that if rear is
equal to 0 then instead of decreasing it by 1 we make it equal to SIZE-1.
55
 Check if Queue is empty
56

 It can be simply checked by looking where front

points to. If front is still intialized with -1, the
queue is empty.
 Check if Queue is full

57

 Since we are using circular array, we check for

following conditions as shown in code to check if
queue is full.
 Complexity
58

 Deque Code
 Insertion or deletion in the middle is O(n)
 The time complexity of random access by index is
O(1)
 time complexity of all
enque(insert)/deque(delete) operations is O(1)
 Agenda
59

 Priority Queue
 Types of Priority Queue.
 Priority queue
60

 Similar to regular queue.

 The key difference is that each element has a
priority.
 An element with high priority serve before an element
with low priority.
 Priority queue
61

 Priority queue data structure is an abstract data type

that provides a way to maintain a set of elements, each
with an associated value called key.

 Priority Queue is an extension of queue with 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.
 How does priority queue differ from a
queue?
62

 In a queue, the first-in-first-out rule is

implemented whereas, in a priority queue, the
values are removed on the basis of priority. The
element with the highest priority is removed first.

 Priority queue can be implemented using an array,

a linked list, a heap data structure or a binary
search tree. Among these data structures, heap
data structure provides an efficient
implementation of priority queues.
 Types of priority queue
63

 Ascending (min) priority queue

 An ascending priority queue is a collection of items
into which items can be inserted arbitrarily and from
which only the smallest item can be removed.

 Descending (max) priority queue

 An descending priority queue is a collection of items
into which items can be inserted arbitrarily and from
which only the largest item can be removed.
 Implementation of PQ
64

 Array based Implementation

 Linked List based Implementation
 Heap based Implementation
 Array implementation of priority queue
65
 example
66
 Complexity
67
 Cont..
68
 Example
69
 Complexity
70
 Min priority queue using
71
heap
 Min priority queue implemented using min heap
 Each element have a priority or key
 A min-priority queue provides the following
operations:
 insert: add an element to the priority queue.
 minElement: return the smallest element in the
priority queue.
 removeMinElement: remove the smallest element
from the priority queue.
 Notes
72
 Operations max priority
73
queue
 A max-priority queue provides the following
operations:
 insert: add an element to the priority queue.

 maxElement: return the largest element in the

priority queue.

 removeMaxElement: remove the largest element

from the priority queue.
 Cont..
74

 A max-priority queue can also provide these additional

operations:
 size: return the number of elements in the priority queue.
 increaseKey: updates the key of an element to a larger
value.
 updatePriorities: assume the values of the keys have
been changed and reorder the internal state of the priority
queue.
 The names of these methods may be different based on
implementations, but all priority queues should provide a
way to do these or similar operations.
 Implementations
75

 Unordered array
 A simple, yet inefficient implementation, as retrieving
the max element would require searching the entire
array.

 Sorted array
 This is not a very efficient implementation either.
Inserting a new element requires linearly searching the
array for the correct position. Removing similarly
requires a linear time: the rest of the elements need to
be adjusted (shifted) into correct positions.
 Cont..
76

 Hash table
 Although inserting into a hash table takes constant time
(given a good hash function), finding the max element
takes linear time. Therefore, this would be a poor choice
for the underlying data structure.

 Heap
 It turns out that that a heap makes an efficient priority
queue.


 Time complexity
77
 Cont..
78

 Strengths:
 Quickly access the highest-priority
item. Priority queues allow you to peek at the top
item in O(1)O(1) while keeping other operations
relatively cheap (O(lg(n))O(lg(n))).
 Weaknesses:
 Slow enqueues and dequeues. Both operations
take O(lg(n))O(lg(n)) time with priority queues.
With normal first-in, first-out queues, these
operations are O(1)O(1) time.
 Application
79

 Any time you want to handle things with different priority

levels: triaging patients in a hospital, locating the closest
available taxi, or just a to-do list.
 Operating system schedulers may use priority queues to
select the next process to run, ensuring high-priority tasks run
before low-priority ones.
 Certain foundational algorithms rely on priority queues:
 Dijkstra's shortest-path
 A* search (a graph traversal algorithm like BFS)
 Huffman codes (an encoding for data compression)
SPPU Questions Apr 23, Oct 22