Extra Lab Solution

static struct node *newNode(Item it);

/**
 * Adds an item to the end of the queue
 */
void QueueEnqueue(Queue q, Item it) {
	struct node *n = newNode(it);
	if (q->size == 0) {
		q->head = n;
	} else {
		q->tail->next = n;
	}
	q->tail = n;
	q->size++;
}

static struct node *newNode(Item it) {
	struct 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;
}

/**
 * Removes an item from the front of the queue and returns it
 * Assumes that the queue is not empty
 */
Item QueueDequeue(Queue q) {
	assert(q->size > 0);
	
	struct node *newHead = q->head->next;
	Item it = q->head->item;
	free(q->head);
	q->head = newHead;
	if (newHead == NULL) {
		q->tail = NULL;
	}
	q->size--;
	return it;
}

static void increaseCapacity(Queue q);

/**
 * Adds an item to the end of the queue
 */
void QueueEnqueue(Queue q, Item it) {
	if (q->size == q->capacity) {
		increaseCapacity(q);
	}
	
	q->items[(q->frontIndex + q->size) % q->capacity] = it;
	q->size++;
}

/**
 * Doubles the capacity of the queue
 * NOTE: Assumes the queue is full when this is called
 */
static void increaseCapacity(Queue q) {
	q->items = realloc(q->items, 2 * q->capacity * sizeof(Item));
	if (q->items == NULL) {
		fprintf(stderr, "couldn't resize Queue\n");
		exit(EXIT_FAILURE);
	}

	// Fix the arrangement of the items	
	// Since the array is doubled in size, this will never overflow
	for (int i = 0; i < q->frontIndex; i++) {
		q->items[q->capacity + i] = q->items[i];
	}
	q->capacity *= 2;
}

/**
 * Removes an item from the front of the queue and returns it
 * Assumes that the queue is not empty
 */
Item QueueDequeue(Queue q) {
	assert(q->size > 0);
	
	Item it = q->items[q->frontIndex];
	q->frontIndex = (q->frontIndex + 1) % q->capacity;
	q->size--;
	return it;
}