Queue Using Array

A queue data structure can be implemented using one dimensional array. The queue implemented using array stores only fixed number of data values. The implementation of queue data structure using array is very simple. Just define a one dimensional array of specific size and insert or delete the values into that array by using FIFO (First In First Out) principle with the help of variables 'front' and 'rear'. Initially both 'front' and 'rear' are set to -1. Whenever, we want to insert a new value into the queue, increment 'rear' value by one and then insert at that position. Whenever we want to delete a value from the queue, then delete the element which is at 'front' position and increment 'front' value by one.

 

The above figure shows the queue of characters forming the English word "HELLO". Since, No deletion is performed in the queue till now, therefore the value of front remains -1 . However, the value of rear increases by one every time an insertion is performed in the queue. After inserting an element into the queue shown in the above figure, the queue will look something like following. The value of rear will become 5 while the value of front remains same. 

 

 After deleting an element, the value of front will increase from -1 to 0. however, the queue will look something like following.

 

Queue Operations using Array

 

Queue data structure using array can be implemented as follows...

 

Before we implement actual operations, first follow the below steps to create an empty queue.

• Step 1 - Include all the header files which are used in the program and define a constant 'SIZE' with specific value.
• Step 2 - Declare all the user defined functions which are used in queue implementation.
• Step 3 - Create a one dimensional array with above defined SIZE (int queue[SIZE])
• Step 4 - Define two integer variables 'front' and 'rear' and initialize both with '-1'. (int front = -1, rear = -1)
• Step 5 - Then implement main method by displaying menu of operations list and make suitable function calls to perform operation selected by the user on queue.

 

enQueue(value) - Inserting value into the queue

In a queue data structure, enQueue() is a function used to insert a new element into the queue. In a queue, the new element is always inserted at rear position. The enQueue() function takes one integer value as a parameter and inserts that value into the queue. We can use the following steps to insert an element into the queue...

• Step 1 - Check whether queue is FULL. (rear == SIZE-1)
• Step 2 - If it is FULL, then display "Queue is FULL!!! Insertion is not possible!!!" and terminate the function.
• Step 3 - If it is NOT FULL, then increment rear value by one (rear++) and set queue[rear] = value.

deQueue() - Deleting a value from the Queue

In a queue data structure, deQueue() is a function used to delete an element from the queue. In a queue, the element is always deleted from front position. The deQueue() function does not take any value as parameter. We can use the following steps to delete an element from the queue...

• Step 1 - Check whether queue is EMPTY. (front == rear)
• Step 2 - If it is EMPTY, then display "Queue is EMPTY!!! Deletion is not possible!!!" and terminate the function.
• Step 3 - If it is NOT EMPTY, then increment the front value by one (front ++). Then display queue[front] as deleted element. Then check whether both front and rear are equal (front == rear), if it TRUE, then set both front and rear to '-1' (front = rear = -1).

display() - Displays the elements of a Queue

We can use the following steps to display the elements of a queue...

• Step 1 - Check whether queue is EMPTY. (front == rear)
• Step 2 - If it is EMPTY, then display "Queue is EMPTY!!!" and terminate the function.
• Step 3 - If it is NOT EMPTY, then define an integer variable 'i' and set 'i = front'.
• Step 4 - Display 'queue[i]' value and increment 'i' value by one (i++). Repeat the same until 'i' value reaches to rear (i <= rear)

 

Implementation of Queue using Array  in C programming

    #include<stdio.h>   
    #include<stdlib.h>  
    #define SIZE 5  
    void insert();  
    void delete();  
    void display();  
    int front = -1, rear = -1;  
    int queue[SIZE];  
    void main ()  
    {  
        int choice;   
        while(choice != 4)   
        {     
            printf("\n*************************Main Menu*****************************\n"); 
            printf("\n1.insert an element\n2.Delete an element\n3.Display the queue\n4.Exit\n");  
            printf("\nEnter your choice ?");  
            scanf("%d",&choice);  
            switch(choice)  
            {  
                case 1:  
                insert();  
                break;  
                case 2:  
                delete();  
                break;  
                case 3:  
                display();  
                break;  
                case 4:  
                exit(0);  
                break;  
                default:   
                printf("\nEnter valid choice??\n");  
            }  
        }  
    }  
    void insert()  
    {  
        int item;  
        printf("\nEnter the element\n");  
        scanf("\n%d",&item);      
        if(rear ==SIZE-1)  
        {  
            printf("\nOVERFLOW\n");  
            return;  
        }  
        if(front == -1 && rear == -1)  
        {  
            front = 0;  
            rear = 0;  
        }  
        else   
        {  
            rear = rear+1;  
        }  
        queue[rear] = item;  
        printf("\nValue inserted ");  
          
    }  
    void delete()  
    {  
        int item;   
        if (front == -1 || front > rear)  
        {  
            printf("\nUNDERFLOW\n");  
            return;  
                  
        }  
        else  
        {  
            item = queue[front];  
            if(front == rear)  
            {  
                front = -1;  
                rear = -1 ;  
            }  
            else   
            {  
                front = front + 1;  
            }  
            printf("\nvalue deleted ");  
        }  
          
          
    }  
          
    void display()  
    {  
        int i;  
        if(rear == -1)  
        {  
            printf("\nEmpty queue\n");  
        }  
        else  
        {   printf("\nprinting values .....\n");  
            for(i=front;i<=rear;i++)  
            {  
                printf("\n%d\n",queue[i]);  
            }     
        }  
    } 

 

 Output