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

	#define EMPTY -1

	typedef struct node {
		int data;
		struct node *next;
	} node;

	typedef struct queue {
		int size;
		struct node *head, *tail;
	} queue;

	// Function prototypes
	queue *createQueue();
	node *createNode(int num);
	int isEmpty(queue *q);
	int enqueue(queue *q, int num);
	int dequeue(queue *q);
	int peek(queue *q);
	void printQueue(queue *q);
	void printVal(int val);
	void printOptions();

	// Return an instantiated queue *
	queue *createQueue() {
		queue *q = (queue *)malloc(sizeof(queue));
		q->size = 0;
		q->head = NULL;
		q->tail = NULL;
		return q;
	}

	// Return an instantiated node *
	node *createNode(int num) {
		node *n = (node *)malloc(sizeof(node));
		n->data = num;
		n->next = NULL;
		return n;
	}

	// Return 1 if queue exists and queue is empty
	// Otherwise return 0
	int isEmpty(queue *q) { return (!q || q->size == 0) ? 1 : 0; }

	// Adds integer to queue to tail of queue
	// Returns 1 if added succesfully, otherwise returns 0
	int enqueue(queue *q, int num) {
		if (!q)
			return 0;

		node *n = createNode(num);

		if (q->size == 0) {
			q->head = n;
			q->tail = n;
		} else {
			q->tail->next = n;
			q->tail = n;
		}
		q->size++;
		return 1;
	}

	// Removes and returns integer from front of queue
	// If queue is empty, returns EMPTY
	int dequeue(queue *q) {
		if (isEmpty(q))
			return EMPTY;

		int data = q->head->data;
		node *tmp = q->head;

		if (q->size == 1) {
			q->tail = NULL;
			q->head = NULL;
		} else {
			q->head = q->head->next;
		}

		free(tmp);
		q->size--;
		return data;
	}

	// Returns - WITHOUT removing - integer from front of queue
	// If queue is empty, returns EMPTY
	int peek(queue *q) {
		if (isEmpty(q))
			return EMPTY;

		return q->head->data;
	}

	// Prints queue to screen
	void printQueue(queue *q) {
		if (isEmpty(q)) {
			printf("Queue is empty\n");
			return;
		}
		printf("(front) ");
		node *walker = q->head;
		while (walker) {
			printf("%d ", walker->data);
			walker = walker->next;
		}
		printf("(back)\n");
	}

	// Print value of integer
	void printVal(int val) {
		if (val == EMPTY) {
			printf("EMPTY\n");
		} else {
			printf("%d\n", val);
		}
	}

	// Print options menu
	void printOptions() {
		printf("1) Enqueue\n");
		printf("2) Dequeue\n");
		printf("3) Peek\n");
		printf("4) Print Queue\n");
		printf("5) Quit\n");
		printf("\n:");
	}

	int main(void) {
		queue *q = createQueue();

		int choice = 0;
		int num;

		while (choice != 5) {
			printOptions();
			scanf("%d", &choice);

			switch (choice) {

			case 1: // Enqueue
				printf("Type a positive integer to add to queue:\n");
				scanf("%d", &num);
				if (enqueue(q, num))
					printf("%d added to queue\n", num);
				else
					printf("Failed to add %d to queue\n", num);
				break;

			case 2: // Dequeue
				num = dequeue(q);
				printf("Dequeued: ");
				printVal(num);
				break;

			case 3: // Peek
				num = peek(q);
				printf("Peeked: ");
				printVal(num);
				break;

			case 4: // Print Queue
				printQueue(q);
				break;

			default:
				break;
			}
			printf("\n");
		}

		// Free Memory
		while (!isEmpty(q))
			dequeue(q);
		free(q);

		return 0;
	}