Queue Implementation

 Queue Implementation

AU: May-15, Marks 16

• Queue is nothing but the collection of items. Both the ends of the queue are having their own functionality.

• The Queue is also called as FIFO i.e. a First In First Out data structure.

• All the elements in the queue are stored sequentially.

• Various operations on the queue are -

1.Queue overflow.

2.Insertion of the element into the queue.

3.Queue underflow.

4. Deletion of the element from the queue.

5.Display of the queue.

Let us see each operation one by one

• 'C' representation of queue.

struct queue

{

int que [size];

int front;

int rear;

}Q;

1. Insertion of element into the queue

The insertion of any element in the queue will always take place from the rear end.

We have inserted first 10, then 20, then 30, then 40, then 50, in the queue.

Before performing insert operation you must check whether the queue is full or not. If the rear pointer is going beyond the maximum size of the queue then the queue overflow Occurs.

2. Deletion of element from the queue

The deletion of any element in the queue takes place by the front end always.

The number 10 gets deleted logically

That means queue is from front to rear only. i.e. from 20 to 60

Before performing any delete operation one must check whether the queue is empty or not. If the queue is empty, you cannot perform the deletion. The result of illegal attempt to delete an element from the empty queue is called the queue underflow condition.

Let us see the 'C' implementation of the queue.

Ex. 4.10.1 Implementation of queue using arrays.

/******************************************************************

 Program for implementing the Queue using arrays

***************************************************************/

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

#define size 5

struct queue Queue data structure declared with array que[], front and rear

{

int que[size];

int front,rear;

}Q;

/*

The Qfull Function

*/

 Qfull()

{

if(Q.rear >=size-1) If Queue exceeds the maximum size of the array then it returns 1 - means queue full is true otherwise 0 means queue full is false

return 1;

else

return 0;

}

/*

The insert Function

*/

int insert(int item)

{

if(Q.front == -1)

Q.front++;

Q.que[++Q.rear] = item; Always increment the rear pointer and place the element in the queue

return Q.rear;

}

int Qempty()

{

if((Q.front == -1) || (Q.front > Q.rear))

The display Function

*/

void display()

{

int i;

for(i=Q.front;i<=Q.rear;i++). Printing the queue from front to rear

 printf("%d", Q.que[i]);

}

void main(void)

{

int choice,item;

char ans;

clrscr();

Q.front =-1;

do

{

printf("\n Main Menu");

printf("\n1.Insert\n2.Delete\n3.Display");

printf("\n Enter Your Choice");

scanf("%d", &choice);

switch(choice)

{

case 1:if(Qfull()) //checking for Queue overflow

printf("\n Can not insert the element");

else

{

printf("\n Enter The number to be inserted");

scanf("%d",&item);

insert(item);

}

break;

case 2:if(Qempty())

printf("\n Queue Underflow!!");

else

delet();

break;

case 3:if(Qempty())

printf("\nQueue Is Empty!");

else

display();

break;

default:printf("\n Wrong choice!");

break;

 }

printf("\n Do You Want to continue?");

ans = getche();

} while(ans == 'Y' || ans =='y');

}

/**************************End Of Program ***************/

Output

Main Menu

1. Insert

2. Delete

3. Display

Enter Your Choice 1

Enter The number to be inserted 10

Do You Want to continue?y

Main Menu

1. Insert

2. Delete

3. Display

Enter Your Choice 1

Enter The number to be inserted 20

Do You Want to continue?y

Main Menu

1. Insert

2. Delete

3. Display

Enter Your Choice 3

10 20

Do You Want to continue?y

Main Menu

1. Insert

2. Delete

3. Display

Enter Your Choice 2

The deleted item is 10

Do You Want to continue?y

Main Menu

1. Insert

2. Delete

3. Display

Enter Your Choice 3

20

Do You Want to continue?n

Key Point Always check queue full before insert operation and queue empty before delete operation.

 

Ex. 4.10.2: Write a C program to implement queue functions using arrays and macros. AU: May-15, Marks 16

Sol. :

#include<stdio.h>

#include<stdlib.h>

#include<conio.h>

/* Macro definitions */

#define size 5

#define Isfull Q.rear >=size-1

#define Isempty (Q.front == -1) || (Q.front > Q.rear)

struct queue

{

int que[size]; //Queue using Arrays

int front,rear;

}Q;

Qfull()

{

if(Isfull)

return 1;

else

return 0;

}

int insert(int item)

{

if(Q.front ==-1)

Q.front++;

Q.que[++Q.rear] = item;

return Q.rear;

}

int Qempty()

{

if(Isempty)

return 1;

else

return 0;

}

int delet()

{

int item;

item = Q.que[Q.front];

Q.front++;

printf("\n The deleted item is %d",item);

return Q.front;

}

void display()

{

int i;

for(i=Q.front;i<=Q.rear;i++)

printf("%d", Q.que[i]);

}

void main(void)

{

int choice,item;

char ans;

Q.front = -1;

Q.rear =-1;

do

{

printf("\n Main Menu");

printf("\n1.Insert\n2.Delete\n3.Display");

printf("\n Enter Your Choice");

scanf("%d", &choice);

switch(choice)

{

case 1:if(Qfull()) //checking for Queue overflow

printf("\n Can not insert the element");

else

{

printf("\n Enter The number to be inserted");

scanf("%d", &item);

insert(item);

}

break;

case 2:if(Qempty())

printf("\n Queue Underflow!!");

else

delet();

break;

case 3:if(Qempty())

printf("\nQueue Is Empty!");

else

display();

break;

default:printf("\n Wrong choice!");

break;

}

printf("\n Do You Want to continue?");

ans = getche();

} while(ans =='Y' || ans =='y');

}

Review Question

1. Develop an algorithm to implement Queue ADT. Give relevant examples and diagrammatic representations.AU: May-16, Marks 12