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.

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
{
rear->next = newNode;

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

Visual representation of the above algorithm

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
{
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;
}
```