Queues

http://install4install.com

Screen Shot 2014-04-10 at 3.48.41 PM

Fig 3 : A Queue

Screen Shot 2014-04-10 at 3.52.07 PM

Fig 2 : A Queue

Fig 1 : A Queue

Fig 1 : A Queue

Queues are the  data structure that stores data  in an ordered way.The  first element entered  is the  first one to be  removed.It is a  FIFO(First In First Out) data structure.The elements are added at one end called REAR end and removed from other end called as  FRONT end.

 

In Fig 2.FRONT =0 and REAR =4

Screen Shot 2014-04-10 at 3.52.07 PM

Fig 2 : A Queue(FIFO)

 

 

Array Representation of Queue

Queues can be represented by linear arrays.It has FRONT and REAR variables.FRONT points to the position from where deletion occurs and REAR points to the position where insertion occurs.

Insertion in Queue

Before insertion,check whether the queue has the space to accommodate the new element .If the queue is full is and still insertion in tried then “OVERFLOW” condition arises and element does not get into queue.It is checked by condition if (REAR = MAX -1) where MAX is the maximum number of elements that a queue can hold.If yes,then OVERFLOW condition arises.

Program 1

#include <stdio.h>

int main( )
{
 int queue[10];
 int max,num,i,item;
 int front,rear;
 //printf("Enter the size of queue");
 scanf("%d",&max);
 //printf("Enter the no of elements in queue");
 scanf("%d",&num);
 //printf("Enter the elements of queue");
 printf("Queue before insertion : "); //Fig3
 for(i=0;i<num;i++)
 	{
 		scanf("%d",&queue[i]);
 		printf(" %d\t",queue[i]);
 	}
 printf("\n");	
 front = 0;
 rear = num -1 ;
 printf("Front end : %d\n",front);
 printf("Rear end : %d\n",rear);
 if (rear == max-1)
 	{
 		printf("Overflow");
 	}
 else
 {
 	//printf("Enter the item you want to insert \n");
 	scanf("%d",&item);
 	rear = rear + 1;
 	front = 0;
 	queue[rear] = item;
 	printf("Queue after insertion :");//Fig 4
 	for(i=0;i<=rear;i++)
 	{
 		printf(" %d\t",queue[i]);
 	}
 printf("\n");
 printf("Front end : %d\n",front);
 printf("Rear end : %d\n",rear);
 }
 	return 0;
}

Run

Say we want to insert 15 in Queue of  Fig 3.

Screen Shot 2014-04-10 at 4.06.31 PM

Fig 3 : FRONT = 0
 REAR = 4

REAR would get incremented by 1(as insertions are done at REAR end) and 15 is stored at value of  5th index(Fig 4).

Screen Shot 2014-04-10 at 4.12.18 PM

Fig 4 : FRONT = 0
 REAR =5

Deletion in Queue

Before deleting an element check for “UNDERFLOW” condition.It occurs when we try to delete the element from an already empty queue.

If FRONT =-1 and REAR = -1 ,it means that there is no element in the queue and it is empty since index starts from 0.

If we want to delete element from the queue,then value of FRONT is incremented(Fig 6).Deletions are done at FRONT end only.

Program 2

#include <stdio.h>
int main( )
{
 int queue[10];
 int max,num,i;
 int front=0,rear;
 //printf("Enter the size of queue");
 scanf("%d",&max);
 //printf("Enter the no of elements in queue");
 scanf("%d",&num);
 //printf("Enter the elements of queue");
 printf("Queue before deletion : ");
 for(i=0;i<num;i++)
 	{
 		scanf("%d",&queue[i]);
 		printf(" %d\t",queue[i]);
 	}
 printf("\n");	
 front = 0;
 rear = num -1 ;
 printf("Front end : %d\n",front);
 printf("Rear end : %d\n",rear);
 if (front == -1 && rear == -1)
 {	
 	printf("Underflow");
 }	
 else
 {
 	front = front +1;
 }	
	printf("Queue after deletion :");
 	for(i=front;i<=rear;i++)
 	{
 		printf(" %d\t",queue[i]);
 	}
 printf("\n");
 printf("Front end : %d\n",front);
 printf("Rear end : %d\n",rear);
 return 0;
}

Run

 

Say we want to delete 25 from the queue(Fig 5)

Screen Shot 2014-04-10 at 4.06.31 PM

Fig 5 : FRONT = 0
  REAR = 4

The value of FRONT in incremented t0 1 and 25 is deleted from the queue(Fig 6)

Screen Shot 2014-04-10 at 4.20.23 PM

  REAR =5



Short URL: http://tinyit.cc/044009
Author: Cusp2207 on April 30, 2014
Category: Algorithms, Computer Science, Data Structures
Tags:

Leave a Reply

Last articles