Array implementation of queue

We have seen an introduction to Queue data structure and how to implement it using linked list.

Now we shall try to implement the queue using an array.

In linked list, front and rear were pointers to nodes with first element of the queue and last element of the queue respectively. In case of array, front is the  index of array which store first element of queue and rear is the index after the last element of the queue

So how do we start the implementation.

• To start with set front and rear = 0
• If front = rear, queue is empty.
• If rear = max , (max is size of array) queue is full
• enqueue
• If queue is not full
• set array[rear] to new value
• increment rear
• dequeue
• If queue is not empty
• set temp to array[front]
• increment front

First let us write isEmpty() function which checks whether queue is empty by inspecting whether front is equal to rear

int is_empty(int front,int rear)
{
   return front==rear;
}

Next to enqueue function we need to send array as a parameter, value to be inserted into the queue and value of rear. Rear must be pointer parameter because the function will modify rear.

void enqueue(int *arr, int *rearptr,int num)
{
 if(*rearptr == MAX)/* check queue is full*/
 {
    printf("Queue is full");
        }
 else
 {
    arr[*rearptr]=num;
     (*rearptr)++;
         }         
}

So we are checking if the queue is full by seeing whether rear is equal to size of the array. If not, we add the new value at array[rear] and then we increment rear.

Next we will write dequeue function. This function needs array and front as parameters and it will return the dequeued element.

int dequeue(int *arr,int *frontptr,int *rearptr)
{
    int temp = -1;
    if(*frontptr==*rearptr)
    {
 printf("Queue is empty");
    }
    else
    {
  temp = arr[*frontptr];
        (*frontptr)++;
     }
     return temp;
}

 Here we check if the queue is empty. If not we remove the front element of queue and increment front.

That's it. Our simple queue implementation is ready.

Let us look at the complete program.

#include<stdio.h>
#define MAX 5 

 void enqueue(int *arr,   int *rearptr,int num)
{
 if(*rearptr == MAX)
 {
    printf("Queue is full");
        }
 else
 {
    arr[*rearptr]=num;
     (*rearptr)++;
         }
         
}
int is_empty(int front,int rear)
{
   return front==rear;
}

int dequeue(int *arr,int *frontptr,int *rearptr)
{
    int temp = -1;
    if(*frontptr==*rearptr)
    {
 printf("Queue is empty");
    }
    else
    {
  temp = arr[*frontptr];
        (*frontptr)++;
     }
     return temp;
}

void print_queue(int *arr,int front, int rear)
{
    int i;
    for(i = front;i<rear;i++)
 printf("%d---",arr[i]);
    printf("\n");
}
 
int main()
{
   int arr[MAX];
   int i ;
   int front =0,rear = 0;
   while(1)
   {
       printf("Enter 1 - enqueue 2 - dequeue 3 - exit");
       int opt;
       scanf("%d",&opt);
       if(opt==1)
       {
  int n;
           printf("Enter a number:");
  scanf("%d",&n);
  enqueue(arr,&rear,n);
                print_queue(arr,front,rear);
 }
 else if(opt==2)
 {
   
  int n;            
  n = dequeue(arr,&front,&rear);
  if (n!=-1)
   printf("Value dequed is %d\n",n);
  print_queue(arr,front,rear);
        }  
 else
  break;
   }
   return 0;
}  

Here is the partial output of the program.

We can clearly see the problem here. When we add 5 elements to the queue, it will be full (our queue size is 5, for the sake of simplicity). Next we are dequeuing elements, all of them. And queue is empty. But as rear is still = MAX, the program does not let us enqueue saying queue is full.

To overcome this problem, we need to use circular queues, which we will see in next post.