Queue Operations

Queue Operations

• 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.

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.

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`mplementation of queue.

Ex. 3.3.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

{

int que[size];

int front,rear;

}Q;

/*

The Qfull Function

Input:none

Output:1 or 0 for q full or not

Called By:main

*/

Qfull()

{

if(Q.rear >=size-1)

return 1;

Note: 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

else

return 0;

}

/*

The insert Function

Input:item which is to be inserted in the Q

Output:rear value

Called By:main

Calls:none

*/

int insert(int item)

{

if(Q.front == -1)

Q.front++;

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

Note:This condition will occur initially when queue is empty when single element will be present then both front and rear points to the same

return Q.rear;

}

int Qempty()

{

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

return 1;

else

return 0;

}

/*

The delet Function

Input:none

Output:front value

Called By:main

Calls:none

*/

int delet()

{

int item;

item = Q.que[Q.front];

Q.front++;

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

return Q.front;

}

/*

The display Function

Input:none

Output:none

Called By:main

Calls:none

*/

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;

clrscr();

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');

}

/********************** 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. 3.3.2: Write a C program to implement queue functions using Arrays and Macros.

Solution :

#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.