The array-based queue implementation introduced in class uses a fixed length array. As a result, it is possible for the queue to become full.

1. Rewrite the \(\texttt{enqueue}\) method so that it doubles the length of the array when the array is full.
2. Rewrite the \(\texttt{dequeue}\) method so that it halves the length of the array when the array is less than half full.

**************************************************
**************************************************
**						**
**	SOLUTION PROVIDED BY ABBAS KHREISS	**
**						**
**************************************************
**************************************************




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

typedef int element;
typedef struct
{
	element * data;
	int front, length,maxSize;
} queue;

queue createQueue()
{
	queue q;
	q.length = 0;
	q.front = 0;
	q.maxSize = 1;
	q.data = (element *)malloc(sizeof(element));
	return q;
}
int isEmptyQueue(queue q)
{
	return q.length == 0;
}
int Front(queue q, element * e)
{
	if (isEmptyQueue(q)) return 0;
	*e = q.data[q.front];
	return 1;
}
int EnQueue(queue * q, element e)
{
	element * tmp;
	int i;
	if (q->maxSize == q->length)
	{
		tmp= (element *)realloc(q->data, sizeof(element) * 2 * q->maxSize);
		if (tmp)
			q->data = tmp;
		else return 0;
		for (int i = 0; i < q->length; i++)
			q->data[q->maxSize + i] = q->data[(q->front + i) % q->maxSize];
		q->front = q->maxSize ;
		q->maxSize *= 2;
	}
	q->data[(q->front + q->length) % q->maxSize] = e;
	++q->length;
	return 1;
}
int DeQueue(queue * q)
{
	element *tmp;
	int i;
	if (isEmptyQueue(*q))
		return 0;
	if (q->length == 1)
	{
		q->length = 0;
		return 1;
	}
	q->front = (q->front + 1) % q->maxSize;
	--q->length;
	if (q->length == q->maxSize / 2)
	{
		tmp = (element *)malloc(sizeof(element) * q->maxSize / 2);
		if (!tmp)
			return 0;
		for (int i = 0; i < q->length; i++)
			tmp[i] = q->data[(q->front + i) % q->maxSize];
		free(q->data);
		q->data = tmp;
		q->maxSize /= 2;
		q->front = 0;
	}
	return 1;
}

void displayQueue(queue q)
{
	element e;
	if (isEmptyQueue(q))
		printf("Queue is Empty\n");
	else printf("<----- ");
	while (Front(q, &e))
	{
		DeQueue(&q);
		printf("%d\t", e);
	}
	printf("\n\n", e);
}

queue copyQueue(queue q)
{
	queue q1 = q;
	element * tmp = (element *)malloc(sizeof(element)*q.maxSize);
	for (int i = 0; i < q.maxSize; i++)
		tmp[i] = q.data[i];
	q1.data = tmp;
	return q1;

}

int main()
{
	element e;
	queue q = createQueue();
	displayQueue(q);
	for (int i = 0; i <10; i++)
	{
		EnQueue(&q, i); 
		displayQueue(copyQueue(q));
	}

	printf("-------------------------------------------------------------------------------------\n");

	while (Front(q, &e))
	{
		DeQueue(&q);
		displayQueue(copyQueue(q));
	}
 
	return 0;
}