LECTURE – QUEUE

DATA STRUCTURE & ALGORITHMS

MR. MUHAMMAD SALEEM

LECTURER
DEPARTMENT OF COMPUTER SCIENCE

Dawood University of Engineering and Technology, Karachi

CONTENTS

◼ Introduction Queue
◼ Applications of the Queue
◼ Complexity Chart
◼ Types of Queue
◼ Simple/Linear Queue
◼ Circular Queue
◼ Priority Queue
◼ Double Ended Queue

2
QUEUE

◼ A queue can be defined as an ordered list which enables insert operations to be performed
at one end called REAR and delete operations to be performed at another end
called FRONT.
◼ Queue is referred to be as First In First Out list (FIFO).
◼ For example, people waiting in line for a rail ticket form a queue.

[Link]@[Link] 11/28/2024 3
QUEUE REPRESENTATIONS

[Link]@[Link] 11/28/2024 4
APPLICATIONS OF QUEUE

◼ Due to the fact that queue performs actions on first in first out basis which is quite fair for the ordering
of actions. There are various applications of queues discussed as below.
1. Queues are widely used as waiting lists for a single shared resource like printer, disk, CPU.
2. Queues are used in asynchronous transfer of data (where data is not being transferred at the same rate
between two processes) for eg. pipes, file IO, sockets.
3. Queues are used as buffers in most of the applications like MP3 media player, CD player, etc.
4. Queue are used to maintain the play list in media players in order to add and remove the songs from
the play-list.
5. Queues are used in operating systems for handling interrupts.

[Link]@[Link] 11/28/2024 5
COMPLEXITY

Data Structure Time Complexity

Average Worst

Access Search Insertion Deletion Access Search Insertion Deletion

Queue θ(n) θ(n) θ(1) θ(1) O(n) O(n) O(1) O(1)

[Link]@[Link] 11/28/2024 6
[Link]@[Link] 11/28/2024 7
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.

[Link]@[Link] 11/28/2024 8
SIMPLE QUEUE OR LINEAR QUEUE

◼ 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.

[Link]@[Link] 11/28/2024 9
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 -
[Link]@[Link] 11/28/2024 10
CIRCULAR QUEUE

◼ 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.
[Link]@[Link] 11/28/2024 11
[Link]@[Link]
OPERATIONS ON CIRCULAR QUEUE

• Front: It is used to get the front element from the Queue.

• Rear: It is used to get the rear element from the Queue.
• enQueue(value): This function is used to insert the new value in the
Queue. The new element is always inserted from the rear end.
• deQueue(): This function deletes an element from the Queue. The
deletion in a Queue always takes place from the front end.

[Link]@[Link] 11/28/2024 13
ENQUEUE OPERATION

• First, we will check whether the Queue is full or not.

• Initially the front and rear are set to -1. When we insert the
first element in a Queue, front and rear both are set to 0.
• When we insert a new element, the rear gets incremented,
i.e., rear=rear+1.

[Link]@[Link] 11/28/2024 14
SCENARIOS FOR INSERTING AN ELEMENT

◼ There are two scenarios in which queue is not full:

• If rear != max - 1, then rear will be incremented, and the new value will be inserted at the
rear end of the queue.
• If front != 0 and rear = max - 1, it means that queue is not full, then set the value of rear to 0
and insert the new element there.
◼ There are two cases in which the element cannot be inserted:
• When front ==0 && rear = max-1, which means that front is at the first position of the Queue
and rear is at the last position of the Queue.
• front== rear + 1;

[Link]@[Link] 11/28/2024 15
 ALGORITHM TO INSERT AN ELEMENT

Step 1: IF (REAR+1)%MAX = FRONT Step 3: SET QUEUE[REAR] = VAL

Write " OVERFLOW "
Goto step 4 Step 4: EXIT
[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]

[Link]@[Link] 11/28/2024 16
DEQUE OPERATION

• The steps of dequeue operation are given below:

• First, we check whether the Queue is empty or not. If the queue is
empty, we cannot perform the dequeue operation.
• When the element is deleted, the value of front gets decremented
by 1.
• If there is only one element left which is to be deleted, then the front
and rear are reset to -1.

[Link]@[Link] 11/28/2024 17
 ALGORITHM DEQUE ELEMENT
Step 1: IF FRONT = -1 Step 3: IF FRONT = REAR
Write " UNDERFLOW " SET FRONT = REAR = -1
Goto Step 4 ELSE
[END of IF] IF FRONT = MAX -1
SET FRONT = 0
Step 2: SET VAL = QUEUE[FRONT] ELSE
SET FRONT = FRONT + 1
[END of IF]
[END OF IF]
Step 4: EXIT

[Link]@[Link] 11/28/2024 18
DIAGRAMMATIC REPRESENTATION

[Link]@[Link] 11/28/2024 19
Insert 10

[Link]@[Link]
Insert 20
Insert 30

[Link]@[Link]
Insert 40

[Link]@[Link]
Insert 50

[Link]@[Link] 11/28/2024 23
 Delete 10
Delete 20

[Link]@[Link] 11/28/2024 24
Insert 60

[Link]@[Link] 11/28/2024 25
Insert 70

[Link]@[Link] 11/28/2024 26
APPLICATIONS OF CIRCULAR QUEUE

• Memory management: The circular queue provides memory management. As we have

