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

	#define DEFAULT_SIZE 10
	#define EMPTY -1

	typedef struct circQueue {
		int *vals;
		int capacity, numItems, front;
	} circQueue;

	// Function prototypes
	circQueue *createQueue();
	int isEmpty(circQueue *q);
	int isFull(circQueue *q);
	circQueue *resizeQueue(circQueue *q);
	int enqueue(circQueue *q, int num);
	int dequeue(circQueue *q);
	int peek(circQueue *q);
	void printQueue(circQueue *q);
	void printVal(int val);
	void printOptions();

	// Returns an initialized queue
	circQueue *createQueue() {
		circQueue *q = (circQueue *)malloc(sizeof(circQueue));
		q->vals = malloc(DEFAULT_SIZE * sizeof(int));
		q->capacity = DEFAULT_SIZE;
		q->numItems = 0;
		q->front = 0;
		return q;
	}

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

	// Return 1 if queue exists and vals array is full
	// Otherwise return 0
	int isFull(circQueue *q) { return (q && q->numItems == q->capacity) ? 1 : 0; }

	// Double the size of vals array in queue
	// Adjust contents of circular to to fit new array size
	// If queue is NULL, not full, or realloc fails, return queue without changes
	circQueue *resizeQueue(circQueue *q) {
		if (!q || !isFull(q))
			return q;

		int newCapacity = q->capacity * 2;
		int *temp = (int *)realloc(q->vals, newCapacity * sizeof(int));

		if (!temp)
			return q;

		q->vals = temp;

		for (int i = 0; i < q->front; i++)
			q->vals[i + q->capacity] = q->vals[i];

		q->capacity = newCapacity;

		return q;
	}

	// Adds integer to vals array to back of queue
	// Returns 1 if added succesfully, otherwise returns 0
	int enqueue(circQueue *q, int num) {
		if (!q)
			return 0; // Returns 0 if queue is NULL

		if (isFull(q))
			q = resizeQueue(q); // Attempts to resize vals array

		if (isFull(q))
			return 0; // Returns 0 if queue failed to resize

		q->vals[(q->front + q->numItems) % q->capacity] = num;
		q->numItems++;

		return 1;
	}

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

		int num = q->vals[q->front];
		q->front = (q->front + 1) % q->capacity;
		q->numItems--;
		return num;
	}

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

		return q->vals[q->front];
	}

	// Prints vals array to screen
	void printQueue(circQueue *q) {
		if (isEmpty(q))
			printf("Queue is empty");
		else {
			printf("(front) ");
			for (int i = 0; i < q->numItems; i++)
				printf("%d ", q->vals[(q->front + i) % q->capacity]);
			printf("(back)");
		}
		printf("\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) {
		circQueue *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
		free(q->vals);
		free(q);

		return 0;
	}