// inserting aand deleting nodes in a quene

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

struct queneNode {
	char data; // define data as a char
	struct queneNode* nextPtr; // queneNode pointer
};

typedef struct queneNode QueneNode;
typedef QueneNode* QueneNodePtr;

void instructions();
void enquene(QueneNodePtr* headPtr, QueneNodePtr* tailPtr, char value);
int dequene(QueneNodePtr* headPtr, QueneNodePtr* tailPtr);
void printQuene(QueneNodePtr currentPtr);
int isEmpty(QueneNodePtr headPtr);

int main()
{
	QueneNodePtr headPtr = NULL; // points to quene head
	QueneNodePtr tailPtr = NULL; // points to quene tail
	int choice; // user's menu choice
	int item; // char input by user

	instructions(); // display the menu
	scanf_s("%d", &choice);

	// while user does not enter 3
	while (choice != 3)
	{
		switch (choice)
		{
		case 1: // push value onto stack
			printf("Enter a cahractor : ");
			scanf_s("\n%c", &item);
			enquene(&headPtr, &tailPtr, item);
			printQuene(headPtr);
			break;

		case 2: // pop value off stack
			if (!isEmpty(headPtr))
			{
				item = dequene(&headPtr, &tailPtr);
				printf("%c has been dequened\n", item);
			}
			printQuene(headPtr);
			break;

		default:
			printf("Invalid choice\n");
			break;
		}
		printf("\n");
		instructions(); // display the menu
		scanf_s("%d", &choice);
	}
	printf("End of run\n");
	return 0;
}

// display program instructions to user
void instructions()
{
	printf("1 to add an item to the quene\n");
	printf("2 to remove an item from the quene\n");
	printf("3 to end program\n");
	printf("Enter choice : ");
} // end function instructions

// insert a node in at quene tail
void enquene(QueneNodePtr* headPtr, QueneNodePtr* tailPtr, char value)
{
	QueneNodePtr newPtr; // pointer to new node

	newPtr = malloc(sizeof(QueneNode));

	if (newPtr != NULL) // is space avaliable
	{
		newPtr->data = value;
		newPtr->nextPtr = NULL;

		// if empty , insert node at head
		if (isEmpty(*headPtr))
		{
			*headPtr = newPtr;
		}
		else
		{
			(*tailPtr)->nextPtr = newPtr;
		}
		*tailPtr = newPtr;
	}
	else
	{
		printf("%c not inserted. No memory avaliable.\n", value);
	}
} // end function enquene

// remove a node from quene head
int dequene(QueneNodePtr* headPtr, QueneNodePtr* tailPtr)
{
	char value; // node value
	QueneNodePtr tempPtr; // temporary node pointer

	value = (*headPtr)->data;
	tempPtr = *headPtr;
	*headPtr = (*headPtr)->nextPtr;

	// if quene is empty
	if (*headPtr == NULL)
	{
		tailPtr == NULL;
	}

	free(tempPtr);
	return value;
} // end function dequene

void printQuene(QueneNodePtr currentPtr)
{
	// if quene is empty
	if (currentPtr == NULL)
	{
		printf("The quene is empty\n");
	}
	else
	{
		printf("The quene is : ");

		// while not the end of the stack
		while (currentPtr != NULL)
		{
			printf("%c --> ", currentPtr->data);
			currentPtr = currentPtr->nextPtr;
		}
		printf("NULL\n");
	}
} // end function printQuene

// Return 1 if stack is empty
// Return 0 if not empty
int isEmpty(QueneNodePtr headPtr)
{
	return headPtr == NULL;
} // end function isEmpty