Queue Implementation in C Using Linked Lists

A queue is a fundamental data structure that follows the First-In-First-Out (FIFO) principle. This article presents a complete implementation of a queue using linked lists in C.

Header File - Queue.h

The header file contains function declarations and structure definitions for our queue implementation. We'll use a linked list approach where each node contains data and a pointer to the next node.

#ifndef QUEUE_H
#define QUEUE_H

#include 
#include 
#include 
#include 

// Data type for queue elements
typedef int QueueElementType;

// Structure for a queue node
typedef struct QueueNode {
    struct QueueNode* next;
    QueueElementType element;
} QueueNode;

// Structure for the queue itself
typedef struct {
    QueueNode* front;
    QueueNode* rear;
    unsigned int count;
} Queue;

// Function declarations
void InitializeQueue(Queue* q);
void DeleteQueue(Queue* q);
void Enqueue(Queue* q, QueueElementType value);
void Dequeue(Queue* q);
unsigned int GetQueueSize(Queue* q);
bool IsQueueEmpty(Queue* q);
QueueElementType GetFrontElement(Queue* q);
QueueElementType GetRearElement(Queue* q);

#endif

Implementation File - Queue.c

InitializeQueue

This function initializes a queue by setting front and rear pointers to NULL and count to 0.

void InitializeQueue(Queue* q) {
    assert(q != NULL);
    
    q->front = q->rear = NULL;
    q->count = 0;
}

DeleteQueue

This function deallocates all memory used by the queue and resets its structure.

void DeleteQueue(Queue* q) {
    assert(q != NULL);
    
    QueueNode* current = q->front;
    while (current != NULL) {
        q->front = current->next;
        free(current);
        current = NULL;
        current = q->front;
    }
    
    q->front = q->rear = NULL;
    q->count = 0;
}

IsQueueEmpty

This function checks if the queue is empty by verifying if the count is zero.

bool IsQueueEmpty(Queue* q) {
    assert(q != NULL);
    
    return q->count == 0;
}

Enqueue

This function adds an element to the rear of the queue.

void Enqueue(Queue* q, QueueElementType value) {
    QueueNode* newNode = (QueueNode*)malloc(sizeof(QueueNode));
    if (newNode == NULL) {
        perror("Memory allocation failed");
        return;
    }
    
    newNode->element = value;
    newNode->next = NULL;
    
    if (q->front == NULL) {
        // Queue is empty
        q->front = q->rear = newNode;
    } else {
        // Add to the rear
        q->rear->next = newNode;
        q->rear = newNode;
    }
    
    q->count++;
}

Dequeue

This function removes an element from the front of the queue.

void Dequeue(Queue* q) {
    assert(q != NULL);
    assert(!IsQueueEmpty(q));
    
    QueueNode* temp = q->front;
    q->front = q->front->next;
    free(temp);
    temp = NULL;
    
    if (q->front == NULL) {
        // Queue is now empty
        q->rear = NULL;
    }
    
    q->count--;
}

GetQueueSize

This function returns the number of elements in the queue.

unsigned int GetQueueSize(Queue* q) {
    assert(q != NULL);
    
    return q->count;
}

GetFrontElement

This function returns the element at the front of the queue without removing it.

QueueElementType GetFrontElement(Queue* q) {
    assert(q != NULL);
    assert(!IsQueueEmpty(q));
    
    return q->front->element;
}

GetRearElement

This function returns the element at the rear of the queue without removing it.

QueueElementType GetRearElement(Queue* q) {
    assert(q != NULL);
    assert(!IsQueueEmpty(q));
    
    return q->rear->element;
}

Test File - Test.c

This file demonstrates the usage of our queue implementation through various test cases.

#include "Queue.h"

void TestQueueOperations() {
    Queue q;
    InitializeQueue(&q);
    
    // Test enqueue operations
    Enqueue(&q, 10);
    Enqueue(&q, 20);
    Enqueue(&q, 30);
    
    printf("Queue size after enqueues: %d\n", GetQueueSize(&q));
    printf("Front element: %d\n", GetFrontElement(&q));
    printf("Rear element: %d\n", GetRearElement(&q));
    
    // Test dequeue operations
    Dequeue(&q);
    printf("Queue size after dequeue: %d\n", GetQueueSize(&q));
    printf("Front element after dequeue: %d\n", GetFrontElement(&q));
    
    // Test empty queue
    while (!IsQueueEmpty(&q)) {
        Dequeue(&q);
    }
    
    printf("Queue is empty: %s\n", IsQueueEmpty(&q) ? "true" : "false");
    
    DeleteQueue(&q);
}

int main() {
    TestQueueOperations();
    return 0;
}