Queues
Prepared By :
Atul R. Thakare
KV Silvassa
[email protected]
Using a Queue
Introduction
Array implementation of Queue
Linked List implementation of Queue
Circular Queue
Dequeue
Introduction
Queue is a data structure in which deletion is done from the
front and insertion is done at rear end or it is an ordered list
where insertion and deletion is done at two different ends
Data 1 Data 2 Data 3 Data 4 Data 5
Front Rear
A queue is like a line of people waiting for a
bank teller in which first person on the line
is serviced first and the person can enter
only at end. $ $
Front
Rear
:- Queue is called as FIFO (First in First Out )
Data Structure
Operations On Queue
We can do two major operations on Queue
Insertion
Deletion
Implementation Of Queue
Queue can be implemented in two ways
Using Arrays
Using Link List
Array implementation of Queue
Algorithm to insert a queue
Steps
1. If rear = MAX Print “ Queue Full” go to step 4
2. rear = rear +1
3. Queue [rear] = val
4. end
Array implementation of Queue
Function for insertion of element
void QINSERT (int queue[],int val, int &rear)
{ if(rear == Max -1)
{ cout<<“Queue Full”; }
else
{ rear = rear + 1;
queue[rear] = val
}
}
Array implementation of Queue
Algorithm to delete a element in a queue
Steps
1. If front = max
Print “Queue Empty” go to step 4
2. Val = queue[front]
3. front = front + 1
4. end
Array implementation of Queue
Function for deletion of element
int QDEL(int queue[],int &front)
{
int val;
if(front == max)
{ couot<<“Queue Empty”;
}
else
{ val = queue[front];
front = front + 1;
}
return(Val);
}
Linked implementation of Queue
Self referential structure : Structure Which
refers itself
Struct node
{
int info;
node * next;
}
Linked implementation of Queue
Algorithm to insert a queue
Steps
1. temp = new node
2. If (temp == NULL) Print(“Overflow”) go to step
3. Read (val)
4. Temp->info= val
5. Temp->next = NULL
6. If(rear = NULL) rear= temp front = rear
else
rear->next =temp rear = temp
7. End
Linked implementation of Queue
Function for insertion of element
Void QINSERT(int val)
{ node *temp;
temp= new node;
if(temp==NULL)
{ cout<<“Overflow”;
exit(0)
}
temp->next = NULL;
temp->info = val
If (rear == NULL)
{ front = temp;
rear = temp;
}
else { rear->next =temp
rear=temp
} }
Linked implementation of Queue
Algorithm to delete a element in a queue
Steps
1. If front = NULL
Print “Queue Empty” go to step 5
2. Temp=front
3. If front = rear front = rear = NULL
else front = front-> next
4. Delete temp
5. end
Linked implementation of Queue
Function for deletion of element
void Qdelete()
{
node *temp;
if ( front == NULL)
{ cout<<“Queue Empty/Underflow”;
}
else
{ Temp=front;
front=front->next;
delete temp;
}
}
Variations in Queues
Two Variations of queues are Circular queues
and deques (double ended queues)
Circular queues are the queues implemented
in the circular form rather than a straight line.
circular queue overcomes the problem of
unutilised space in array implementation of
queue.
deque
Double ended queue are the refined queues in
which elements can be added or removed at
either end but not in the middle.
There are two variations of dqueue –
An input restricted dequeu and
Output restricted dequeu
Dequeu
An input restricted dequeu is a dqueue which
allows insertion at one one end but allows
deletion at both the ends of the list.
An output restricted dequeu is a dqueue which
allows deletion only at one one end but allows
insertion at both the ends of the list.
