Implementing a Queue Using Arrays Along With Source Code

What is a Queue

A queue is a linear structure where adding of items is done at one end but removing of items is done at the other end. It is for this reason that a queue is also called as FIFO (First In First Out) structure. For implementing a queue, we need two pointers or variables called front and rear to keep track of elements that are inserted or deleted from queue. Addition in queue is done at the rear end and deletion is done at the front end. It is same as the queue made in front of a railway reservation counter, the first person in the queue will get the ticket first and after getting the ticket, he/she leaves the queue from the front end and the new person is added at the end of the queue.

Adding value to the Queue

Again, in a queue, there are two indexes/pointers used called front and rear. The rear designates the location where new element is to be inserted and front designates the location from where the element will be removed from queue.

Consider a  queue of size 5 elements. Initially, the rear and front are both -1 as shown in Figure 1

Figure 1 - Queue is empty, front and rear both are -1

When first element is added to the queue, both rear and front subscripts will point at that location. Assuming, value 10 is to be added to the queue, then both front and rear are incremented to 0 and the new value is added at queue[0] location as shown in Figure 2.

Figure 2 - First value added to queue, both front and rear = 0

Thereafter whenever, a new element is added, rear(r) is incremented and the element is added at its location. For example, to add value 20 to the queue, the rear value which is 0 currently, is incremented to 1 and the value 20 is added to the queue at queue[1] location as shown in Figure 3.

Figure 3 - Second value inserted to queue, front =0 and rear =1

Let us assume, we have to add one more value to the queue, say 30. Again, the rear value which is 1 currently, is incremented to 2 and the value 30 is added to the queue at queue[2] location as shown in Figure 4.

Figure 4 - Third value added to queue at rear location, rear becomes 2

When rear reaches to the maximum position i.e. when value of rear becomes 4, any attempt to add more value to the queue,  will display a  message, "queue is full".

Deleting values from the Queue

Elements from the queue can be deleted from front only. More precisely, when the elements are deleted from queue, the element is deleted from the location where index front is pointing. After deleting of value from queue, the value of front is incremented to point at the next value that can be deleted.

Currently, the value of front is 0 i.e. it is pointing at the queue[0] location. The value, 10 at queue[0] location is deleted and value of front index is incremented by 1 as shown in Figure 5.

Figure 5 - Value represented by front is deleted from queue, front increments to 1

Now, the front index value is 1 i.e. it is pointing at queue[1] location. The value at queue[1] location is 20. If we want to delete a value from queue, the value pointed to by front index i.e. 20 will be deleted and after deleting of value, the front index is incremented to 2 as shown in Figure 6. That is, values of front and rear both will become 2.

Figure 6 - Last value pointed to by front is deleted and front and rear are set to -1

The values of front and rear indices are same i.e. 2 and are pointing at the last element in the queue. If this last value is deleted from the queue, the values of front and rear indices are set to -1. The values of front and rear are set to -1 when queue is empty.

 

C Program for implementing a queue using array

# include<stdio.h>

# define max 5

int front=-1,rear=-1;

void addq(int queue[], int value);

int delq(int queue[]);

main()

{

  int q[max];

  int k,n=0;

  while(n!=3)

  {

     printf("\n\n1...Add an element into the queue\n");

     printf("2...Delete an element from the queue\n");

     printf("3...Quit\n");

     printf("Enter your choice 1/2/3:");

     scanf("%d",&n);

     switch(n)

     {

        case 1: 

         if(rear >=max-1)

         {

            printf("Sorry the queue is full\n");

         }

         else

         {

            printf("Enter the value to add: ");

            scanf("%d",&k);

            addq(q,k);

            printf("%d is added to queue\n", k);

         }

         break;

       case 2:   

         k=delq(q);

         if(k!='#')

            printf("Value returned from queue %d\n",k);

         break;

     }

  }

}

void addq(int queue[], int value)

{

  rear++;

  queue[rear]=value;

  if(front==-1)

     front=rear;

}

int delq(int queue[])

{

  int j;

  if(front==-1)

  {

       printf("Sorry queue is

         empty\n");

       return '#';

  }

  else

  {

     if(front==rear)

     {

       j=queue[front];

       front=-1;

       rear=-1;

     }

     else

     {

       j=queue[front];

       front++;

     }

     return(j);

  }

}