Queue using linked list

Queue using an array - drawback

If we implement the queue using an array, we need to specify the array size at the beginning(at compile time).

We can't change the size of an array at runtime. So, the queue will only work for a fixed number of elements.

Solution

We can implement the queue data structure using the linked list.

In the linked list, we can change its size at runtime.

Let's implement the queue using linked list

If you are not familiar with linked list and queue, kindly visit the below links before we get started.

Linked List Basics
Queue using array

Node structure for Queue

struct node
{
    int data;
    struct node *next;
};

To point the front and rear node

struct node *front = NULL, *rear = NULL;

Enqueue function

Enqueue function will add the element at the end of the linked list.

Using the rear pointer, we can track the last inserted element.

1. Declare a new node and allocate memory for it.

2. If front == NULL,

make both front and rear points to the new node.

3. Otherwise,

add the new node in rear->next.

make the new node as the rear node. i.e. rear = new node

void enqueue(int val)
{
    struct node *newNode = malloc(sizeof(struct node));
    newNode->data = val;
    newNode->next = NULL;

    //if it is the first node
    if(front == NULL && rear == NULL)
        //make both front and rear points to the new node
        front = rear = newNode;
    else
    {
        //add newnode in rear->next
        rear->next = newNode;

        //make the new node as the rear node
        rear = newNode;
    }
}

Visual representation of the above algorithm

Insert 10

Insert 20

Insert 30

Dequeue function

Dequeue function will remove the first element from the queue.

1.Check whether the queue is empty or not

2.If it is the empty queue (front == NULL)

We can't dequeue the element.

3.Otherwise,

Make the front node points to the next node. i.e front = front->next;

if front pointer becomes NULL, set the rear pointer also NULL.

Free the front node's memory.

void dequeue()
{
    //used to freeing the first node after dequeue
    struct node *temp;

    if(front == NULL)
         printf("Queue is Empty. Unable to perform dequeue\n");
    else
    {
        //take backup
        temp = front;

        //make the front node points to the next node
        //logically removing the front element
        front = front->next;

        //if front == NULL, set rear = NULL
        if(front == NULL)
            rear = NULL;

       //free the first node
       free(temp);
    }

}

Implementation of the queue using linked list

/*
 * Program  : Queue using linked list
 * Language : C
 */

#include<stdio.h>
#include<stdlib.h>

struct node
{
    int data;
    struct node *next;
};

struct node *front = NULL, *rear = NULL;

void enqueue(int val)
{
    struct node *newNode = malloc(sizeof(struct node));
    newNode->data = val;
    newNode->next = NULL;

    //if it is the first node
    if(front == NULL && rear == NULL)
        //make both front and rear points to the new node
        front = rear = newNode;
    else
    {
        //add newnode in rear->next
        rear->next = newNode;

        //make the new node as the rear node
        rear = newNode;
    }
}

void dequeue()
{
    //used to free the first node after dequeue
    struct node *temp;

    if(front == NULL)
         printf("Queue is Empty. Unable to perform dequeue\n");
    else
    {
        //take backup
        temp = front;

        //make the front node points to the next node
        //logically removing the front element
        front = front->next;

        //if front == NULL, set rear = NULL
        if(front == NULL)
            rear = NULL;

       //free the first node
       free(temp);
    }

}

void printList()
{
    struct node *temp = front;

    while(temp)
    {
        printf("%d->",temp->data);
        temp = temp->next;
    }
    printf("NULL\n");
}

int main()
{
    enqueue(10);
    enqueue(20);
    enqueue(30);
    printf("Queue :");
    printList();
    dequeue();
    printf("After dequeue the new Queue :");
    printList();
    dequeue();
    printf("After dequeue the new Queue :");
    printList();

    return 0;
}