Published: 18 Feb 2025 | Reading Time: 3 min read
A queue is a linear data structure that operates on the First-In-First-Out (FIFO) principle, where the first element added to the queue will be the first one to be removed. Unlike arrays, queues implemented using linked lists can dynamically adjust their size, allowing for efficient memory usage. This article explores implementing a queue using linked list in C, covering key operations and code examples.
A queue in C is a linear data structure that follows the FIFO principle. This means that elements are added to the back (rear) of the queue and removed from the front (front) of the queue. It can be implemented using arrays or linked lists.
A linked list comprises nodes containing two parts: the data it holds and a pointer to the next node in the sequence. This structure allows for efficient insertion and deletion of elements, as nodes can be added or removed without shifting other aspects.
A variable that holds the memory address of another variable. It allows indirect access to the value stored at that address.
A basic unit of data structure, typically containing:
In our queue implementation, each node will have the following structure:
struct Node {
int data; // The data stored in the node
struct Node* next; // Pointer to the next node
};
Here are some disadvantages of using an array as a queue:
A queue implemented using a linked list is a dynamic data structure that efficiently manages elements in a First-In-First-Out (FIFO) manner. It contains two pointers such as:
Initially, both pointers are set to NULL, indicating an empty queue:
struct Node* front = NULL;
struct Node* rear = NULL;
The main operations performed on a linked list queue include:
The enqueue operation adds an element to the rear of the queue.
void enqueue(int value);
Suppose we want to enqueue values 10, 20, and 30 into an initially empty queue.
Here is the enqueue operation in queue in c using linked list:
void enqueue(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
newNode->data = value;
newNode->next = NULL;
if (rear == NULL) { // Queue is empty
front = rear = newNode;
return;
}
rear->next = newNode; // Link new node at end
rear = newNode; // Update rear pointer
}
Front -> [10] -> [20] -> [30] -> NULL
The dequeue operation eliminates an item from the front of the queue.
void dequeue();
After enqueuing values (10, 20, and 30), if we perform a dequeue operation, we remove 10.
Here is the dequeue implementation using linked list in c:
void dequeue() {
if (front == NULL) {
printf("Queue is empty.\n");
return;
}
struct Node* temp = front; // Backup front node
front = front->next; // Move front to next node
if (front == NULL) {
rear = NULL; // If queue becomes empty, update rear
}
free(temp); // Free memory of dequeued node
}
Front -> [20] -> [30] -> NULL
Returns the front element present in the queue without removing it.
int peek(struct Stack* s);
Here is the queue implementation using linked list in c for peek operation:
#include <stdio.h>
#define MAXSIZE 10
struct Stack {
int items[MAXSIZE];
int top;
};
// isEmpty Function
int isEmpty(struct Stack* s) {
return s->top == -1; // Returns 1 if empty, 0 otherwise
}
// Peek Function
int peek(struct Stack* s) {
if (isEmpty(s)) {
printf("Stack is empty. No top element.\n");
return -1; // or some error value
} else {
return s->items[s->top];
}
}
int main() {
struct Stack s;
s.top = -1; // Initialize stack
// Attempting to peek into an empty stack
printf("Top element: %d\n", peek(&s)); // Output: Stack is empty. No top element.
return 0;
}
The peek function first checks if the stack is empty using isEmpty. If it finds that the stack has no elements, it prints a message and returns -1. If there are elements in the stack, it returns the item located at the top index without modifying the stack.
Stack is empty. No top element.
Top element: -1
The isEmpty function checks whether a stack is empty. It returns 1 (true) if the stack has no elements, and 0 (false) otherwise.
int isEmpty(struct Stack* s);
Here is the program for isempty operation in c:
#include <stdio.h>
#define MAXSIZE 10
struct Stack {
int items[MAXSIZE];
int top;
};
// Function to check if the stack is empty
int isEmpty(struct Stack* s) {
return s->top == -1; // Returns 1 if empty, 0 otherwise
}
int main() {
struct Stack s;
s.top = -1; // Initialize stack
// Example usage
printf("Is stack empty? %d\n", isEmpty(&s)); // Output: 1 (true)
return 0;
}
The function checks if the top index of the stack is -1. If it is, this indicates that there are no elements in the stack, and thus it returns true (1). If there are elements, it returns false (0).
Is stack empty? 1
To visualize the current state of our queue, we can implement a function that traverses from front to rear and prints each element.
void displayQueue();
Here is the program for queue in c using linked list:
void displayQueue() {
struct Node* temp = front;
if (temp == NULL) {
printf("Queue is empty.\n");
return;
}
while (temp != NULL) {
printf("%d -> ", temp->data);
temp = temp->next;
}
printf("NULL\n");
}
20 -> 30 -> NULL
Here is the implementation of queue using linked list in c:
#include <stdio.h>
#include <stdlib.h>
struct Node {
int data; // The data stored in each node
struct Node* next; // Pointer to the next node
};
// Initialize front and rear pointers for the queue
struct Node* front = NULL; // Pointer to the front of the queue
struct Node* rear = NULL; // Pointer to the rear of the queue
// Function prototypes
void enqueue(int value);
void dequeue();
void displayQueue();
int isEmpty();
int peek();
int main() {
// Enqueue elements into the queue
enqueue(10);
enqueue(20);
enqueue(30);
printf("Current Queue: ");
displayQueue(); // Display current state of the queue
printf("Peek: %d\n", peek()); // Peek at the front element
dequeue(); // Remove an element from the queue
printf("After Dequeue: ");
displayQueue(); // Display state of the queue after dequeue
printf("Is Queue Empty? %s\n", isEmpty() ? "Yes" : "No"); // Check if queue is empty
return 0;
}
// Function to add an element to the end of the queue
void enqueue(int value) {
struct Node* newNode = (struct Node*)malloc(sizeof(struct Node)); // Allocate memory for new node
newNode->data = value; // Set the data for the new node
newNode->next = NULL; // New node will be at the end, so next is NULL
if (rear == NULL) { // Check if the queue is empty
front = rear = newNode; // If empty, both front and rear point to new node
return;
}
rear->next = newNode; // Link new node at end of queue
rear = newNode; // Update rear pointer to point to new node
}
// Function to remove an element from the front of the queue
void dequeue() {
if (front == NULL) { // Check if the queue is empty
printf("Queue is empty.\n");
return;
}
struct Node* temp = front; // Store pointer to front node
front = front->next; // Move front pointer to next node
if (front == NULL) { // If queue becomes empty after dequeue
rear = NULL; // Update rear pointer to NULL as well
}
free(temp); // Free memory of dequeued node
}
void displayQueue() {
struct Node* temp = front; // Start from the front of the queue
if (temp == NULL) { // Check if queue is empty
printf("Queue is empty.\n");
return;
}
while (temp != NULL) { // Traverse through all nodes in the queue
printf("%d -> ", temp->data); // Print current node's data
temp = temp->next; // Move to next node
}
printf("NULL\n"); // Indicate end of queue
}
int isEmpty() {
return front == NULL; // Returns 1 (true) if front is NULL, indicating an empty queue
}
// Function to peek at the front element without removing it
int peek() {
if (isEmpty()) { // Check if the queue is empty first
printf("Queue is empty. Cannot peek.\n");
return -1; // Return -1 or any sentinel value indicating failure
}
return front->data; // Return data of front node without dequeuing it
}
Current Queue: 10 -> 20 -> 30 -> NULL
Peek: 10
After Dequeue: 20 -> 30 -> NULL
Is Queue Empty? No
Time Complexity: O(1)
Space Complexity: O(n)
Here are the advantages of queue using linked list:
Here are the disadvantages of queue using linked list:
In conclusion, the linked list-based queue implementation is well-suited for applications requiring flexible data management, such as task scheduling, resource management in operating systems, and handling asynchronous data streams. Its design principles emphasize efficiency, clarity, and adaptability, making it a valuable tool in various programming scenarios.
A queue is a linear data structure that follows FIFO (First In, First Out) order.
A linked list is a data structure consisting of nodes, where each node has a data element and a pointer to the next node.
In a queue, new nodes are inserted at the rear (tail) of the linked list during enqueue.
NxtWave is an educational technology organization providing industry-recognized certifications and training programs for students and professionals in software development and data analysis.
Contact Information:
Course Offerings: