Data Structures Tutorial

Data Structures Tutorial Asymptotic Notation Structure and Union Array Data Structure Linked list Data Structure Type of Linked list Advantages and Disadvantages of linked list Queue Data Structure Implementation of Queue Stack Data Structure Implementation of Stack Sorting Insertion sort Quick sort Selection sort Heap sort Merge sort Bucket sort Count sort Radix sort Shell sort Tree Traversal of the binary tree Binary search tree Graph Spanning tree Linear Search Binary Search Hashing Collision Resolution Techniques

Misc Topic:

Priority Queue in Data Structure Deque in Data Structure Difference Between Linear And Non Linear Data Structures Queue Operations In Data Structure About Data Structures Data Structures Algorithms Types of Data Structures Big O Notations Introduction to Arrays Introduction to 1D-Arrays Operations on 1D-Arrays Introduction to 2D-Arrays Operations on 2D-Arrays Strings in Data Structures String Operations Application of 2D array Bubble Sort Insertion Sort Sorting Algorithms What is DFS Algorithm What Is Graph Data Structure What is the difference between Tree and Graph What is the difference between DFS and BFS Bucket Sort Dijkstra’s vs Bellman-Ford Algorithm Linear Queue Data Structure in C Stack Using Array Stack Using Linked List Recursion in Fibonacci Stack vs Array What is Skewed Binary Tree Primitive Data Structure in C Dynamic memory allocation of structure in C Application of Stack in Data Structures Binary Tree in Data Structures Heap Data Structure Recursion - Factorial and Fibonacci What is B tree what is B+ tree Huffman tree in Data Structures Insertion Sort vs Bubble Sort Adding one to the number represented an array of digits Bitwise Operators and their Important Tricks Blowfish algorithm Bubble Sort vs Selection Sort Hashing and its Applications Heap Sort vs Merge Sort Insertion Sort vs Selection Sort Merge Conflicts and ways to handle them Difference between Stack and Queue AVL tree in data structure c++ Bubble sort algorithm using Javascript Buffer overflow attack with examples Find out the area between two concentric circles Lowest common ancestor in a binary search tree Number of visible boxes putting one inside another Program to calculate the area of the circumcircle of an equilateral triangle Red-black Tree in Data Structures Strictly binary tree in Data Structures 2-3 Trees and Basic Operations on them Asynchronous advantage actor-critic (A3C) Algorithm Bubble Sort vs Heap Sort Digital Search Tree in Data Structures Minimum Spanning Tree Permutation Sort or Bogo Sort Quick Sort vs Merge Sort Boruvkas algorithm Bubble Sort vs Quick Sort Common Operations on various Data Structures Detect and Remove Loop in a Linked List How to Start Learning DSA Print kth least significant bit number Why is Binary Heap Preferred over BST for Priority Queue Bin Packing Problem Binary Tree Inorder Traversal Burning binary tree Equal Sum What is a Threaded Binary Tree? What is a full Binary Tree? Bubble Sort vs Merge Sort B+ Tree Program in Q language Deletion Operation from A B Tree Deletion Operation of the binary search tree in C++ language Does Overloading Work with Inheritance Balanced Binary Tree Binary tree deletion Binary tree insertion Cocktail Sort Comb Sort FIFO approach Operations of B Tree in C++ Language Recaman’s Sequence Tim Sort Understanding Data Processing Applications of trees in data structures Binary Tree Implementation Using Arrays Convert a Binary Tree into a Binary Search Tree Create a binary search tree Horizontal and Vertical Scaling Invert binary tree LCA of binary tree Linked List Representation of Binary Tree Optimal binary search tree in DSA Serialize and Deserialize a Binary Tree Tree terminology in Data structures Vertical Order Traversal of Binary Tree What is a Height-Balanced Tree in Data Structure Convert binary tree to a doubly linked list Fundamental of Algorithms Introduction and Implementation of Bloom Filter Optimal binary search tree using dynamic programming Right side view of binary tree Symmetric binary tree Trim a binary search tree What is a Sparse Matrix in Data Structure What is a Tree in Terms of a Graph What is the Use of Segment Trees in Data Structure What Should We Learn First Trees or Graphs in Data Structures All About Minimum Cost Spanning Trees in Data Structure Convert Binary Tree into a Threaded Binary Tree Difference between Structured and Object-Oriented Analysis FLEX (Fast Lexical Analyzer Generator) Object-Oriented Analysis and Design Sum of Nodes in a Binary Tree What are the types of Trees in Data Structure What is a 2-3 Tree in Data Structure What is a Spanning Tree in Data Structure What is an AVL Tree in Data Structure Given a Binary Tree, Check if it's balanced

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.   

Linear Queue Data Structure In C

 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.

Linear Queue Data Structure In C

  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.

Linear Queue Data Structure In C

  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.

Linear Queue Data Structure In C

Step 3: Again, perform the delete operation

Linear Queue Data Structure In C

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

Linear Queue Data Structure In C

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

Linear Queue Data Structure In C

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

Linear Queue Data Structure In C

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.

Linear Queue Data Structure In C

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

Linear Queue Data Structure In C

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

Linear Queue Data Structure In C

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

Linear Queue Data Structure In C

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:

Linear Queue Data Structure In C

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.



ADVERTISEMENT
ADVERTISEMENT