BCS-DS-301A: DATA STRUCTURES & ALGORITHMS
Ms. Swati Hans
Assistant Professor, CSE
Manav Rachna International Institute of Research and Studies, Faridabad
1
BCS-DS-301A: DATA STRUCTURES &
ALGORITHMS
Unit3
Queues
Ms. Swati Hans
Assistant Professor, CSE
MRIIRS
2
Queue
• Queue: a collection whose elements are added
at one end (the rear or tail of the queue) and
removed from the other end (the front or head
of the queue)
• A queue is a FIFO (first in, first out) data
structure
• Any waiting line is a queue:
– The check-out line at a grocery store
– The cars at a stop light
– An assembly line
Conceptual View of a Queue
Adding an element
Front of queue
New element is added
to the rear of the queue
Conceptual View of a Queue
Removing an element
New front element of queue
Element is removed
from the front of the
queue
Queue
Implementation of Queue
1. Using Array
2. Using Link List
Application of Queue
Queues are used in a lot of applications, few of them are:
•Queue is used to implement many algorithms like Breadth First Search (BFS), etc.
•It can be also used by an operating system when it has to schedule jobs with equal priority
•Customers calling a call center are kept in queues when they wait for someone to pick up the
calls
Queue
Insertion in Queue using Array
A[0] A[1] A[2] A[3] A[4]
F=R=(-1)
10
A[0] A[1] A[2] A[3] A[4]
F=R=0
10 20
A[0] A[1] A[2] A[3] A[4]
F=0 R=1
Queue
Queue
Operations on Queue
Insertion:
Algorithm:
Step 1: If REAR = MAX – 1 then
Write “Queue is Overflow”
Goto step 4
[End of IF]
Step 2: IF FRONT=-1 and REAR=-1
SET FRONT=REAR=0
ELSE
SET REAR=REAR+1
[END OF IF]
Step 3: SET QUEUE [REAR] =
NUM
Step 4: EXIT
Queue
Example of Deletion in Queue
10 20
A[0] A[1] A[2] A[3] A[4]
F=0 R=1
20
A[0] A[1] A[2] A[3] A[4]
F=R=1
Queue
Example of Deletion in Queue
10 20
A[0] A[1] A[2] A[3] A[4]
F=0 R=1
20
A[0] A[1] A[2] A[3] A[4]
F=R=1
Queue
Operations on Queue
Deletion:
Algorithm:
Step 1: IF FRONT = -1 OR FRONT>REAR
Write “Queue is Underflow”
ELSE
SET VAL=QUEUE [FRONT]
FRONT = FRONT + 1
[END OF IF]
Step 2: EXIT
Queue
Drawback of array implementation
Although, the technique of creating a queue is easy, but there are some
drawbacks of using this technique to implement a queue.
• Static Array Size
•Memory wastage : The space of the array, which is used to store
queue elements, can never be reused to store the elements of that
queue because the elements can only be inserted at front end and the
value of front might be so high so that, all the space before that, can
never be filled.
Queue
Types Of Queue
1. Circular Queue
2. Priority Queue
3. Deque
4. Multiple Queue
Queue
Why Circular Queue is needed?
• Problem:
– Wastage of memory in standard queue in DEQUEUE
operation
Queue
What is Circular Queue?
• The Arrangement of the elements Q[0], Q[1], ..,Q[n] in a circular
fashion with Q[1] following Q[n] is called Circular Queue.
• The last node is connected to first node
to make a circle.
• Initially, Both Front and Rear pointers points
to the beginning of the array.
• It is also known as “Ring Buffer”.
Queue
Queue
Insertion in circular queue
Step 1 - Check whether Circular queue is FULL.
if( Front == (Rear+1)%Max)
then display "Queue is FULL!!! Insertion is not
possible!!!" and terminate the function.
Step 2 - If it is empty or having space, then check
if(Front == -1)
then set Front =0,Rear=0
else
set Rear = (Rear+1)%max
Step 3 - set queue[Rear] = value.
Queue
Deletion in circular queue
Step 1 - Check whether queue is EMPTY. (front == -1)
Step 2 - If it is EMPTY, then display “Circular Queue is
EMPTY!!! Deletion is not possible!!!" and terminate the
function.
Step 3 - Val = queue[front];
Step 4 – if(front==rear)
front = rear = -1;
Step 5 – front = (front+1)%Max;
Step 6 – return Val
Queue
Application of Circular Queue
Traffic light functioning is the best example for circular queues. The
colors in the traffic light follow a circular pattern.
In page replacement algorithms, a circular list of pages is maintained
and when a page needs to be replaced, the page in the front of the
queue will be chosen.
Queue
display() - Displays the elements of a Circular Queue
We can use the following steps to display the elements of a circular queue...
Step 1 - Check whether queue is EMPTY. (front == -1)
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'.
Step 4 – for(i = front; i!=rear; i = (i+1)%Max)
Print Cqueue[i];
end
print(queue[rear]);
Step 5 - Exit
