// Implementation of the Queue ADT using a linked list

// !!! DO NOT MODIFY THIS FILE !!!

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

#include "Queue.h"

typedef struct node *Node;
struct node {
    char *item;
    Node next;
};

struct queue {
    Node head;
    Node tail;
    int size;
};

static Node newNode(char *it);

Queue QueueNew(void) {
    Queue q = malloc(sizeof(*q));
    if (q == NULL) {
        fprintf(stderr, "error: out of memory\n");
        exit(EXIT_FAILURE);
    }

    q->head = NULL;
    q->tail = NULL;
    q->size = 0;
    return q;
}

void QueueFree(Queue q) {
    Node curr = q->head;
    while (curr != NULL) {
        Node temp = curr;
        curr = curr->next;
        free(temp);
    }
    free(q);
}

void QueueEnqueue(Queue q, char *it) {
    Node n = newNode(it);
    if (q->size == 0) {
        q->head = n;
    } else {
        q->tail->next = n;
    }
    q->tail = n;
    q->size++;
}

static Node newNode(char *it) {
    Node n = malloc(sizeof(*n));
    if (n == NULL) {
        fprintf(stderr, "error: out of memory\n");
        exit(EXIT_FAILURE);
    }

    n->item = it;
    n->next = NULL;
    return n;
}

char *QueueDequeue(Queue q) {
    if (q->size == 0) {
        fprintf(stderr, "error: queue is empty\n");
        exit(EXIT_FAILURE);
    }

    Node newHead = q->head->next;
    char *it = q->head->item;
    free(q->head);
    q->head = newHead;
    if (newHead == NULL) {
        q->tail = NULL;
    }
    q->size--;
    return it;
}

char *QueueFront(Queue q) {
    if (q->size == 0) {
        fprintf(stderr, "error: queue is empty\n");
        exit(EXIT_FAILURE);
    }

    return q->head->item;
}

int QueueSize(Queue q) {
    return q->size;
}

bool QueueIsEmpty(Queue q) {
    return q->size == 0;
}

void QueueShow(Queue q) {
    for (Node curr = q->head; curr != NULL; curr = curr->next) {
        printf("%s ", curr->item);
    }
    printf("\n");
}