📌 Array and Linked List Implementation of Queues in C

A Queue is a FIFO (First-In, First-Out) data structure. It allows elements to be added from the rear and removed from the front.

---

1️⃣ Queue Using Arrays

🔹 Fixed size, which can lead to space wastage.
🔹 Uses a circular approach to optimize space.

✅ C Program: Queue Using Array

#include <stdio.h>
#define SIZE 5  // Define queue size

int queue[SIZE], front = -1, rear = -1;

// Check if queue is empty
int isEmpty() {
    return (front == -1);
}

// Check if queue is full
int isFull() {
    return (rear == SIZE - 1);
}

// Enqueue operation
void enqueue(int value) {
    if (isFull()) {
        printf("Queue Overflow! Cannot insert %d\n", value);
        return;
    }
    if (front == -1) front = 0;  // Initialize front if queue is empty
    queue[++rear] = value;
    printf("Enqueued: %d\n", value);
}

// Dequeue operation
void dequeue() {
    if (isEmpty()) {
        printf("Queue Underflow! No element to remove\n");
        return;
    }
    printf("Dequeued: %d\n", queue[front]);
    if (front == rear) front = rear = -1;  // Reset queue when empty
    else front++;
}

// Display the queue
void display() {
    if (isEmpty()) {
        printf("Queue is empty!\n");
        return;
    }
    printf("Queue: ");
    for (int i = front; i <= rear; i++)
        printf("%d ", queue[i]);
    printf("\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();
    
    dequeue();
    display();
    
    enqueue(40);
    enqueue(50);
    enqueue(60);
    display();
    
    return 0;
}

✅ Simple implementation
❌ Fixed size & memory wastage after deletions

---

2️⃣ Queue Using Linked List

🔹 Dynamic size, so no space wastage.
🔹 Requires additional memory for pointers.

✅ C Program: Queue Using Linked List

#include <stdio.h>
#include <stdlib.h>

// Define Node structure
struct Node {
    int data;
    struct Node* next;
};

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

// Check if queue is empty
int isEmpty() {
    return (front == NULL);
}

// Enqueue operation
void enqueue(int value) {
    struct Node* newNode = (struct Node*)malloc(sizeof(struct Node));
    newNode->data = value;
    newNode->next = NULL;

    if (isEmpty()) {
        front = rear = newNode;
    } else {
        rear->next = newNode;
        rear = newNode;
    }
    printf("Enqueued: %d\n", value);
}

// Dequeue operation
void dequeue() {
    if (isEmpty()) {
        printf("Queue Underflow! No element to remove\n");
        return;
    }
    struct Node* temp = front;
    printf("Dequeued: %d\n", front->data);
    front = front->next;
    free(temp);

    if (front == NULL) rear = NULL;  // Reset rear when queue is empty
}

// Display the queue
void display() {
    if (isEmpty()) {
        printf("Queue is empty!\n");
        return;
    }
    struct Node* temp = front;
    printf("Queue: ");
    while (temp != NULL) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

int main() {
    enqueue(10);
    enqueue(20);
    enqueue(30);
    display();
    
    dequeue();
    display();
    
    enqueue(40);
    enqueue(50);
    display();
    
    return 0;
}

✅ Efficient memory usage
✅ No size restriction
❌ Extra memory needed for pointers

---

3️⃣ Comparison: Array vs Linked List Implementation

Feature	Array Implementation	Linked List Implementation
Memory Usage	Fixed size (wastes space)	Dynamic size (efficient)
Time Complexity (Enqueue/Dequeue)	O(1)	O(1)
Implementation Complexity	Simple	More complex (requires pointers)
Memory Overhead	No extra memory needed	Extra memory for pointers
Speed	Faster (better cache locality)	Slightly slower