Linear Queue Data Structure in C

Data Structure

There are many ways to store data in programming, that Queue has features that make it all the more special. We all know that data structure is a way of storing or arranging data so that we can use it efficiently. There are two types of queues one is linear, and the other is circular. As of now, we will discuss the Linear model

Linear Data Structure Queue

Linear data structure Queue has data elements that are arranged sequentially. Before stepping into the main topic, we need to understand the basic working of a queue. The very basic principle of Queue is "First in, First Out" it means the element inserted first will get deleted first when the delete operation takes place.

Important features of Linear Queue

The following are the features of linear queue:

1. Similar to a stack, the Queue is a list of items with similar data types.

2. Queues are arranged in a FIFO (First In, First Out) structure.

3. To remove a new element from the Queue, all the elements inserted before the new element must be removed.

The Linear Queue mainly has two ends, one in front and the other in the rear end. Check the below diagram to get an idea.   

 To understand linear Queue simply, imagine you are in a normal Queue in the bank where whenever a new person adds to the Queue, he/she will stand at the end. The first person in the Queue leaves once work is done, so the second person in Queue will become the first person. Simply everyone moves one step ahead right here. Everything will be in order. Look at the image here for a better understanding.

  Once person A finishes work, person B will take the first position, and person C will move ahead.

 Example: Imagine a linear data structure with six elements 7,17,27,37,47,57

Step 1: Here, first element '7' is marked as the front-end element, and last element 57 is marked as the rear element.

  Step 2: Delete an element

As we know in Queue, the first element only gets deleted whenever we perform a delete operation. Now, the front marks the first element, but the first element will be 17 as all the elements move left when one element is deleted. Here rear will skip one step left, as you can notice it.

Step 3: Again, perform the delete operation

Now 17 will be deleted means 27 will its place, and the rear moves left means the rear will be in 2nd position.

Step 4: Again, perform the delete operation

Now 27 will be deleted means 37 will its place, and the rear moves left means the rear will be in 2nd position.

Step 4: Again, perform the delete operation

Now 37 will be deleted means 47 will its place, and the rear moves left means rear will be in 1st position.

Step 6: Again, perform the delete operation

Now 47 will be deleted means 57 will its place, and the rear moves left means the rear will be in the 0th position.

Here, if you observe carefully, both front and rear will be pointing to the same index. It indicates that if another deletion operation is performed, the "Queue" will become empty. Similarly, in a linear Queue, the new elements are inserted from the rear end, and whenever we delete an element, then the front end will get deleted. When the first element gets deleted, then 2nd element will take the first position means all elements will shift left; therefore, rear moves ahead. Check the below sequence so you will understand.

Majorly we can perform three operations on Queue. The following is the list of operations which we can perform on queue:

1. Insertion

2. Deletion

3. Displaying

1. Insertion

Inserting an element in Queue is called insertion. Here, the new element will get added at the rear end, which means at last place.

2. Deletion

This operation deletes or eliminates an element from the Queue. Always Front element in Queue only gets eliminated. The middle-order elements won't be disturbed.

3. Displaying

We can display all the elements in the Queue just by using this operation.

Let's look into the detailed explanation of all the above three operations using algorithms and detailed code.

Linear Queue is a data structure that is easy to implement because computer memory is allocated sequentially. We can implement Linear Queues using two ways one is using a static array, and the second is using a dynamic array. In a static array, the memory of the Queue is fixed. That is, it will be allocated in the compile-time itself, and we cannot change it in run time. In a dynamic array, the memory is allocated in the run time means the memory is not at all fixed, and this is flexible to use that. The size will automatically increase when elements are getting more, and the size gets decreases when elements are deleted.

Step By Step Implementation

Now, let's move to the Implementation using the static array model, which means the memory is allocated at the compile time, and we cannot change it during run time. Simply queue size is fixed. Let's take an example of the Queue with a fixed size of 5. It means we can have 0-5 elements and not more than that, as we know that declaring front and rear end variables are important. Initially, both of them point to 0 means the Queue is empty, so based on these particular variables, let us move to perform operations like insertion and deletion.

1.Insertion

In Queue, the insertion occurs from the rear end, the last end. At first, before inserting, we need to check whether the Queue is full or not why because we cannot insert or add a new element if the Queue is full.

The algorithm is:

Step 1: START

Step 2: Store the element which is to be inserted

Step 3: Check if REAR= MAX-1 then write Queue is full

             else go to step 5

Step 4: Check whether REAR=-1 then set FRONT=REAR=0

              else

              set REAR=REAR+1

Step 5: Set QUEUE [REAR]=Value

Step 6: STOP

Initially, the algorithm gets started in step 2. The new element will be stored in temporary memory in step 3. The main decision takes place, which is if Rear=Max-1 means the rear is pointing to maximum index, then the Queue will be full, and the message is displayed accordingly and then stops. In the other case, that is, if the Queue is not full and we have space to insert an element according to the algorithm, we go to step 5, where the rear value gets updated to the newly inserted value, and then in step 4, the rear value gets incremented by 1, and finally, the algorithm stops.

Here we use the rear variable mostly because the algorithm strictly specifies that insertion should be done at the rear end only. No middle-order element will interfere.

The function to implement the insertion algorithm is as given below

Code Function In C Language

2. Deletion

Here we initially check whether the Queue is empty because if it is empty, we won't be able to delete any element. The front plays a key role in deleting. The algorithm is

