When we implement a queue using an array, the size of the array must be known in advance. If the queue is allocated less space, then frequent overflow conditions will be encountered. To deal with this problem, the code will have to be modified to reallocate more space for the array.
In case we allocate a large amount of space for the queue, it will result in sheer wastage of the memory. Thus, there lies a tradeoff between the frequency of overflows and the space allocated.
So a better solution to deal with this problem is to have multiple queues or to have more than one queue in the same array of sufficient size. Figure 8.31 illustrates this concept
In the figure, an array Queue[n] is used to represent two queues, Queue A and Queue B. The value of n is such that the combined size of both the queues will never exceed n. While operating on these queues, it is important to note one thing—queue A will grow from left to right, whereas queue B will grow from right to left at the same time.
Extending the concept to multiple queues, a queue can also be used to represent n number of queues in the same array. That is, if we have a QUEUE[n], then each queue I will be allocated an equal amount of space bounded by indices b[i] and e[i]. This is shown in Fig. 8.32.
C program to implement multiple queues
#include <stdio.h>
#include <conio.h>
#define MAX 10
int QUEUE[MAX], rearA=–1,frontA=–1, rearB=MAX, frontB = MAX;
void insertA(int val)
{
if(rearA==rearB –1)
printf("\n OVERFLOW");
else
{
if(rearA ==–1 && frontA == –1)
{ rearA = frontA = 0;
QUEUE[rearA] = val;
}
else
QUEUE[++rearA] = val;
}
}
int deleteA()
{
int val;
if(frontA==–1)
{
printf("\n UNDERFLOW");
return –1;
}
else
{
val = QUEUE[frontA];
frontA++;
if (frontA>rearA)
frontA=rearA=–1
return val;
}
}
void display_queueA()
{
int i;
if(frontA==–1)
printf("\n QUEUE A IS EMPTY");
else
{
for(i=frontA;i<=rearA;i++)
printf("\t %d",QUEUE[i]);
}
}
void insertB(int val)
{
if(rearA==rearB–1)
printf("\n OVERFLOW");
else
{
if(rearB == MAX && frontB == MAX)
{ rearB = frontB = MAX–1;
QUEUE[rearB] = val;
}
else
QUEUE[––rearB] = val;
}
}
int deleteB()
{
int val;
if(frontB==MAX)
{
printf("\n UNDERFLOW");
return –1;
}
else
{
val = QUEUE[frontB];
frontB––;
if (frontB<rearB)
frontB=rearB=MAX;
return val;
}
}
void display_queueB()
{
int i;
if(frontB==MAX)
printf("\n QUEUE B IS EMPTY");
else
{
for(i=frontB;i>=rearB;i––)
printf("\t %d",QUEUE[i]);
}
}
int main()
{
int option, val;
clrscr();
do
{
printf("\n *******MENU******");
printf("\n 1. INSERT IN QUEUE A");
printf("\n 2. INSERT IN QUEUE B");
printf("\n 3. DELETE FROM QUEUE A");
printf("\n 4. DELETE FROM QUEUE B");
printf("\n 5. DISPLAY QUEUE A");
printf("\n 6. DISPLAY QUEUE B");
printf("\n 7. EXIT");
printf("\n Enter your option : ");
scanf("%d",&option);
switch(option)
{
case 1: printf("\n Enter the value to be inserted in Queue A : ");
scanf("%d",&val);
insertA(val);
break;
case 2: printf("\n Enter the value to be inserted in Queue B : ");
scanf("%d",&val);
insertB(val);
break;
case 3: val=deleteA();
if(val!=–1)
printf("\n The value deleted from Queue A = %d",val);
break;
case 4 : val=deleteB();
if(val!=–1)
printf("\n The value deleted from Queue B = %d",val);
break;
case 5: printf("\n The contents of Queue A are : \n");
display_queueA();
break;
case 6: printf("\n The contents of Queue B are : \n");
display_queueB();
break;
}
}while(option!=7);
getch();
}
Output
*******MENU******"
1. INSERT IN QUEUE A
2. INSERT IN QUEUE B
3. DELETE FROM QUEUE A
4. DELETE FROM QUEUE B
5. DISPLAY QUEUE A
6. DISPLAY QUEUE B
7. EXIT
Enter your option : 2
Enter the value to be inserted in Queue B : 10
Enter the value to be inserted in Queue B : 5
Enter your option: 6
The contents of Queue B are : 10 5
Enter your option : 7