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 enqueue method so that it doubles the length of the array when the array is full.
  2. Rewrite the dequeue method so that it halves the length of the array when the array is less than half full.
Difficulty level
This exercise is mostly suitable for students 
**************************************************
**************************************************
**						**
**	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;
}
Back to the list of exercises
Looking for a more challenging exercise, try this one !!
UVA 1112 - Mice and Maze