Step 1: Start

Step 2: Store the element to insert

Step 3: Check if FRONT=-1 or FRONT>REAR write queue is empty

            And go to step 4

 Step 4: SET VAL = QUEUE[FRONT]          

           SET FRONT = FRONT+1

Step 5 STOP

Code Function In C Language

According to the algorithm, if the rear is pointed at 0, the Queue is empty. We cannot delete an element from the Queue in other cases, we set the value of the front as a new element value, and the front will get incremented by one.

3. Display

To display the elements in the Queue, first, the elements should exist, so first, we check whether the Queue is empty or not. If empty, then there is no point in the display. When at least one element exits, the elements will be displayed. We mostly use a loop to display all the elements from front to rear here.

Code Function In C Language

There are a few other operations in Queue that are:

peek():  This function displays the first element of the Queue, and the important thing is it won't delete the element or modify it..

isFull(): When this function is called, it checks whether does Queue is full or not  

isEmpty(): When this function is called, it checks whether Queue is empty or not.

Complete Linear Queue in Data Structure Program in C language

#include <stdio.h>
#include<stdlib.h>
#define CAPACITY 50
 
void insert();
void delete();
void display();
int queue_array[CAPACITY];
int rear = - 1;
int front = - 1;
void main()
{
    int choice;
    while (1)
    {
        printf("1.Enter 1 to insert element to queue \n");
        printf("2.Enter 2 to delete element from queue \n");
        printf("3.Enter 3 to display all elements of queue \n");
        printf("4.Enter 4 to quit \n");
        printf("Enter your choice : ");
        scanf("%d", &choice);
        switch (choice)
        {
            case 1:
            insert();
            break;
            case 2:
            delete();
            break;
            case 3:
            display();
            break;
            case 4:
            exit(1);
            default:
            printf("Wrong choice \n");
        } 
    } 
} 
 
void insert()
{
    int element;
    if (rear == CAPACITY - 1)
    printf("Queue is full\n");
    else
    {
        if (front == - 1)
        
        front = 0;
        printf("Enter element which is to be inserted ");
        scanf("%d", &element);
        rear = rear + 1;
        queue_array[rear] = element;
    }
} /* End of insert() */
 
void delete()
{
    if (front == - 1 || front > rear)
    {
        printf("Queue is empty we cannot delete an element  \n");
        return ;
    }
    else
    {
        printf("Element deleted from queue is : %d\n", queue_array[front]);
        front = front + 1;
    }
} /* End of delete() */
 
void display()
{
    int i;
    if (front==-1 || front > rear)
        printf("Queue is empty \n");
    else
    {
        printf("Elements of Queue are: \n");
        for (i = front; i <= rear; i++)
            printf("%d ", queue_array[i]);
        printf("\n");
    }
}

Output:

Code Explanation

This is an understandable user code. Initially, we included the important libraries studio. h and stdlib.h, we defined the size of the Queue are constant number 5 means we can only insert 1-5 elements. We took variables queue_array and initialized rear and front values as -1. To make it user-friendly, we gave options to users as entering 1 to insert an element to the Queue, Entering 2 to delete elements from the Queue, Entering 3 to display all elements of the Queue, and Entering 4 to quit. The user will enter the choice if it is "1," and then it goes to the insert function here before inserting an element. The program will check whether the Queue is full or not and then takes an element from the user to insert and increments the rear value by 1, and replaces the rear value with an element value.

If the user enters 2, then the element in the front end will be deleted before the program checks whether the Queue is empty. After deleting, the front value gets incremented by 1. The user enters 3 to check the elements of the Queue. And finally, to quit the loop user will enter 4. In our testing inputs and outputs, we entered two elements, 7 and 17, and displayed those elements, then deleted two elements, and given the choice of 3 now, the program tells us the Queue is empty as no more elements are there in the Queue.

Applications

Queue data structures are often used when FIFO (First In, First Out) is needed. Some major uses of the Queue are as follows:

1. Real-time system or hardware interrupt management.

2. Helps in CPU scheduling and disk scheduling

3. Managing Website Traffic efficiently

4. Maintain playlists in Media Player for listening to songs

5. In Routers and network switches  

Advantages

1. It follows the first-in, first-out rule, making it easy to perform insertion and deletion operations.

2. When it comes to inter-process data communication, queues are fast.

3. A large amount of data can be managed efficiently and easily.

4. When multiple people use a particular service, queues are useful.

5. Other data structures can be implemented using queues.

Disadvantages

1. Operations such as insertion and deletion of elements from the middle are time-consuming and difficult.

2. Adding a new element to the Queue in a classical queue requires that the existing items be deleted first.

3. Compared with other data structures, searching for an element takes more time than O(N).

4. In the static case, a queue's maximum size must be determined beforehand, which is a disadvantage because the user will not be able to compute its exact size at the start.

Comparison of Stacks and Queues

Stacks and queues are linear data structures in which elements are stored in sequence and accessed in a single path. The main difference between stacks and queues in data structures is that stacks follow the LIFO principle, while queues follow the FIFO approach. LIFO (last in, first out) processes the last item inserted in the stack first, while FIFO (first in, first out) processes the first item in the Queue.

Comparison of Linear Queue and Circular Queue

An obvious difference between a linear queue and a circular queue is that a linear queue consists of data arranged sequentially, one after another. In contrast, a circular queue consists of data arranged in a circle by connecting the last element back to the first element.