Data Structures and Algorithms

Queue

Prepared By : Vaishali Koria Data Structure and Algorithms 1

Simple Queue
• A queue is a non-primitive linear data structure.

• It is an homogeneous collection of elements in which new elements are added at

one end called the Rear end (R) and the existing elements are deleted from other
end called the Front end (F).

• A queue follows First In First Out (FIFO)

• In our everyday life we come across many situation where we are wait for the
desired service, there we have to get into a waiting line for our turn to get serviced.

Prepared By : Vaishali Koria Data Structure and Algorithms 2

Simple Queue Algorithms
void Enqueue(int item) q[0] q[1] q[2] q[3] q[4] q[5]
{
if(rear==n−1)
printf("\"Queue Overflow" ");
else
{
rear=rear+1;
q[rear]=item;
}
if (front==−1)
front=0;
return;

} F=-1
R= -1

Prepared By : Vaishali Koria Data Structure and Algorithms 3

Simple Queue Algorithms
void Enqueue(int item) q[0] q[1] q[2] q[3] q[4] q[5]
{
11 12 13 14 15 16
if(rear==n−1)
printf("\"Queue Overflow" ");
else F=0 R= 5
{
rear=rear+1;
q[rear]=item;
}
if (front==−1)
front=0;
return;

Prepared By : Vaishali Koria Data Structure and Algorithms 4

Simple Queue Algorithms
void Enqueue(int item) q[0] q[1] q[2] q[3] q[4]
{
11 12 13 14
if(rear==n−1)
printf("\"Queue Overflow" ");
else F=0 R= 4
{
rear=rear+1;
q[rear]=item;
}
if (front==−1)
front=0;
return;

Prepared By : Vaishali Koria Data Structure and Algorithms 5

Simple Queue Algorithms
void Enqueue(int item) q[0] q[1] q[2] q[3] q[4]
{
11 12 13 14 15
if(rear==n−1)
printf("\"Queue Overflow" ");
else F=0 R= 4
{
rear=rear+1;
q[rear]=item;
}
if (front==−1)
front=0;
return;

Prepared By : Vaishali Koria Data Structure and Algorithms 6

 Simple Queue Algorithms
int dequeue() q[0] q[1] q[2] q[3] q[4] q[5]
{
if (front==−1)
{
printf("\"Underflow" "); F=-1 R= -1
return 0;
}
item=q[front];
if(front==rear)
front=rear=−1;
else
front=front+1;
return item;
}

Prepared By : Vaishali Koria Data Structure and Algorithms 7

 Simple Queue Algorithms
int dequeue() q[0] q[1] q[2] q[3] q[4] q[5]
{
if (front==−1) 11 12 13 14 15 16
{
printf("\"Underflow" ");
F=0 R= 5
return 0;
}
item=q[front]; 1. dequeue()
if(front==rear) Item =11
front=rear=−1; F=1
else
front=front+1;
return item;
}

Prepared By : Vaishali Koria Data Structure and Algorithms 8

 Simple Queue Algorithms
int dequeue() q[0] q[1] q[2] q[3] q[4] q[5]
{
if (front==−1) 12 13 14 15 16
{
printf("\"Underflow" ");
F=1 R= 5
return 0;
}
item=q[front]; 2. dequeue()
if(front==rear) Item =12
front=rear=−1; F=2
else
front=front+1;
return item;
}

Prepared By : Vaishali Koria Data Structure and Algorithms 9

 Simple Queue Algorithms
int dequeue() q[0] q[1] q[2] q[3] q[4] q[5]
{
if (front==−1) 13 14 15 16
{
printf("\"Underflow" ");
F=2 R= 5
return 0;
}
item=q[front]; 3. dequeue()
if(front==rear) Item =13
front=rear=−1; F=3
else
front=front+1;
return item;
}

Prepared By : Vaishali Koria Data Structure and Algorithms 10

 Simple Queue Algorithms
int dequeue() q[0] q[1] q[2] q[3] q[4] q[5]
{
if (front==−1) 14 15 16
{
printf("\"Underflow" ");
F=3 R= 5
return 0;
}
item=q[front]; 4. dequeue()
if(front==rear) Item =14
front=rear=−1; F=4
else
front=front+1;
return item;
}

Prepared By : Vaishali Koria Data Structure and Algorithms 11

 Simple Queue Algorithms
int dequeue() q[0] q[1] q[2] q[3] q[4] q[5]
{
if (front==−1) 15 16
{
printf("\"Underflow" ");
F=4 R= 5
return 0;
}
item=q[front]; 5. dequeue()
if(front==rear) Item =15
front=rear=−1; F=5
else
front=front+1;
return item;
}

Prepared By : Vaishali Koria Data Structure and Algorithms 12

 Simple Queue Algorithms
int dequeue() q[0] q[1] q[2] q[3] q[4] q[5]
{
if (front==−1) 16
{
printf("\"Underflow" ");
F=5 R= 5
return 0;
}
item=q[front]; 6. dequeue()
if(front==rear) Item =16
front=rear=−1; F=5 and R =5 so
else
front=front+1; F=R=-1
return item;
}

Prepared By : Vaishali Koria Data Structure and Algorithms 13

Queue Implementation
Static Implementation : Using an array

Dynamic Implementation : Using an Linked List

Prepared By : Vaishali Koria Data Structure and Algorithms 15

 Simple Queue disadvantage
q[0] q[1] q[2] q[3] q[4] q[5]
Consider the full queue:
11 12 13 14 15 16

F=0
R= 5
q[0] q[1] q[2] q[3] q[4] q[5]
After 3 delete operations:
14 15 16

F=3
R= 5
Call Insert function for 17. It will result in overflow as R= n-1 (where n is the size of the
queue)
This is the disadvantage of simple queue as there are blank spaces in an array but we
cannot store the elements.

To solve this, we can use Circular queue.

Prepared By : Vaishali Koria Data Structure and Algorithms 16

Circular Queue Algorithms
CQINSERT(Q,F,R,X) R= 7 F=0 R= 0
Q[0]=1
1. [Check for Queue Overflow] Q[7]=8
If(R=size-1 and F=0) or F=R+1 R= 1
then write “Queue is overflow” R= 6
Q[1]=2
return Q[6]=7
2. [Set Rear]
F=R=-1
If(R=size-1 && F!=0)
Size= 8
R=0
Q[2]=3
Else Q[5]=6
R=R+1 R= 2
3. [Insert element] R= 5 Q[4]=5 Q[3]=4
Q[R] = X
4. [Set front]
If(F=-1) R= 3
F=0
R= 4
5. [Finish]
return

Prepared By : Vaishali Koria Data Structure and Algorithms 17

Circular Queue Algorithms
CQINSERT(Q,F,R,X) R= Size-1 F=0
R= 7
Q[0]=1
1. [Check for Queue Overflow] Q[7]=8
If(R=size-1 and F=0) or F=R+1
then write “Queue is overflow”
Q[6]=7 Q[1]=2
return
2. [Set Rear]
If(R=size-1 && F!=0)
R=0 Q[5]=6 Q[2]=3
Else
R=R+1
3. [Insert element]
Q[4]=5 Q[3]=4
Q[R] = X
4. [Set front]
If(F=-1)
F=0
5. [Finish]
return

Prepared By : Vaishali Koria Data Structure and Algorithms 18

Circular Queue Algorithms
CQINSERT(Q,F,R,X) R= Size-1 R= 0

1. [Check for Queue Overflow] Q[7]=8

If(R=size-1 and F=0) or F=R+1
then write “Queue is overflow”
Q[6]=7
return
2. [Set Rear]
If(R=size-1 && F!=0)
R=0 Q[5]=6
Else
R=R+1
3. [Insert element]
Q[4]=5 Q[3]=4
Q[R] = X
4. [Set front]
If(F=-1) F=3
F=0
5. [Finish]
return

Prepared By : Vaishali Koria Data Structure and Algorithms 19

Circular Queue Algorithms
CQINSERT(Q,F,R,X)
R= 0

1. [Check for Queue Overflow] Q[7]=8 Q[0]=9

If(R=size-1 and F=0) or F=R+1
then write “Queue is overflow”
Q[6]=7
return
2. [Set Rear]
If(R=size-1 && F!=0)
R=0 Q[5]=6
Else
R=R+1
3. [Insert element]
Q[4]=5 Q[3]=4
Q[R] = X
4. [Set front]
If(F=-1) F=3
F=0
5. [Finish]
return

Prepared By : Vaishali Koria Data Structure and Algorithms 20

Circular Queue Algorithms
CQINSERT(Q,F,R,X)

1. [Check for Queue Overflow] Q[7]=8 Q[0]=9

If(R=size-1 and F=0) or F=R+1 R= 1
then write “Queue is overflow”
Q[6]=7 Q[1]=10
return
2. [Set Rear]
If(R=size-1 && F!=0)
R=0 Q[5]=6
Else
R=R+1
3. [Insert element]
Q[4]=5 Q[3]=4
Q[R] = X
4. [Set front]
If(F=-1) F=3
F=0
5. [Finish]
return

Prepared By : Vaishali Koria Data Structure and Algorithms 21

Circular Queue Algorithms
CQINSERT(Q,F,R,X)

1. [Check for Queue Overflow] Q[7]=8 Q[0]=9

If(R=size-1 and F=0) or F=R+1
then write “Queue is overflow”
Q[6]=7 Q[1]=10
return
2. [Set Rear]
If(R=size-1 && F!=0)
R=0 Q[5]=6 Q[2]=11
Else
R=R+1
R= 2
3. [Insert element]
Q[4]=5 Q[3]=4
Q[R] = X
4. [Set front]
If(F=-1) F=3
F=0
5. [Finish]
return

Prepared By : Vaishali Koria Data Structure and Algorithms 22

Circular Queue Algorithms
CQINSERT(Q,F,R,X)

1. [Check for Queue Overflow] Q[7]=8 Q[0]=9

If(R=size-1 and F=0) or F=R+1
then write “Queue is overflow”
Q[6]=7
return Q[1]=10
2. [Set Rear]
If(R=size-1 && F!=0)
R=0 Q[5]=6 Q[2]=11
Else
R=R+1
3. [Insert element] R= 2
Q[4]=5 Q[3]=4
Q[R] = X
4. [Set front]
If(F=-1) F=3
F=0
5. [Finish]
return

Prepared By : Vaishali Koria Data Structure and Algorithms 23

Circular Queue Algorithms
CQDELETE(Q,F,R)

1. [Check for Queue Underflow]

If(F=-1)
then write “Queue is underflow”
return
2. [Delete Element]
Y = Q[F]
3. [Set Front]
If (F=R)
F =R = -1
else if (F = size-1)
F=0
Else
F = F+1
4. [Return element]
return Y F=-1 ( no insertion) R=-1

Prepared By : Vaishali Koria Data Structure and Algorithms 24

Circular Queue Algorithms
CQDELETE(Q,F,R) F=0

1. [Check for Queue Underflow] Q[0]=1

If(F=-1)
then write “Queue is
underflow” Q[1]=2
return
2. [Delete Element]
Y = Q[F] Q[5]=6 Q[2]=3
3. [Set Front]
R= 5
If (F=R)
F =R = -1
Q[4]=5 Q[3]=4
else if (F = size-1)
F=0
Else
F = F+1
4. [Return element] Y =1
return Y

Prepared By : Vaishali Koria Data Structure and Algorithms 25

Circular Queue Algorithms
CQDELETE(Q,F,R) F=0

1. [Check for Queue Underflow] Q[0]=1

If(F=-1)
then write “Queue is
underflow” Q[1]=2
return
2. [Delete Element]
Y = Q[F] Q[5]=6 Q[2]=3
3. [Set Front]
R= 5
If (F=R)
F =R = -1
Q[4]=5 Q[3]=4
else if (F = size-1)
F=0
Else
F = F+1
4. [Return element] Y =1
return Y

Prepared By : Vaishali Koria Data Structure and Algorithms 26

Circular Queue Algorithms
CQDELETE(Q,F,R)

1. [Check for Queue Underflow]

If(F=-1) F=1
then write “Queue is
underflow” Q[1]=2
return
2. [Delete Element]
Y = Q[F] Q[5]=6 Q[2]=3
3. [Set Front]
R= 5
If (F=R)
F =R = -1
Q[4]=5 Q[3]=4
else if (F = size-1)
F=0
Else
F = F+1
4. [Return element] return Y = 1
return Y

Prepared By : Vaishali Koria Data Structure and Algorithms 27

Circular Queue Algorithms
CQDELETE(Q,F,R)

1. [Check for Queue Underflow]

If(F=-1)
then write “Queue is
underflow”
return
2. [Delete Element]
Y = Q[F] Q[5]=6
3. [Set Front]
R= 5
If (F=R)
F =R = -1 F=5
else if (F = size-1)
F=0
Else
F = F+1
Y =6
4. [Return element]
return Y

Prepared By : Vaishali Koria Data Structure and Algorithms 28

Circular Queue Algorithms
CQDELETE(Q,F,R)

1. [Check for Queue Underflow]

If(F=-1)
then write “Queue is
underflow”
return
2. [Delete Element]
Y = Q[F]
3. [Set Front]
If (F=R)
F =R = -1
else if (F = size-1)
F=0
Else
F = F+1 R= -1 F=-1 Y =6
4. [Return element]
return Y

Prepared By : Vaishali Koria Data Structure and Algorithms 29

Circular Queue Algorithms
CQDELETE(Q,F,R) F=0

1. [Check for Queue Underflow] Q[0]=1

If(F=-1)
then write “Queue is
underflow” Q[1]=2
return
2. [Delete Element]
Y = Q[F] Q[2]=3
3. [Set Front]
If (F=R)
F =R = -1
Q[3]=4
else if (F = size-1)
F=0
Else
F = F+1
4. [Return element] R= 3
return Y

Prepared By : Vaishali Koria Data Structure and Algorithms 30

Priority Queue
• A priority queue is a list of elements where the elements are stored according to their priority
levels.

• The order in which the elements should get added or removed is decided based the priority of
the element.

• The element with a higher priority is processed before lower priority element.

• Same priority elements are processed in FIFO manner.

• Smallest number means highest priority and greater number means less priority.

Element Q[0] Q[1] Q[2] Q[3] Q[4]

Names
Values 11 12 13 14 15
Priority 1 2 3 4 5

Prepared By : Vaishali Koria Data Structure and Algorithms 31

Priority Queue
• Two methods to access the elements of priority Queue:

• Method 1:
Element Q[0] Q[1] Q[2] Q[3] Q[4]
Names Consider Insert operation for value 16
with priority 2.
Values 11 12 13 14 15
16
Priority 5 1 6 4 3
2
R
F

Element Q[0] Q[1] Q[2] Q[3] Q[4] Q[5]

Names
Values 11 12 13 14 15 16
Priority 5 1 6 4 3 2

F R

Prepared By : Vaishali Koria Data Structure and Algorithms 32

 Priority Queue
Method 1: Element Q[0] Q[1] Q[2] Q[3] Q[4] Q[5]
Names
Values 11 12 13 14 15 16
Priority 5 1 6 4 3 2

For deletion, preference will be given to highest priority element.

Element Q[0] Q[1] Q[2] Q[3] Q[4] Q[5]
Names
Find max priority element,
Values 11 12 13 14 15 16 which is Q[1]. Delete that.
Priority 5 1 6 4 3 2 Then shift the elements.

Element Q[0] Q[1] Q[2] Q[3] Q[4]

Names
Values 11 13 14 15 16

Priority 5 6 4 3 2

R
F
Prepared By : Vaishali Koria Data Structure and Algorithms 33
Priority Queue
• Two methods to access the elements of priority Queue:

• Method 2:
Element Q[0] Q[1] Q[2] Q[3] Q[4]
Names Consider Insert operation for value 16
with priority 2.
Values 11 12 13 14 15
16
Priority 5 1 6 4 3
2
R
F

Element Q[0] Q[1] Q[2] Q[3] Q[4] Q[5]

Names
Values 11 12 13 14 15 16
Priority 5 1 6 4 3 2

Prepared By : Vaishali Koria Data Structure and Algorithms 34

 Priority Queue
Method 2: Element Q[0] Q[1] Q[2] Q[3] Q[4] Q[5]
Names
Values 11 12 13 14 15 16
Priority 5 1 6 4 3 2

After Insertion, sort the elements based on priority.

Element Q[0] Q[1] Q[2] Q[3] Q[4] Q[5]
Names
Values 12 16 15 14 11 13

Priority 1 2 3 4 5 6

Then we can delete from front.

Element Q[0] Q[1] Q[2] Q[3] Q[4] Q[5]
Names
Values 16 15 14 11 13

Priority 2 3 4 5 6

F R

Prepared By : Vaishali Koria Data Structure and Algorithms 35

 Multi Queue implementation of Priority Queue
Priority 1 : Element Q[0] Q[1] Q[2] Q[3] Q[4]
Names
Values 11 12 13 14 15

Priority 2 : Element Q[0] Q[1] Q[2] Q[3] Q[4]

Names
Values 16 17 18 19 20

Priority 3 : Element Q[0] Q[1] Q[2] Q[3] Q[4]

Names
Values 21 22 23 24 25

F R

Prepared By : Vaishali Koria Data Structure and Algorithms 36

 Multi Queue implementation of Priority Queue
Priority 1 : Element Q[0] Q[1] Q[2] Q[3] Q[4]
Names
Values 11 12 13 14 15

Priority 2 : Element Q[0] Q[1] Q[2] Q[3] Q[4]

Names
Values 16 17 18 19 20

Priority 3 : Element Q[0] Q[1] Q[2] Q[3] Q[4]

Names
Values 21 22 23 24 25

F R
Insertion will be done in queue with matching priority queue of element. Suppose we
want to insert 26 with priority 2.
Element Q[0] Q[1] Q[2] Q[3] Q[4] Q[5]
Priority 2 : Names
Values 16 17 18 19 20 26

F R
Prepared By : Vaishali Koria Data Structure and Algorithms 37
 Multi Queue implementation of Priority Queue
Priority 1 : Element Q[0] Q[1] Q[2] Q[3] Q[4]
Names
Values 11 12 13 14 15

Priority 2 : Element Q[0] Q[1] Q[2] Q[3] Q[4] Q[5]

Names
Values 16 17 18 19 20 26

Priority 3 : Element Q[0] Q[1] Q[2] Q[3] Q[4]

Names
Values 21 22 23 24 25

F R

Deletion from priority Queue 2 is possible if priority Queue 1 is empty.

Prepared By : Vaishali Koria Data Structure and Algorithms 38

 Double Ended Queue
• It is a list of elements in which insertion and deletion operations are performed from both the
ends.
• We can insert elements from the rear end or from the front ends. Hence it is called double-
ended queue. It is commonly referred as a Deque.

• There are two types of Deque. These two types are due to the restrictions put to perform
either the insertions or deletions only at one end.

• Input Restricted Dequeue

• Output Restricted Dequeue

Q[0] Q[1] Q[2] Q[3] Q[4]

Insertion Deletion
Deletion Insertion

Prepared By : Vaishali Koria Data Structure and Algorithms 39

 Thank You!!!

Prepared By : Vaishali Koria Data Structure and Algorithms 46