already seen that in linear queue, the memory is not managed very efficiently. But in case of
a circular queue, the memory is managed efficiently by placing the elements in a location
which is unused.
• CPU Scheduling: The operating system also uses the circular queue to insert the processes
and then execute them.
• Traffic system: In a computer-control traffic system, traffic light is one of the best examples
of the circular queue. Each light of traffic light gets ON one by one after every jinterval of
time. Like red light gets ON for one minute then yellow light for one minute and then green
light. After green light, the red light gets ON.

[Link]@[Link] 11/28/2024 27
VISUALIZATION

EXIT ENTER

5 10 25 15 45

Front = NULL

Rear = NULL
[Link]@[Link] 11/28/2024 28
VISUALIZATION

Front

EXIT 5 ENTER

Rear
10 25 15 45

[Link]@[Link] 11/28/2024 29
VISUALIZATION

Front

EXIT 5 ENTER

RearRear
10 25 15 45

[Link]@[Link] 11/28/2024 30
VISUALIZATION

Front

EXIT 5 10 ENTER

Rear Rear
25 15 45

[Link]@[Link] 11/28/2024 31
VISUALIZATION

Front

EXIT 5 10 25 ENTER

Rear Rear
15 45

[Link]@[Link] 11/28/2024 32
VISUALIZATION

Front

EXIT 5 10 25 15 ENTER

Rear Rear
45

[Link]@[Link] 11/28/2024 33
VISUALIZATION

Front

EXIT 5 10 25 15 45 ENTER

Rear

[Link]@[Link] 11/28/2024 34
VISUALIZATION

Front

EXIT 5 10 25 15 45 ENTER

Rear

[Link]@[Link] 11/28/2024 35
VISUALIZATION

Front

EXIT 10 25 15 45 ENTER

Rear

[Link]@[Link] 11/28/2024 36
VISUALIZATION

Front

EXIT 25 15 45 ENTER

Rear

[Link]@[Link] 11/28/2024 37
VISUALIZATION

Front

EXIT 25 15 45 ENTER

Rear

[Link]@[Link] 11/28/2024 38
VISUALIZATION

Front

EXIT 15 45 ENTER

Rear

[Link]@[Link] 11/28/2024 39
VISUALIZATION

Front

EXIT 45 ENTER

Rear

[Link]@[Link] 11/28/2024 40
VISUALIZATION

EXIT ENTER

Front = -1
Rear = -1
[Link]@[Link] 11/28/2024 41
 Priority Queue

[Link]@[Link] 11/28/2024 42
PRIORITY QUEUE

◼ 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.
◼ The priority of the elements in a priority queue will determine the order in which elements
are removed from the priority queue.
◼ The priority queue supports only comparable elements, which means that the elements are
either arranged in an ascending or descending order.

[Link]@[Link] 11/28/2024 43
PRIORITY QUEUE

◼ 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.

[Link]@[Link] 11/28/2024 44
CHARACTERISTICS OF PRIORITY QUEUE

• Every element in a priority queue has some priority associated with it.
• An element with the higher priority will be deleted before the deletion of the lesser priority.
• If two elements in a priority queue have the same priority, they will be arranged using the
FIFO principle.

[Link]@[Link] 11/28/2024 45
LET'S UNDERSTAND THE PRIORITY QUEUE THROUGH AN EXAMPLE.

We have a priority queue that contains the following values:

1, 3, 4, 8, 14, 22
◼ All the values are arranged in ascending order. Now, we will observe how the priority queue will look
after performing the following operations:
• poll(): This function will remove the highest priority element from the priority queue. In the above
priority queue, the '1' element has the highest priority, so it will be removed from the priority queue.
• add(2): This function will insert '2' element in a priority queue. As 2 is the smallest element among
all the numbers so it will obtain the highest priority.
• poll(): It will remove '2' element from the priority queue as it has the highest priority queue.
• add(5): It will insert 5 element after 4 as 5 is larger than 4 and lesser than 8, so it will obtain the third
highest priority in a priority queue.

[Link]@[Link] 11/28/2024 46
TYPES OF PRIORITY QUEUE

◼ Types of Priority Queue

◼ There are two types of priority queue:
◼ Ascending Order Priority Queue
◼ Descending Order Priority Queue

[Link]@[Link] 11/28/2024 47
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.

[Link]@[Link] 11/28/2024 48
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.

[Link]@[Link] 11/28/2024 49
REPRESENTATION OF PRIORITY QUEUE

◼ Now, we will see how to represent the priority queue through a one-way list.
◼ We will create the priority queue by using the list given below in which:
◼ INFO list contains the data elements,
◼ PRN list contains the priority numbers of each data element available in the INFO list, and
◼ LINK basically contains the address of the next node.

[Link]@[Link] 11/28/2024 50
MAKE A PRIORITY QUEUE BASED ON GIVEN DATA

[Link]@[Link] 11/28/2024 51
IMPLEMENTATION OF PRIORITY QUEUE

◼ The priority queue can be implemented in four ways that include arrays, linked list, heap
data structure and binary search tree.
◼ The heap data structure is the most efficient way of implementing the priority queue, so we
will implement the priority queue using a heap data structure in this topic.

[Link]@[Link] 11/28/2024 52
 Thanks!
For The Time & Attention

Do You Have Any Question?

[Link]@[Link]
+923333217216

For more information: [Link]