Unit 5: Queue
Unit 5.1 Concepts of Queue (FIFO)
A Queue is a linear structure which follows a particular order in which the operations are performed. The order
is First In First Out (FIFO). A good example of a queue is any queue of consumers for a resource where the
consumer that came first is served first. 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. The difference between stacks and queues is in removing. In a stack we remove the item the
most recently added; in a queue, we remove the item the least recently added. Since insertion and deletion in
queue is performed from two different ends, elements are removed in the same order in which they were
inserted. Time sharing operating system is an example of queue.
Unit 5.1.1 Concepts of Queues and its basic operations
Queue can be implemented in two ways.
1. Static Queue: Queue that is implemented using fixed length array is called static queue.
2. Dynamic Queue: Queue implemented using linked list is called dynamic queue.
Types of queues:
1. Simple Queue (Q)
2. Circular Queue (CQ)
3. Double Ended Queue (DQ)
4. Priority Queue
Operations performed on the queue:
There are two operation that can be performed on queue:
1. Insertion
2. Deletion
Simple Queue:
Simple queue is a linear queue which has rea and front end to insert and delete elements to and from the
queue respectively.
Insertion Operation in Simple queue:
When we insert an element in simple queue, first we have to check whether queue is full or not. This is
called checking for the Overflow. If the queue is not full insertion will be performed at the Rear end. If n is
the size of the queue and r is the rear end than overflow condition will be r>=n-1.
Algorithm to insert an element in Simple Queue:
insert()
here,
q = an array representing Simple Queue
f = front end variable (for deletion)
Unit 5: Queue
r = rear end variable (for insertion)
n= maximum number of elements that can be inserted in a queue.
data = it is the value to be inserted in the queue
Initially f and r both will be set to -1.
Algorithm
Step 1: Check for the Overflow Condition
if r>=n-1 then
print “Overflow”
end if
return
Step 2: Increment the rear pointer
r=r+1
Step 3: Insert the element
q[r] = data
Step 4: Set the front pointer
if f == -1 then
f=0
end if
Step 5: Exit
Deletion Operation in Simple queue:
Removing an element from the queue is called deletion. When we are deleting an element from simple
queue, we have to first check whether the queue is empty or not. This is called checking for underflow
condition. If queue is not empty than deletion operation will be performed at the front end. When the value
of f = -1 then the queue is empty.
Algorithm to delete an element from Simple Queue:
del()
here,
q = an array representing Simple Queue
f = front end variable (for deletion)
r = rear end variable (for insertion)
n= maximum number of elements that can be inserted in a queue.
data = it is the value to be inserted in the queue
Initially f and r both will be set to -1.
Algorithm
Step 1: Check for the Underflow Condition
if f<=-1 then
print “Underflow”
Unit 5: Queue
end if
return
Step 2: Delete the value
Data = q[f]
Step 3: Check for the deletion of the last value
if f == r then
f = r = -1
else
f=f+1
Step 4: Return data
Step 5: Exit
Note: When r = f, the queue is empty, so we have to set r and f to -1.
Write a program to implement simple queue.
#include<iostream.h>
#include<conio.h>
#define max 5
int q[max];
int f = r = -1;
void insert()
{
int value;
if ( r > = max – 1)
{
cout<<”Overflow”;
return();
}
cout<<”enter the value to be inserted”
cin>>value;
r++;
q[r] = value;
if ( f == -1)
f = 0;
return();
}
void del()
{
Unit 5: Queue
int value;
if ( f == -1)
{
cout<<”Underflow”;
return 0;
}
cout<< q[f];
if (f == r)
f = r = -1;
else
f++;
return;
}
void display()
{
int i;
for (i = f ; i < = r ; i++)
cout<<q[i];
}
int main()
{
int ch;
do
{
cout<<”1. Insertion”;
cout<<”2. Deletion”;
cout<<”3. Display”;
cout<<”0. Exit”;
cout<<”Enter your choice”;
cin>>ch;
switch(ch)
{
case 1:
insert();
break;
case 2:
Unit 5: Queue
del();
break;
case 3:
display();
break;
case 0: exit(0);
default: cout<<”enter valid choice”
}
}while(ch!=0);
getch();
return 0;
}
#include<iostream.h>
#include<conio.h>
#define max 5
class queue
{
int q[max], r, f;
public:
queue()
{
r = f = -1
}
void insert()
{
int value;
if ( r > = max – 1)
{
cout<<”Overflow”;
return();
}
cout<<”enter the value to be inserted”
cin>>value;
r++;
q[r] = value;
if ( f == -1)
Unit 5: Queue
f = 0;
return();
}
void del()
{
int value;
if ( f == -1)
{
cout<<”Underflow”;
return 0;
}
cout<< q[f];
if (f == r)
f = r = -1;
else
f++;
return;
}
void display()
{
int i;
for (i = f ; i < = r ; i++)
cout<<q[i];
}
}
int main()
{
int ch;
queue q1;
do
{
cout<<”1. Insertion”;
cout<<”2. Deletion”;
cout<<”3. Display”;
cout<<”0. Exit”;
cout<<”Enter your choice”;
Unit 5: Queue
cin>>ch;
switch(ch)
{
case 1:
q1.insert();
break;
case 2:
q1.del();
break;
case 3:
q1.display();
break;
case 0: exit(0);
default: cout<<”enter valid choice”
}
}while(ch!=0);
getch();
return 0;
}
Limitations of simple queue
There is one limitation in the array implementation of Queue. If the rear reaches to the end position of the
Queue then there might be possibility that some vacant spaces are left in the beginning which cannot be
utilized. Simple Queue cannot utilize memory efficiently. Consider the following queue.
Here, after deleting two elements from the queue looks like this. If we try to insert an element in the queue,
it will give us “Overflow”, though there is space available at the beginning of the queue. This happened
because of the overflow condition r > = n -1. This limitation can be overcome in the circular queue.
Circular Queue:
To overcome the limitation of Simple Queue Circular Queue is used. 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. In other words, we can say that a queue is
a circular queue where the last element comes just before the first element.
Unit 5: Queue
Insertion Operation in Circular queue:
In Circular Queue when rear pointer reaches the end of the queue, but there is some space available in the
front of the queue, it will allow us to insert. So for overflow condition we have to check two condition. First
r>=n-1 and along with that, we also have check there are no elements deleted from front, i.e f = 0.
Algorithm to insert an element in Circular Queue:
insert()
here,
cq = an array representing Circular Queue
f = front end variable (for deletion)
r = rear end variable (for insertion)
n= maximum number of elements that can be inserted in a queue.
data = it is the value to be inserted in the queue
Initially f and r both will be set to -1.
Algorithm
Step 1: Check for the Overflow Condition
If ( (r >= n-1) and (f = 0) ) OR (f == r +1 )then
print “Overflow”
end if
return
Step 2: Update the rear pointer
If r = n – 1 then
r=0
else
r=r+1
End if
Unit 5: Queue
Step 3: Insert the element
cq[r] = data
Step 4: Set the front pointer
if f == -1 then
f=0
end if
Step 5: Exit
Deletion Operation in Circular queue:
In Circular Queue when front pointer reaches the end of the queue, but there are some elements in the front
of the queue, deletion can still be performed.
Algorithm to delete an element in Circular Queue:
del()
here,
cq = an array representing Circular Queue
f = front end variable (for deletion)
r = rear end variable (for insertion)
n= maximum number of elements that can be inserted in a queue.
data = it is the value to be inserted in the queue
Initially f and r both will be set to -1.
Algorithm
Step 1: Check for the Underflow Condition
if f = = - 1 then
print “Overflow”
end if
return
Step 2: Delete an element
data = cq[f]
Step 3: Check for the deletion of the last element
If (f = = r) then
f = r = -1
else if (f == n – 1) then
f = 0;
else
f=f+1
end if
Step 4: Return the deleted element
Unit 5: Queue
Return data
Step 5: Exit
Write a program to implement Circular queue.
#include<iostream.h>
#include<conio.h>
#define max 5
int cq[max];
int f = r = -1;
void insert()
{
int value;
if (( r > = max – 1) && (f == 0)) || (f == r + 1)
{
cout<<”Overflow”;
return();
}
cout<<”enter the value to be inserted”
cin>>value;
if ( r == max – 1)
r = 0;
else
r++;
cq[r] = value;
if ( f == -1)
f = 0;
return();
}
void del()
{
int value;
if ( f == -1)
{
cout<<”Underflow”;
return 0;
}
cout<< cq[f];
Unit 5: Queue
if (f == r)
f = r = -1;
else if (f == max – 1)
f = 0;
else
f++;
return;
}
void display()
{
int i;
if (r<f)
{
for (i = f ; i < = max - 1 ; i++)
cout<<cq[i];
for (i = 0; i < = r ; i++)
cout<<cq[i];
}
else
{
for (i = f ; i < = r ; i++)
cout<<cq[i];
}
}
int main()
{
int ch;
do
{
cout<<”1. Insertion”;
cout<<”2. Deletion”;
cout<<”3. Display”;
cout<<”0. Exit”;
cout<<”Enter your choice”;
cin>>ch;
Unit 5: Queue
switch(ch)
Unit 5: Queue
{
case 1:
insert();
break;
case 2:
del();
break;
case 3:
display();
break;
case 0: exit(0);
default: cout<<”enter valid choice”
}
}while(ch!=0);
getch();
return 0;
}
Double Ended Queue (dequeue):
The dequeue stands for Double Ended Queue. In the queue, the insertion takes place from one end while
the deletion takes place from another end. The end at which the insertion occurs is known as the rear
end whereas the end at which the deletion occurs is known as front end. Deque is a linear data structure in
which the insertion and deletion operations are performed from both ends. We can say that deque is a
generalized version of the queue.
There are two types of Queues, Input-restricted queue, and output-restricted queue.
1. Input-restricted queue: The input-restricted queue means that some restrictions are applied to the
insertion. In input-restricted queue, the insertion is applied to one end while the deletion is applied
from both the ends.
Unit 5: Queue
2. Output-restricted queue: The output-restricted queue means that some restrictions are applied to
the deletion operation. In an output-restricted queue, the deletion can be applied only from one end,
whereas the insertion is possible from both ends.
Operations performed on the dequeue:
The following are the operations applied on deque:
o Insert right
o Delete right
o insert left
o delete left
Algorithm to insert an element at right in deueue:
here,
deq = an array representing dequeue
f = front end variable (for deletion)
r = rear end variable (for insertion)
n= maximum number of elements that can be inserted in a queue.
data = it is the value to be inserted in the queue
Initially f and r both will be set to -1.
Algorithm
Step 1: Check for the Overflow Condition
if r>=n-1 then
print “Overflow”
end if
return
Step 2: Increment the rear pointer
r=r+1
Step 3: Insert the element
deq[r] = data
Step 4: Set the front pointer
if f == -1 then
f=0
end if
Step 5: Exit
Unit 5: Queue
Algorithm to insert an element at left in deueue:
here,
deq = an array representing dequeue
f = front end variable (for deletion)
r = rear end variable (for insertion)
n= maximum number of elements that can be inserted in a queue.
data = it is the value to be inserted in the queue
Initially f and r both will be set to -1.
Algorithm
Step 1: Check for the Overflow Condition
if f == 0 then
print “Overflow”
end if
return
Step 2: Set the front variable
If f == -1 then
r=f=n–1
else
f=f–1
end if
Step 3: Insert the element
deq[f] = data
Step 4: Exit
Algorithm to delete an element from left in deueue:
here,
deq = an array representing dequeue
f = front end variable (for deletion)
r = rear end variable (for insertion)
n= maximum number of elements that can be inserted in a queue.
data = it is the value to be inserted in the queue
Initially f and r both will be set to -1.
Algorithm
Step 1: Check for the Underflow Condition
if f<=-1 then
print “Underflow”
end if
return
Unit 5: Queue
Step 2: Delete the value
Unit 5: Queue
Data = q[f]
Step 3: Check for the deletion of the last value
if f == r then
f = r = -1
else
f=f+1
Step 4: Return data
Step 5: Exit
Algorithm to delete an element from right in deueue:
here,
deq = an array representing dequeue
f = front end variable (for deletion)
r = rear end variable (for insertion)
n= maximum number of elements that can be inserted in a queue.
data = it is the value to be inserted in the queue
Initially f and r both will be set to -1.
Algorithm
Step 1: Check for the Underflow Condition
if r == -1 then
print “Underflow”
end if
return
Step 2: Delete the value
Data = q[r]
Step 3: Check for the deletion of the last value
if f == r then
f = r = -1
else
r=r-1
Step 4: Return data
Step 5: Exit
Note: For input restricted queue use algorithm insert right, delete right, delete left.
For output restricted queue use algorithm delete left, insert right, insert left.
Unit 5: Queue
Write a program to implement DEQueue.
#include<iostream.h>
#include<conio.h>
#define max 5
int deq[max];
int f = r = -1;
void insert_right()
{
int value;
if (( r > = max – 1)
{
cout<<”Overflow”;
return();
}
cout<<”enter the value to be inserted”
cin>>value;
r++;
deq[r] = value;
if ( f == -1)
f = 0;
return();
}
void del_left()
{
if ( f == -1)
{
cout<<”Underflow”;
return ;
}
cout<< deq[f];
if (f == r)
f = r = -1;
else
f++;
return;
}
Unit 5: Queue
void insert_left()
{
int value;
if (f == 0)
{
cout<< “Overflow”;
return;
}
If f == -1
r = f = n – 1;
else
f = f – 1;
cout<<”enter the value to be inserted”;
cin>>value;
deq[f] = data;
}
del_right()
{
if (r == -1)
{
print “Underflow”;
return;
}
cout<<deq[r];
if f == r then
f = r = -1;
else
r = r – 1;
}
void display()
{
int i;
for (i = 0 ; i < = max - 1 ; i++)
cout<<q[i];
}
int main()
Unit 5: Queue
{
Unit 5: Queue
int ch;
do
{
cout<<”1. Insert Right”;
cout<<”2. Delete Right”;
cout<<”3. Insert Left”;
cout<<”4. Delete Left”;
cout<<”5. Display”;
cout<<”0. Exit”;
cout<<”Enter your choice”;
cin>>ch;
switch(ch)
{
case 1:
insert_right();
break;
case 2:
delete_right();
break;
case 3:
insert_left();
break;
case 4:
del_left();
break;
case 5:
display();
break;
case 0: exit(0);
default: cout<<”enter valid choice”
}
}while(ch!=0);
getch();
return 0;
}
