Linear Queue In Data Structure

Introduction to Data Structures

Data structures are a subject that studies the different ways to store and organize data. Data can be stored in many forms, such as arrays, linked lists, stacks, queues, trees, and graphs. Organizing data is an essential part of programming. Data structures are one of the most popular ways of organizing data.

Different types of data structures are used by programmers to organize data. Every data structure has its way of storing data. For example, an array stores data in a linear way while a binary tree stores data in a tree-like structure. One of the most popular and commonly used data structures is Queue. Queue stores data in a linear way just like an array and linear list, but follows a particular order like Stack.

A queue can be created in multiple ways. We can create linear queues, priority queues, and circular queues. While the basic functionality is the same, the implementation is different. In this article, we will discuss the most commonly used type of queue – the linear queue.

Understanding linear queue

A linear queue follows the First In First Out (FIFO) order, meaning, the element that is added first will be removed first. Let’s understand the working of a linear queue with the help of a real-life example.

Suppose you went to a cinema. You see a line outside the ticket booth. You stand behind the line and four men are standing ahead of you. When the booth opens, the very first person buys the ticket and leaves. Then the second person buys the ticket and leaves. You cannot leave with the ticket before the four men standing ahead of you. So this is a linear queue.

Two types of operations are performed on linear queues:

  1. Enqueue – This operation inserts an element at the rear, meaning, end of the queue.
  2. Dequeue – This operation removes the element from the front of the queue.

The linear queue can be implemented in two ways:

  1. By using arrays.
  2. By using linear lists.

In this article, we will use arrays for implementing a linear queue.

Implementing linear queue

Let’s start by declaring the required variables.

#include <stdio.h>
#define maxvalue 5

int queue[maxvalue];
int front = -1;
int rear = -1;

int main(void) {  
}

Initially, the queue will be empty and can hold up to 5 elements. Observe the two variables – “front” and “rear”. These two are initialized with -1, meaning, the queue is empty. Their values will change with the insertion and deletion of elements.

Next, let’s declare the functions that will perform different operations on the queue.

#include <stdio.h>
#define maxvalue 5

int queue[maxvalue];
int front = -1;
int rear = -1;

void insert_element(void);
void delete_element(void);
void display_queue(void);
void peek_queue(void);

void main() {

}

Let’s discuss what each of the above functions is doing.

  • insert_element: Inserts an element at the end of the linear queue.
  • delete_element: Deletes an element from the front of the queue.
  • display_queue: Display the linear queue.

Before implementing the functions, let’s add a switch to the main body.

#include <stdio.h>
#define maxvalue 5

int queue[maxvalue];
int front = -1;
int rear = -1;

void insert_element(void);
void delete_element(void);
void display_queue(void);
void peek_queue(void);

int main(void) {
    
    int choice = 0;
   
    while(choice!=-1)
    {
        printf("\nEnter 1 to insert an element");
        printf("\nEnter 2 to delete an element");
        printf("\nEnter 3 to display the queue");
        printf("\nEnter 4 to peek");
        printf("\nEnter -1 to abort\n");
        scanf("%d", &choice);
        
        switch(choice)
        {
            case 1:
            insert_element();
            break;
            case 2:
            delete_element();
            break;
            case 3:
            display_queue();
            break;
            case 4:
            peek_queue();
            break;
	default:
            printf("INVALID");

        }
    }
    
    printf("ABORTED!");    
}

Now, let’s implement the functions one by one starting with insert_element().

void insert_element(){
    int val;
    printf("ENTER A VALUE!\n");
    scanf("%d", &val);
    if(rear == maxvalue-1){
        printf("\nQUEUE OVERFLOW");
    }
    else{
        if(front == -1){
            front++;
        }
        rear++;
        queue[rear] = val;
    }    
}

In the insert_element() function, after inputting a value, first,, we check if “rear” is equal to “maxvalue”. If yes, then the queue is overflowing. If not, then we insert the element at the “rear”.

Next, let’s create the delete_element() function.

