Queue Data Structure
Out Line
• Introduction
• Implementation of Queue
• Checking of Overflow and Insertion
• Checking of Underflow and Deletion
Introduction
• Queue is an abstract data structure where the elements are
inserted in one end and is deleted from other end.
• Queue is also a linear data structure.
• Queue data structure somewhat similar to Stacks .
• Unlike stacks, a queue is open at both its ends.
• The queue data structure follows the FIFO (First In First
Out) principle.
• One end is always used to insert data and the other is used
to remove data.
• The size of the queue depends on the number and order of
insertion and deletion.
• It may be situation where memory is available but insertion
is not possible.
Implementation of Queue
• The ‘Maxsize’ variable is responsible to indicate the sixe of the
queue.
• Two variables are there to control the number of elements in
the queue:
– Front: This variable looks after the deletion of an element
from the queue
– Rear: This variable takes care about the element that will
be inserted in the queue.
• Four functions are there
– Overflow: Check whether the queue is full or not
– Underflow: Check whether the queue is empty or not
– Insert: Insert an element and increase the rear position
– Delete: Delete an element and increase the front position
Checking of Overflow and Insertion
Overflow:
if(rear==Maxsize-1)
printf(“Overflow”);
Insert:
if(front==-1){
front=0;
}
rear =rear+1;
qarr[rear] = item;
Example of Queue (Insertion)
front=-1, rear = -1
front=0, rear = 0 6
front=0, rear = 1 6 7
front=0, rear = 2 6 7 8
front=0, rear = 3 6 7 8 11
front=0, rear = 4 6 7 8 11 4
front=0, rear = 5 6 7 8 11 4 5
Checking of underflow and Deletion
Underflow:
if(front==-1||front>rear)
printf(“Underflow”);
Delete:
qarr[rear] = item;
rear =rear+1;
Example of Queue (Deletion)
front= 0, rear = 5 6 7 8 11 4 5
front= 1, rear = 5 7 8 11 4 5
front= 2, rear = 5 8 11 4 5
front= 3, rear = 5 11 4 5
front= 4, rear = 5 4 5
front= 5, rear = 5 5
front= -1, rear = -1
Circular Queue
• In normal queue some situations are occurred where the
positions of the queue is empty but we are not able to insert
the element there.
front= 3, rear = 5 11 4 5
• To overcome the difficulties of this scenario the proposal of
circular queue has come.
• In circular queue the if the rear is reached to (Maxsize-1)
position and front is not 0 then the rear will be set to 0 again.
• Insert 8 8 11 4 5
front= 3, rear = 0
Overflow and Insert Circular Queue
Overflow:
if(((front==0)&&(rear==Maxsize-1))|| (front==rear+1)) {
printf(“Overflow”); }
Insert: if(front==-1){
front = 0;
rear = 0;
}
else {
if(rear == Maxsize-1){ rear = 0; }
else { rear =rear+1; }
}
qarr[rear] = item;
Underflow and Delete Circular Queue
Overflow:
if( front == -1) {
printf(“Underflow”); }
Insert: item = qarr[front];
if(front == rear){
front = -1;
rear = -1;
}
else {
if(front == Maxsize-1){ front = 0; }
else { front = front + 1; }
}
De-Queue
• In normal queue and circular queue the operations for
insertion and deletion can be possible from one end only.
o overcome the difficulties of this scenario the proposal of
circular queue has come.
• In circular queue the if the rear is reached to (Maxsize-1)
position and front is not 0 then the rear will be set to 0 again.
front= 3, rear = 5 11 4 5
• Insert 8 8 11 4 5
front= 3, rear = 0
Overflow and Insert (right) De-Queue
Overflow:
if(((left == 0)&&(right == Maxsize-1))|| (left == right+1)) {
printf(“Overflow”); }
Insert: if( left == -1){
left = 0;
right = 0;
}
else {
if( right == Maxsize-1){ right = 0; }
else { right = right + 1; }
}
qarr[right] = item;
Overflow and Insert (left) De-Queue
Overflow:
if(((left == 0)&&(right == Maxsize-1))|| (left == right+1)) {
printf(“Overflow”); }
Insert: if( left == -1){
left = 0;
right = 0;
}
else {
if( left == 0){ left = Maxsize -1; }
else { left = left - 1; }
}
qarr[left] = item;
Underflow and Delete (right) De-Queue
Overflow:
if( left == -1) {
printf(“Underflow”); }
Insert: item = qarr[right];
if(left == right){
front = -1;
rear = -1;
}
else {
if(right == 0){ right = Maxsize-1; }
else { right = right - 1; }
}
Underflow and Delete (left) De-Queue
Overflow:
if( left == -1) {
printf(“Underflow”); }
Insert: item = qarr[left];
if(left == right){
left = -1;
right = -1;
}
else {
if(left == Maxsize-1){ left = 0; }
else { left = left + 1; }
}
Example of Queue (Input restricted)
left= 1, right = 3 9 8 11
left= 1, right = 4 9 8 11 4
left= 1, right = 5 9 8 11 4 5
left= 2, right = 5 8 11 4 5
left= 2, rear = 4 8 11 4
left= 3, right = 4 11 4
front= -1, rear = -1
Out Line
• Direct applications:-
• Waiting lists
• Access to shared resources (e.g., printer)
• Multiprogramming
• Indirect applications:-
• Auxiliary data structure for algorithms
• Component of other data structures
