/**

 *FILENAME: listQueue.c

 *PURPOSE: Implements a simple queue data structure using C.

 *         This queue's data is stored in a linked list.

 *         Since the queue is passed to the functions as an argument,

 *         a program can have many different queues.

 *         This queue can be traversed with the traverseQueue function,

 *         however the visit function must be different for each

 *         different datatype stored in the queue.

 *DATE: 16-Apr-2005

 *PROGRAMMER: Charles Moen

 */

#include <stdio.h>

#include <stdlib.h>



typedef char Object;  /*Datatype of the elements in the queue*/



typedef struct node{  /*Nodes stored in the linked list*/

	Object element;

	struct node *next;

} Node;



typedef struct queue{ /*A struct facilitates passing a queue as an argument*/

	Node *head;       /*Pointer to the first node holding the queue's data*/

	Node *tail;       /*Pointer to the last node holding the queue's data*/

	int sz;           /*Number of nodes in the queue*/

} Queue;



int size( Queue *Q ){

	return Q->sz;

}



int isEmpty( Queue *Q ){

	if( Q->sz == 0 ) return 1;

	return 0;

}



void enqueue( Queue *Q, Object elem ){

	Node *v = (Node*)malloc(sizeof(Node));/*Allocate memory for the Node*/

	if( !v ){

		printf("ERROR: Insufficient memory\n");

		return;

	}

	v->element = elem;

	v->next = NULL;

	if( isEmpty(Q) ) Q->head = v;

	else Q->tail->next = v;

	Q->tail = v;

	Q->sz++;

}



Object dequeue( Queue *Q ){

	Node *oldHead;

	Object temp;

	if( isEmpty(Q) ){

		printf("ERROR: Queue is empty\n");

		return 0;

	}

	oldHead = Q->head;

	temp = Q->head->element;

	Q->head = Q->head->next;

	free(oldHead);

	Q->sz--;

	return temp;

}



Object first( Queue *Q ){

	if( isEmpty(Q) ){

		printf("ERROR: Queue is empty\n");

		return 0;

	}

	return Q->head->element;

}



void destroyQueue( Queue *Q ){

	while( !isEmpty(Q) ) dequeue(Q);

}



/*A different visit function must be used for each different datatype.*/

/*The name of the appropriate visit function is passed as an argument */

/*to traverseQueue.                                                   */

void visitChar( Object elem ){

	printf("%c ",elem);

}



/*The following function isn't part of the Queue ADT, however*/

/*it can be useful for debugging.                            */

void traverseQueue( Queue *Q, void (*visit)(Object elem) ){

	Node *current = Q->head;

	while( current ){

		visit(current->element);

		current = current->next;

	}

	printf("\n");

}



/*Sample code that demonstrates the queue*/

int main( int argc, char *argv[] ){

	/*Declare a queue and initialize its fields*/

	Queue Q;

	Q.head = NULL;

	Q.tail = NULL;

	Q.sz = 0;

	printf("Enqueueing three chars, abc\n");

	enqueue(&Q,'a');

	enqueue(&Q,'b');

	enqueue(&Q,'c');

	printf("Size = %d\n",size(&Q));

	printf("isEmpty = %d\n",isEmpty(&Q));

	printf("First = %c\n",first(&Q));

	printf("Traversing the queue: ");

	traverseQueue(&Q,visitChar);

	printf("Dequeueing two chars:\n");

	printf("%c",dequeue(&Q));

	printf("%c\n",dequeue(&Q));

	printf("Size = %d\n",size(&Q));

	printf("First = %c\n",first(&Q));

	printf("Dequeueing one char:\n");

	printf("%c\n",dequeue(&Q));

	printf("Size = %d\n",size(&Q));

	printf("isEmpty = %d\n",isEmpty(&Q));

	printf("Attempting to dequeue one char:\n");

	dequeue(&Q);

	/*Recover the memory to avoid memory leaks*/

	destroyQueue(&Q);

}