#include <stdio.h>

typedef enum {FALSE, TRUE} bool;

/* DECLARATION FOR QUEUE */

typedef char queueElt;

typedef struct queueNode* queueNodePtr;
typedef struct queueNode {
	queueElt      elt;
	queueNodePtr next;
} queueNode;

queueNodePtr newQueueNode(queueElt e); // auxiliary function
queueNodePtr newQueueNode(queueElt e) {
	queueNodePtr p = (queueNodePtr)malloc(sizeof(queueNode));
	p->elt = e;
	p->next = p; // a cyclic node!
	return(p);
}

typedef struct queueHeader {
	queueNodePtr rear;
	int         size;
} queueHeader;
typedef queueHeader* queue;


/* FUNCTION PROTOTYPES AND DOCUMENTATION FOR QUEUE */ file queue.h

queue createQueue();             // create a new empty queue

bool isEmptyQueue(queue q);      // check whether queue q is empty or not
bool isFullQueue (queue q);      // check whether queue q is full or not
int  sizeOfQueue (queue q);

queue insert(queueElt e, queue q);  // add element e to non-full queue q
queue serve(queue q);               // remove front element from non-empty queue
queueElt front(queue q);            // get front element of non-empty queue
queueElt rear(queue q);             // get rear element of non-empty queue

void showQueueFrontToRear(queue q);

/* DEFINITION OF THE QUEUE FUNCTIONS */ file queue.c

queue createQueue() {
	queue q = (queue)malloc(sizeof(queueHeader));
	q->rear = NULL;
	q->size = 0;
	return(q);
}

bool isEmptyQueue(queue q) {return(q->size == 0);}
bool isFullQueue (queue q) {return(FALSE);}
int  sizeOfQueue (queue q) {return(q->size);}

queue insert(queueElt e, queue q) {
	queueNodePtr p = newQueueNode(e);
	if (q->size) {
		p->next = q->rear->next;
		q->rear->next = p; 
	}
	q->rear = p;
	q->size++; 
	return(q);
}
queue serve(queue q) {                   // q is not empty
	queueNodePtr front = q->rear->next;
	q->rear->next = front->next;
	free(front);
	q->size--;
	if (q->size == 0)
		q->rear = NULL;
	return(q);
}

queueElt front(queue q) {               // q is not empty
	return(q->rear->next->elt);
}
queueElt rear(queue q) {                // q is not empty
	return(q->rear->elt);
}

void showQueueFrontToRear(queue q) {    // q is not empty
	queueNodePtr front = q->rear->next;
	do {
		printf("%2c", front->elt);
		front = front->next;
	} while (front != q->rear->next);
}