Write a C program to implement queue data structure using linked list. In this post I will explain queue implementation using linked list in C language.
In previous post, I explained about queue implementation using array. Here, I will explain how to implement a basic queue using linked list in C programming. Along with I will explain how to perform enqueue and dequeue operations on Queue in C language.
Required knowledge
Functions, Structure, Pointers, Dynamic Memory Allocation
Before continuing to this post, you must have a basic knowledge of linked list. How to create and traverse a linked list.
What is Queue?
Queue is a linear data structure where elements are ordered in special fashion i.e. FIFO (First In First Out). Which means element inserted first to the queue will be removed first from the queue.
In real life you have come across various queue examples. Such as queue of persons at ticket counter, where the first person entering queue gets ticket first.
Operations performed on Queue
On queue we generally perform two basic operations.
Queue structure
Before you perform any operations on queue, you need a queue structure. Let us first define a custom type to represent our individual queue node.
typedef struct node
{
int data;
struct node * next;
} Queue;Note: In the above declaration I have used typedef. It is used to create an alias for our new type. Hence, in program I will use Queue instead of struct node.
Read more about typedef in C language.
After defining queue structure node, we will need few variables to keep track of our queue. Let us define them one after another.
unsigned int size = 0; // Size of queue
Queue *rear, *front; // Reference of rear and front node in queueHow to enqueue an element in Queue using linked list?
Insertion of new element in queue is known as enqueue. You can enqueue a new element at rear of the queue, if its capacity is not full.
Step by step descriptive logic to enqueue an element in queue.
- If queue size is more than capacity, then throw out of capacity error. Otherwise continue to next step.
- Allocate memory for node of
Queuetype usingmalloc(). SayQueue *newNode = (Queue *) malloc (sizeof(Queue));. - Make sure that the newly created node points to nothing i.e.
newNode->next = NULL; - Assign data to the new node, may be user input.
- If queue is not empty then link
rearnode tonewNode. Say(*rear)->next = newNode;. - Make
newNodeasrear. Since after each enqueue rear gets changed. - If its first node in queue then make it as front node too, say
*front = *rear;. - Finally after each successful enqueue, increment
size++by one.
How to dequeue an element from Queue using linked list?
Removal of an existing element from queue is known as dequeue. You can perform dequeue from front of the queue, if its not empty.
Step by step descriptive logic to dequeue element from queue using linked list.
- If queue is empty, then throw empty queue error. Otherwise continue to next step.
- Get front element from queue, which is our required element to dequeue. Store it in some variable say
Queue *toDequeue = *front;. Also store its data to some variable sayint data = toDequeue->data; - Move
frontnode ahead. To make sure that it points to next node after the first node. Say*front = (*front)->next;. - Decrement
size--;by one. - Free the dequeued element from memory to save resources, say
free(toDequeue);. - Return
data, which is our required dequeued element.
Program to implement queue using linked list
Let us transform the above logic to functional programming block. In addition to enqueue and dequeue operation I have also implemented isEmpty(), isFull(), getRear() and getFront() method to perform respective actions.
/**
* Queue implementation using linked list in C.
*/
#include <stdio.h>
#include <stdlib.h>
#include <limits.h>
#define CAPACITY 100 // Queue max capacity
/* Queue structure definition */
typedef struct node
{
int data;
struct node * next;
} Queue; // Queue is a typedef of struct node
/* Queue size */
unsigned int size = 0;
int enqueue(Queue ** rear, Queue ** front, int data);
int dequeue(Queue ** front);
int getRear(Queue * rear);
int getFront(Queue * front);
int isEmpty();
int isFull();
int main()
{
int ch, data;
Queue *rear, *front;
rear = NULL;
front = NULL;
/* Run indefinitely until user manually terminates */
while (1)
{
/* Queue menu */
printf("--------------------------------------------\n");
printf(" QUEUE LINKED LIST IMPLEMENTATION PROGRAM \n");
printf("--------------------------------------------\n");
printf("1. Enqueue\n");
printf("2. Dequeue\n");
printf("3. Size\n");
printf("4. Get Rear\n");
printf("5. Get Front\n");
printf("0. Exit\n");
printf("--------------------------------------------\n");
printf("Select an option: ");
scanf("%d", &ch);
/* Menu control switch */
switch (ch)
{
case 1:
printf("\nEnter data to enqueue: ");
scanf("%d", &data);
// Enqueue function returns 1 on success
// otherwise 0
if (enqueue(&rear, &front, data))
printf("Element added to queue.");
else
printf("Queue is full.");
break;
case 2:
data = dequeue(&front);
// on success dequeue returns element removed
// otherwise returns INT_MIN
if (data == INT_MIN)
printf("Queue is empty.");
else
printf("Data => %d", data);
break;
case 3:
// isEmpty() function returns 1 if queue is emtpy
// otherwise returns 0
if (isEmpty())
printf("Queue is empty.");
else
printf("Queue size => %d", size);
break;
case 4:
data = getRear(rear);
if (data == INT_MIN)
printf("Queue is empty.");
else
printf("Rear => %d", data);
break;
case 5:
data = getFront(front);
if (data == INT_MIN)
printf("Queue is empty.");
else
printf("Front => %d", data);
break;
case 0:
printf("Exiting from app.\n");
exit(0);
default:
printf("Invalid choice, please input number between (0-5).");
break;
}
printf("\n\n");
}
}
/**
* Enqueues/Insert an element at the rear of a queue.
* Function returns 1 on success otherwise returns 0.
*/
int enqueue(Queue ** rear, Queue ** front, int data)
{
Queue * newNode = NULL;
// Check queue out of capacity error
if (isFull())
{
return 0;
}
// Create a new node of queue type
newNode = (Queue *) malloc (sizeof(Queue));
// Assign data to new node
newNode->data = data;
// Initially new node does not point anything
newNode->next = NULL;
// Link new node with existing last node
if ( (*rear) )
{
(*rear)->next = newNode;
}
// Make sure newly created node is at rear
*rear = newNode;
// Link first node to front if its NULL
if ( !( *front) )
{
*front = *rear;
}
// Increment quque size
size++;
return 1;
}
/**
* Dequeues/Removes an element from front of the queue.
* It returns the element on success otherwise returns
* INT_MIN as error code.
*/
int dequeue(Queue ** front)
{
Queue *toDequque = NULL;
int data = INT_MIN;
// Queue empty error
if (isEmpty())
{
return INT_MIN;
}
// Get element and data to dequeue
toDequque = *front;
data = toDequque->data;
// Move front ahead
*front = (*front)->next;
// Decrement size
size--;
// Clear dequeued element from memory
free(toDequque);
return data;
}
/**
* Gets, element at rear of the queue. It returns the element
* at rear of the queue on success otherwise return INT_MIN as
* error code.
*/
int getRear(Queue * rear)
{
// Return INT_MIN if queue is empty otherwise rear.
return (isEmpty())
? INT_MIN
: rear->data;
}
/**
* Gets, element at front of the queue. It returns the element
* at front of the queue on success otherwise return INT_MIN as
* error code.
*/
int getFront(Queue * front)
{
// Return INT_MIN if queue is empty otherwise front.
return (isEmpty())
? INT_MIN
: front->data;
}
/**
* Checks, if queue is empty or not.
*/
int isEmpty()
{
return (size <= 0);
}
/**
* Checks, if queue is within the maximum queue capacity.
*/
int isFull()
{
return (size > CAPACITY);
}-------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 2 Queue is empty. -------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 3 Queue is empty. -------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 4 Queue is empty. -------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 5 Queue is empty. -------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 1 Enter data to enqueue: 10 Element added to queue. -------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 1 Enter data to enqueue: 20 Element added to queue. -------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 1 Enter data to enqueue: 30 Element added to queue. -------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 1 Enter data to enqueue: 40 Element added to queue. -------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 3 Queue size => 4 -------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 4 Rear => 40 -------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 5 Front => 10 -------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 2 Data => 10 -------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 2 Data => 20 -------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 2 Data => 30 -------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 2 Data => 40 -------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 2 Queue is empty. -------------------------------------------- QUEUE LINKED LIST IMPLEMENTATION PROGRAM -------------------------------------------- 1. Enqueue 2. Dequeue 3. Size 4. Get Rear 5. Get Front 0. Exit -------------------------------------------- Select an option: 0 Exiting from app.
Have any doubt or suggestion, feel free to write to us below in the comments section 🙂