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

// Define a node
typedef struct Node {
    int data;
    struct Node* next;
} Node;

// Define a Queue structure
typedef struct Queue {
    Node* front;  // points to first node
    Node* rear;   // points to last node
} Queue;

// Function to initialize queue
void initQueue(Queue* q) {
    q->front = q->rear = NULL;
}

// Function to create a new node
Node* createNode(int data) {
    Node* newNode = (Node*)malloc(sizeof(Node));
    if (!newNode) {
        printf("Memory allocation failed!\n");
        exit(1);
    }
    newNode->data = data;
    newNode->next = NULL;
    return newNode;
}

// Check if queue is empty
bool isEmpty(Queue* q) {
    return q->front == NULL;
}

// Enqueue (insert element at the end)
void enqueue(Queue* q, int data) {
    Node* newNode = createNode(data);
    if (q->rear == NULL) {
        q->front = q->rear = newNode;
    } else {
        q->rear->next = newNode;
        q->rear = newNode;
    }
    printf("Enqueued %d\n", data);
}

// Dequeue (remove element from front)
int dequeue(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue Underflow! Cannot dequeue.\n");
        return -1;
    }

    Node* temp = q->front;
    int value = temp->data;

    q->front = q->front->next;
    if (q->front == NULL)
        q->rear = NULL;  // queue becomes empty

    free(temp);
    printf("Dequeued %d\n", value);
    return value;
}

// Peek (view front element)
int peek(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return -1;
    }
    return q->front->data;
}

// Display the queue
void display(Queue* q) {
    if (isEmpty(q)) {
        printf("Queue is empty.\n");
        return;
    }

    printf("Queue (front → rear): ");
    Node* temp = q->front;
    while (temp) {
        printf("%d ", temp->data);
        temp = temp->next;
    }
    printf("\n");
}

// Free all nodes in the queue
void clearQueue(Queue* q) {
    Node* temp = q->front;
    while (temp) {
        Node* next = temp->next;
        free(temp);
        temp = next;
    }
    q->front = q->rear = NULL;
}

// Main function for demonstration
int main() {
    Queue q;
    initQueue(&q);

    enqueue(&q, 10);
    enqueue(&q, 20);
    enqueue(&q, 30);

    display(&q);
    printf("Front element: %d\n", peek(&q));

    dequeue(&q);
    display(&q);

    dequeue(&q);
    dequeue(&q);
    dequeue(&q); // underflow case

    clearQueue(&q);
    return 0;
}