Queue Using Linked List in C: Implementation of Each Operations

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.

Pointer 

A variable that holds the memory address of another variable. It allows indirect access to the value stored at that address.

Node 

A basic unit of data structure, typically containing:

• Data: The value the node stores.
• Pointer(s): References to other nodes (e.g., in linked lists or trees).

Node Structure

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

Drawbacks of using an Array as Queue

Here are some disadvantages of using an array as a queue:  

• The queue size is static, so there may be overflow if it’s full or wasted or unused slots are present.
• Removing elements from the front means that every other element must be shifted, which gives rise to an O(n) time complexity. 
• In a non-circular array, space at the front is wasted once elements are dequeued.
• It’s very easy for an array implementation of a queue to overflow (when full) or underflow (when empty).

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:

• Front: This points to the first element in the queue.
• Rear: This points to the last element in the queue.

Initially, both pointers are set to NULL, indicating an empty queue:

Representation

struct Node* front = NULL;
struct Node* rear = NULL;

The main operations performed on a linked list queue include:

1. Enqueue Operation

The enqueue operation adds an element to the rear of the queue

Syntax

void enqueue(int value);

Algorithm

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

2. Set the new node's data.

3. If the queue is empty (both front and rear are NULL):

• Set both front and rear pointers to point to this new node.

4. If not empty:

• Set the current rear's next pointer to point to the new node.
• Update the rear pointer to reference the newly added node.

Example

Suppose we want to enqueue values 10, 20, and 30 into an initially empty queue.

C Code for Enqueue Operation

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
}

Code Explanation

• In the above program, malloc allocates memory for a new node.
• The data field of the new node is set to the provided value.
• If rear is NULL, it means the queue is empty. Both front and rear are set to point to the new node.
• If the queue is not empty, the current rear's next pointer is updated to point to the new node, and then rear is updated to point to this new node.

Output

Front -> [10] -> [20] -> [30] -> NULL

2. Dequeue Operation

The dequeue operation eliminates an item from the front of the queue..

Syntax

void dequeue();

Algorithm

1. Check if the queue is empty by verifying if the front pointer is NULL.

If it is NULL, print an underflow message.

2. If not empty, store a temporary pointer to the front node.

3. Move the front pointer to its next node.

4. Free memory allocated for the dequeued node.

Example:

After enqueuing values (10, 20, and 30), if we perform a dequeue operation, we remove 10.

C Code Example for Dequeue

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
}

Code Explanation

• If front is NULL, it indicates that the queue is empty, and a message is printed.
• A temporary pointer temp stores the current front node so that we can free its memory later.
• The front pointer is moved to the next node in the queue.
• If the front becomes NULL, it means the queue is now empty, so we also set rear to NULL.
• Finally, we free the memory allocated for the dequeued node.

Output:

Front -> [20] -> [30] -> NULL

3. Peek Operation

Returns the front element present in the queue without removing it.

Syntax

int peek(struct Stack* s);

Algorithm

1. Check if the stack is empty by calling isEmpty.

2. If it is empty, return an error value (like -1).

3. If not, return the element at the index top

C Code Example for Peek 

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

Code Explanation

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.

Output

Stack is empty. No top element.
Top element: -1

4. IsEmpty Operation

The isEmpty function checks whether a stack is empty. It returns 1 (true) if the stack has no elements, and 0 (false) otherwise.

Syntax

int isEmpty(struct Stack* s);

Algorithm

1. Check if the top index of the stack is -1.

2. If it is, return true (1).

3. Otherwise, return false (0).

C Code Example for isEmpty

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

Code Explanation

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).

Output

Is stack empty? 1

5. Displaying the Queue Operation

To visualize the current state of our queue, we can implement a function that traverses from front to rear and prints each element.

Syntax

void displayQueue();

Algorithm

1. Start from the front pointer and traverse through each node until reaching NULL.

2. Print each node's data.

C Code Example for Displaying Queue

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");
}

Code Explanation

• A temporary pointer temp starts at the front of the queue.
• If temp is NULL, it indicates that the queue is empty, and a message is printed.
• A while loop traverses through each node in the queue. For each node, it prints its data followed by an arrow (->) until it reaches the end of the list (when temp becomes NULL).
• After exiting the loop, it prints "NULL" to indicate that there are no more elements in the queue.

Output

20 -> 30 -> NULL

Here is the implementation of queue using linked list in c:

Code

#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
}

Code Explanation

• Defines a Node structure with data and next, initializing front and rear to NULL.
• The enqueue adds a node to the rear; if empty, both front and rear point to it.
• The operation dequeue removes the front node and updates front; if empty, sets rear to NULL.
• The displayQueue prints all node data or "Queue is empty" if empty.
• The operation isEmpty checks if the queue is empty, and peek returns the front element’s data or -1 if empty.

Output

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 such as:

• It contains dynamic memory allocation that allows the queue to grow or shrink without predefined size limits.
• Enqueue and dequeue operations run in constant time, O(1), enhancing performance.
• It can handle an indefinite number of elements based on available memory.
• Adding or removing nodes is easy without shifting elements.

Here are the disadvantages of queue using linked list such as:

• Each node requires extra memory for pointers, increasing overall usage.
• Poor cache performance due to non-contiguous memory allocation can slow access.
• More complex to implement due to pointer management and memory handling.
• Improper deallocation of nodes can lead to wasted memory over time.
• Searching for elements may require linear time, O(n), affecting efficiency.

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.

1. What is a Queue and Linked List in Data Structures?

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.

2. Where is a New Node Typically Inserted in a Linked List When Implementing a Queue Using a Singly Linked List?

In a queue, new nodes are inserted at the rear (tail) of the linked list during enqueue.

3. How to Implement Queue Using a Linked List?

• Use two pointers: front (points to the first node) and rear (points to the last node).
• For enqueue: Add a node to the rear.
• For dequeue: Remove a node from the front.

4. Why is Linked List Better Than Array for Implementing a Queue?

• Linked lists provide dynamic memory allocation, so no fixed size is needed, avoiding overflow problems.
• Arrays require resizing or shifting elements, which can be inefficient for large queues.