void delete_element(){
    if(front > rear || front == -1){
        printf("QUEUE UNDERFLOW");
    }
    else{
        printf("VALUE DELETED: %d", queue[front]);
        front++;
        if(front > rear)
        {
            front = -1;
            rear = -1;
        }
    }    
}

First, we check the underflow condition. If the condition is false, then the first element of the queue is deleted. To do this, the value of “front” is incremented by 1. Remember, if the value of “front” crosses the value of “rear”, then the queue is empty. So we have to assign -1 to both “front” and “rear”.

The peek_element() function returns the first element of the queue, meaning, the element at the front.

void peek_queue(){
    if(front > rear || front == -1){
        printf("QUEUE IS EMPTY");   
    }
    else{
        printf("FRONT ELEMENT: %d", queue[front]);
    }
}

In the last, the display_queue() function will display the entire queue and the values of “front” and “rear”.

void display_queue(){
    if(front > rear || front == -1){
        printf("QUEUE IS EMPTY");   
    }
    else{
    
        int x;
        printf("QUEUE: ");
        for(x = front; x <= rear; x++)
        {
            printf("%d ", queue[x]);
        }
        printf("\n");
        printf("FRONT: %d\n", front);
        printf("REAR: %d\n", rear);
    }
}

The entire code is ready. Let’s put everything together.

#include <stdio.h>
#define maxvalue 5

int queue[maxvalue];
int front = -1;
int rear = -1;

void insert_element(void);
void delete_element(void);
void display_queue(void);
void peek_queue(void);

int main(void) {
    
    int choice = 0;
    
    while(choice!=-1)
    {
        printf("\nEnter 1 to insert an element");
        printf("\nEnter 2 to delete an element");
        printf("\nEnter 3 to display the queue");
        printf("\nEnter 4 to peek");
        printf("\nEnter -1 to abort\n");
        scanf("%d", &choice);

        
        switch(choice)
        {
            case 1:
            insert_element();
            break;
            case 2:
            delete_element();
            break;
            case 3:
            display_queue();
            break;
            case 4:
            peek_queue();
            break;
default:
            printf("INVALID");
        }
    }
    
    printf("ABORTED!");
   
}

void insert_element(){
    int val;
    printf("ENTER A VALUE!\n");
    scanf("%d", &val);
    if(rear == maxvalue-1){
        printf("\nQUEUE OVERFLOW");
    }
    else{
        if(front == -1){
            front++;
        }
        rear++;
        queue[rear] = val;
    }
    
}

void delete_element(){
    
    if(front > rear || front == -1){
        printf("QUEUE UNDERFLOW");
    }
    else{
        printf("VALUE DELETED: %d", queue[front]);
        front++;
        if(front > rear)
        {
            front = -1;
            rear = -1;
        }
    }
    
}

void display_queue(){
    if(front > rear || front == -1){
        printf("QUEUE IS EMPTY");   
    }
    else{
    
        int x;
        printf("QUEUE: ");
        for(x = front; x <= rear; x++)
        {
            printf("%d ", queue[x]);
        }
        printf("\n");
        printf("FRONT: %d\n", front);
        printf("REAR: %d\n", rear);
    }
}


void peek_queue(){
    if(front > rear || front == -1){
        printf("QUEUE IS EMPTY");   
    }
    else{
        printf("FRONT ELEMENT: %d", queue[front]);
    }
}

Let’s insert one value.

output 1

Similarly we can insert four more values. Let’s display the queue after adding those five values.

output 2

Let’s delete a value.

output 3

And finally, let’s peek.

So this is how the linear queue is implemented!

Wrapping it up

The linear queue is a popular and commonly used data structure. It adds an element at the end and removes an element from the front. We can implement a linear queue using an array or linear list. In this article, we discussed what a linear queue is and how to implement it using an array.

Recent Articles

Related Stories

Leave A Reply

Please enter your comment!
Please enter your name here

Subscribe to get IQ's , Tutorials & Courses