Data Structures & Algorithms
101009/IT200C (Module 2)
S2 CU
Mr. Tinku Soman Jacob
Asst. Prof IT
RSET
1
Index
• Queue
• Circular Queue
101009/IT200C _S2 CU_Module-2 Mr. Tinku Soman Jacob, DIT, RSET(Autonomous) 2
Queue (Linear Queue)
• A queue is an ordered list in which insertion (also called addition,
enqueue) and deletion (also called remove, dequeue) take place at
different ends.
• The end at which new elements are added is called the rear and the
end from which old elements are deleted is called the front.
• Since the first element inserted into a queue is the first element
removed, queue are also known as First-in-First-Out (FIFO) list.
• It’s a linear DS.
• Can be implemented using 1-D array.
• Queue is empty when front and rear are -1.
101009/IT200C _S2 CU_Module-2 Mr. Tinku Soman Jacob, DIT, RSET(Autonomous) 3
Stack Vs Queue
101009/IT200C _S2 CU_Module-2 Mr. Tinku Soman Jacob, DIT, RSET(Autonomous) 4
Queue-Enqueue
101009/IT200C _S2 CU_Module-2 Mr. Tinku Soman Jacob, DIT, RSET(Autonomous) 5
Queue-Enqueue
//create an empty queue q[] with maxi size n.
//front = rear = -1
enqueue(int item) //item – element to insert
{
if(rear = n-1)
print “Overflow error”
else //other than initial enqueue if(rear=-1)//initial enqueue
rear++ front=rear=0
q[rear] = item q[rear]=item
101009/IT200C _S2 CU_Module-2 Mr. Tinku Soman Jacob, DIT, RSET(Autonomous) 6
Queue-Dequeue
Status,
dequeue
operation
After
deletion
101009/IT200C _S2 CU_Module-2 Mr. Tinku Soman Jacob, DIT, RSET(Autonomous) 7
Queue-Dequeue
dequeue()
{
if(front > rear or front=rear=-1)
print “Underflow error”
else // general case if (rear=front)//only one data
data = q[front] data=q[front]
front++ front=rear=-1
print “deleted item is”, data
}
101009/IT200C _S2 CU_Module-2 Mr. Tinku Soman Jacob, DIT, RSET(Autonomous) 8
Queue-Applications
• Printer buffer.
• OS process scheduling
• CPU scheduling
• Disk Scheduling
• IO Buffers, pipes, file IO, etc.
101009/IT200C _S2 CU_Module-2 Mr. Tinku Soman Jacob, DIT, RSET(Autonomous) 9
Linear Queue - Drawback
• In a simple queue, we cannot insert elements into the queue, when we
reach to the end of queue, in-spite of the free space made available in
the memory by the element deleted from the queue.
• Another drawback is that the insertion of elements are restricted to the
rear end and deletion of the element to the front end only.
101009/IT200C _S2 CU_Module-2 Mr. Tinku Soman Jacob, DIT, RSET(Autonomous) 10
Queue - Types
1. Simple queue
2. Circular queue – it follows the same rule of simple queue for insertion and deletion of
elements except that after the end of queue is reached, insertion continues from the
initial index position, if vacant.
3. Priority queue – insertion and deletion performed according to the priority assigned.
4. Deque (Double ended queue) - insertion and deletion performed from both ends of
the queue.
101009/IT200C _S2 CU_Module-2 Mr. Tinku Soman Jacob, DIT, RSET(Autonomous) 11
Circular Queue
• It follows the same rule of simple queue for insertion and deletion of
elements except that after the end of queue it reaches, the start position
of queue.
101009/IT200C _S2 CU_Module-2 Mr. Tinku Soman Jacob, DIT, RSET(Autonomous) 12
Circular Queue - Enqueue
front=rear=-1
enqueue(int item)
{ // n size of queue
if(front=(rear+1)%n)
print ”Overflow error”
else if(front=-1)
{
front=rear=0
cq[rear]=item
}
else
{
rear=(rear+1)%n
cq[rear]=item
} 101009/IT200C _S2 CU_Module-2 Mr. Tinku Soman Jacob, DIT, RSET(Autonomous) 13
Circular Queue - Dequeue
dequeue()
{
if(front=-1)
print ”Underflow error”
else if(front=rear)
{
var=cq[front]
print “var deleted”
front=rear=-1
}
else
{
var=cq[front]
print “var deleted”
front=(front+1)%n
} 14
}
Circular Queue
101009/IT200C _S2 CU_Module-2 Mr. Tinku Soman Jacob, DIT, RSET(Autonomous) 15
Circular Queue – Display/Traversal
traversal()
{
if(front=-1)
print ”Queue Empty”
else if(rear<front)
{
print”Elements are:”
for(i=front;i<n;i++)
print cq[i]
for(i=0;i<=rear;i++)
print cq[i]
}
else
{
print”Elements are:”
for(i=front;i<=rear;i++)
print cq[i]
} 16