BIM SEM - III
Data Structures & Algorithms
Unit-4: Queues
Introduction
A queue is a linear list of elements in which deletion of an element can take place
at one end called the front or head and insertion can take place on the other end
which is termed as the rear or tail. The term front and rear are frequently used
while describing queues in a linked list.
In the concept of a queue, the first element to be inserted in the queue will be the
first element to be deleted or removed from the list. So Queue is said to follow the
FIFO (First In First Out) structure. A real-life scenario in the form of example for
queue will be the queue of people waiting to accomplish a particular task where the
first person in the queue is the first person to be served first.
Teksan Gharti
Other examples can also be noted within a computer system where the queue of
tasks arranged in the list to perform for the line printer, for accessing the disk
storage, or even in the time-sharing system for the use of CPU. So basically queue
is used within a single program where there are multiple programs kept in the
queue or one task may create other tasks which must have to be executed in turn by
keeping them in the queue.
Front: It is a first position of the queue where element is popped out
Lecturer: Teksan Gharti Magar
BIM SEM - III
Data Structures & Algorithms
Rear: It is a last position of the queue, where element is inserted
Enqueue(): it is the operation of inserting the element in the queue
Dequeue(): it is the operation of deleting the element in the queue
Queue as an ADT (Abstract Data Type)
The meaning of an abstract data type clearly says that for a data structure to be
abstract, it should have the below-mentioned characteristics:
First, there should be a particular way in which components are related to
each other
Second, a statement for the operation that can be performed on elements of
abstract data type must have to be specified
Thus for defining a Queue as an abstract data type, these are the following criteria:
Initially a queue to be empty
Check whether a queue is empty or not
Teksan Gharti
Check whether a queue is full or not
Insert a new element after the last element in a queue, if the queue is not full
Retrieve the first element of the queue, if it is not empty
Delete the first element in a queue, if it is not empty
Primitive operations in the queue
Queue operations may involve initializing or defining the queue, utilizing it, and
then completely erasing it from the memory. Following are the primitive or basic
operations performed in the queue:
initialize: this operation is used to initialize the queue
enqueue(): this function is used to insert the element in the queue
dequeue(): this function is used to delete the element from the queue
peek(): this function is used to get element from the front position of
thqueue
isFull(): this function is used to check the queue is full or not
Lecturer: Teksan Gharti Magar
BIM SEM - III
Data Structures & Algorithms
isEmpty():this function is used to check the queue is empty or no
Linear Queue
A linear queue is a linear data structure that serves the request first, which has been
arrived first, also called FIFO. It consists of data elements which are connected in a
linear fashion. It is so called linear because it resembles to a straight line where the
elements are positioned one after the other. It contains a homogeneous collection
of the elements in which new elements are added at one end and deleted from
another end. It has two pointers, i.e., front and rear, where the insertion takes place
from the rear end, and deletion occurs from the front end.
Enqueue operation of linear queue
Algorithm for enqueue operation
Step1: Start
Step2: Check if the queue is full. Teksan Gharti
Step3: If the queue is full, produce overflow error and exit.
Step4: If the queue is not full, increment rear pointer to point the next empty
space.
Step5: Add data element to the queue location, where the rear is pointing.
Step6: Stop
Lecturer: Teksan Gharti Magar
BIM SEM - III
Data Structures & Algorithms
Dequeue operation of linear queue
Algorithm for dequeue operation
Step1: Start Teksan Gharti
Step2: Check if the queue is empty.
Step3: If the queue is empty, produce underflow error and exit.
Step4: If the queue is not empty, access the data where front is pointing.
Step5: Increment front pointer to point to the next available data element.
Step6: Stop
Lecturer: Teksan Gharti Magar
BIM SEM - III
Data Structures & Algorithms
Dra
wback of Linear Queue
The linear queue suffers from serious drawback that performing some operations,
we cannot insert items into queue, even if there is space in the queue. Suppose we
have queue of 5 elements and we insert 5 items into queue, and then delete some
Teksan Gharti
items, then queue has space, but at that condition we cannot insert items into
queue.
Applications of Queue
Queue, as the name suggests is used whenever we need to manage any group of
objects in an order in which the first one coming in, also gets out first while the
others wait for their turn, like in the following scenarios:
1. Serving requests on a single shared resource, like a printer, CPU task
scheduling, buffer of keyboard etc.
2. In real life scenario, Call Center phone systems uses Queues to hold people
calling them in an order, until a service representative is free.
3. Handling of interrupts in real-time systems. The interrupts are handled in the
same order as they arrive i.e First come first served.
4. In Networks: Queues in routers/ switches, Mail Queues
Lecturer: Teksan Gharti Magar
BIM SEM - III
Data Structures & Algorithms
5. When data is transferred asynchronously (data not necessarily received at
same rate as sent) between two processes. Examples include IO Buffers,
pipes, file IO, etc.
Circular Queue
A circular queue is a variant of the linear queue which effectively overcomes
the limitation of the linear queue. In circular queue, the new element is added at the
very first position of the queue if the last is occupied and space is available.
Circular queue connects the two ends through a pointer where the very first
element comes after the last element. It also keeps track of the front and rear by
implementing some extra logic so that it could trace the elements that are to be
inserted and deleted. With this, the circular queue does not generate the overflow
condition until the queue is full in actual. In the circular queue, when the rear
reaches the end of the queue, then rear is reset to zero. It helps in refilling all the
free spaces.
Teksan Gharti
Conditions for the queue to be a circular queue
q[0] comes after q[n-1]
Lecturer: Teksan Gharti Magar
BIM SEM - III
Data Structures & Algorithms
Enqueue: It inserts an element in a queue.
Algorithm for enqueue operation
Step1: Start
Step2: Check queue is full or not.
If queue is full, display error message as “Queue is overflow” and go to
step4
Step3: Check queue is empty or not.
If the queue is empty i.e. front and rear value is -1, then the front and rear
are set to 0 to insert a new element.
If queue is not empty, then the value of the rear gets incremented by 1.
If queue is not empty and rear is equal to n-1, then rear is set to 0
Step4: Stop
Teksan Gharti
Dequeue: It performs a deletion operation in the Queue.
Algorithm for dequeue operation
Step1: Start
Step2: Check queue is empty or not.
If queue is empty, display error message as “Queue is underflow” and go to
step4
Step3: Check queue is not empty,
If queue is not empty, the value of front gets incremented by 1.
If there is only one element in a queue, after dequeue operation is performed
on the queue, the queue will become empty. In this case, the front and rear
values are set to -1.
Lecturer: Teksan Gharti Magar
BIM SEM - III
Data Structures & Algorithms
If the value of the front is equal to n-1, after the dequeue operation is
performed, the value of the front variable is set to 0.
Step4: Stop
Example: Following diagram shows the enqueue and deque operation in circular
queue.
At initial state, let’s consider queue is empty i.e. front=-1, rear=-1
Teksan Gharti
Applications of Circular Queue
Lecturer: Teksan Gharti Magar
BIM SEM - III
Data Structures & Algorithms
The circular Queue can be used in the following scenarios:
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 j-interval 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.
Difference between Linear and Circular Queue
Basis of Linear Queue Circular Queue
comparison
Teksan Gharti
Meaning The linear queue is a The circular queue is also a linear
type of linear data data structure in which the last
structure that contains element of the Queue is connected
the elements in a to the first element, thus creating a
sequential manner. circle.
Insertion and In linear queue, insertion In circular queue, the insertion and
Deletion is done from the rear deletion can take place from any
end, and deletion is done end.
from the front end.
Memory space The memory space It requires less memory as
occupied by the linear compared to linear queue.
queue is more than the
circular queue.
Lecturer: Teksan Gharti Magar
BIM SEM - III
Data Structures & Algorithms
Memory The usage of memory is The memory can be more
utilization inefficient. efficiently utilized.
Order of It follows the FIFO It has no specific order for
execution principle in order to execution.
perform the tasks.
Priority Queue
A priority queue is a collection of elements such that each element has been
assigned a priority value such that the order in which elements are deleted and
processed comes from the following rules
1. An element of higher priority is processed before any element of lower
priority.
2. Two elements with the same priority are processed according to the order in
which they were added to the queue. Teksan Gharti
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.
Then, priority queue is:
1 3 4 8 14 22
Front Rear
Example1: we have a priority queue that contains the following values:
1 3 4 8 14 22
Lecturer: Teksan Gharti Magar
BIM SEM - III
Data Structures & Algorithms
Front Rear
All the values are arranged in ascending order. Now, we will observe how the
priority queue will look after performing the following operations:
pull(): This function will remove the highest priority element from front position
of the priority queue. In the above priority queue, the '1' element in the front
position and has the highest priority, so it will be removed from the priority queue.
Then, new queue becomes:
3 4 8 14 22
add(2): This function will insert '2' element in a priority queue. Here 2 will be
compare with the each element of the queue and shift highest value or lowest
priority element towards right.
Then, new queue becomes:
2 3 4 8 14 Teksan Gharti
22
pull(): It will remove '2' element from the priority queue as it has the highest
priority queue.
Then, new queue becomes:
3 4 8 14 22
add(5): It will insert element 5 before 8 and after 4, because 5 is larger than 4 and
lesser than 8,
Then, new queue becomes:
3 4 5 8 14 22
There are two types of priority queue:
Lecturer: Teksan Gharti Magar
BIM SEM - III
Data Structures & Algorithms
Ascending order priority queue: In ascending order priority queue, a smaller
number element 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
priority queue.
Teksan Gharti
Descending order priority queue: In descending order priority queue, a larger
number element is given as a higher priority in a priority queue.
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.
Lecturer: Teksan Gharti Magar
BIM SEM - III
Data Structures & Algorithms
Representation of priority queue in list
Let’s take an example: Teksan Gharti
New, the priority queue using list is
End of Unit-3
Lecturer: Teksan Gharti Magar
BIM SEM - III
Data Structures & Algorithms
Teksan Gharti
Lecturer: Teksan Gharti Magar