Linear Queue Implementation

Similar to Stack, Queue is a linear data structure that follows a particular order in which the operations are performed for storing data. The order is First In First Out (FIFO). One can imagine a queue as a line of people waiting to receive something in sequential order which starts from the beginning of the line. It is an ordered list in which insertions are done at one end which is known as the rear and deletions are done from the other end known as the front. A good example of a queue is any queue of consumers for a resource where the consumer that came first is served first.

The difference between stacks and queues is in removing. In a stack we remove the item the most recently added; in a queue, we remove the item the least recently added.

It has three components:

A Container of items that contains elements of queue.
A pointer front that points the first item of the queue.
A pointer rear that points the last item of the queue.

Operations associated with a queue in C :

isEmpty(): To check if the queue is empty
isFull(): To check whether the queue is full or not
dequeue(): Removes the element from the frontal side of the queue
enqueue(): It inserts elements to the end of the queue
Front: Pointer element responsible for fetching the first element from the queue
Rear: Pointer element responsible for fetching the last element from the queue

Algorithm

Queue follows the First-In-First-Out pattern. The first element is the first to be pulled out from the list of elements.

Front and Rear pointers keep the record of the first and last element in the queue.
At first, we need to initialize the queue by setting Front = -1 and Rear = -1
In order to insert the element (enqueue), we need to check whether the queue is already full i.e. check the condition for Overflow. If the queue is not full, we'll have to increment the value of the Rear index by 1 and place the element at the position of the Rear pointer variable. When we get to insert the first element in the queue, we need to set the value of Front to 0.
In order to remove the element (dequeue) from the queue, we need to check whether the queue is already empty i.e. check the condition for Underflow. If the queue is not empty, we'll have to remove and return the element at the position of the Front pointer, and then increment the Front index value by 1. When we get to remove the last element from the queue, we will have to set the values of the Front and Rear index to -1.

Queues in C can be implemented using Arrays, Lists, Structures, etc. Below here we have implemented queues using Arrays in C.

Program using C

//LINEAR QUEUE
#include<stdio.h>
    #include<stdlib.h>
    #define max 10
    int front=-1, rear=-1;
    void insert(int [], int);
    void display(int[]);
    int del(int []);
    int main()
    {
        int item, ch, LQ[max],deleted_item;
        while(1)
        {
            printf("\nMENU\n1.Display\n2.Insert\n3.Delete\n4.Exit\nEnter your choice: ");
            scanf("%d",&ch);
            switch(ch)
            {
                case 1:
                    display(LQ);
                    break;
                case 2:
                    printf("Enter the element to be inserted: ");
                    scanf("%d",&item);
                    insert(LQ, item);
                    break;
                case 3: 
                    deleted_item = del(LQ);
                    if(deleted_item != -1)
                        printf("Deleted item is: %d",deleted_item);
                    break;
                case 4: exit(0);				
            }
        }
    }
    
    void display(int LQ[])
    {
        int i;
        if(front==-1)
            printf("Queue is empty");
        else
        {
            printf("Queue is: ");
            for(i=front;i<=rear;i++)
                printf("%d<--",LQ[i]);
        }	
    }
    
    void insert(int LQ[], int item)
    {
        if(rear==max-1)
            printf("Queue is full");
        else
        {
            if(front==-1)
                front=rear=0;
            else
                rear=rear+1;
            LQ[rear]=item;		
        }	
    }
    
    int del(int LQ[])
    {
        int item;
        if(front==-1)
        {
            printf("Queue is empty");
            return(-1);
        }
        else
        {
            item=LQ[front];
            if(front==rear)
                front=rear=-1;
            else
                front = rear+1;
            return(item);		
        }
    }