// Program to demonstrate a queue using nodePtrs
// The size of the queue is limited only by the
// amount of dynamic RAM available

#include <iostream.h>
#include <stdlib.h>


struct node;
typedef node *nodePtr;

struct node
{
	char data;
	nodePtr next;
};

struct queue
{
	nodePtr front;
	nodePtr rear;
};


void create(queue&);
bool empty(queue);
bool full();
void addToQueue(queue&, char);
void deleteFromQueue(queue&, char&);
void traverseQueue(queue);


void create(queue& Q)
{
	Q.front = NULL;
	Q.rear = NULL;
}


bool empty(queue Q)
{
	if(Q.front == NULL)
		return true;
	else
		return false;
}

bool full()
{
	nodePtr temp =new node;

	if (temp == NULL)
		return true;
	else
	{
		delete temp;
		return false;
	}
}

void addToQueue(queue& Q, char item)
{
		nodePtr temp;

		temp = new node;
		temp->data = item;
		temp->next = NULL;

		if (Q.front != NULL) // ie not empty
		{
			Q.rear->next = temp;
			Q.rear = temp;
		}
		else
		{
			Q.front = temp;
			Q.rear = temp;
		}
}

void deleteFromQueue(queue& Q, char& item)
{
	nodePtr temp;

	if (Q.front != NULL)      // ie not empty
	{
		temp = Q.front;
		item = temp->data;

		if (Q.rear == Q.front) // ie single node so queue becomes empty
		{
			Q.front = NULL;
			Q.rear = NULL;
		}
		else                  // more than one node
			Q.front = temp->next;

   	delete temp;
	}
}

void traverseQueue(queue Q)
{
	nodePtr temp;

	temp = Q.front;

	while (temp != NULL)
		{
		cout << temp->data << endl;
		temp =  temp->next;
		}
}

void main()
{
	queue q;
	char command, letter;

	create(q);
	system("cls");

	cout << "This program uses a queue implemented using pointers\n";
	cout << "The number of items in the queue is only limited by\n";
	cout << "amount of dynamic RAM available\n";

	do
	{
		cout << "\n[A]dd to queue, [D]elete from queue, [P]rint queue, "  ;
		cout << "or [Q]uit -> ";
		cin >> command;
		switch(command)
		{
			case 'a' :
			case 'A' :  cout << "Enter data -> ";
						cin >> letter;
						addToQueue(q, letter);
						break;
			case 'd' :
			case 'D' :  if (!empty(q))
						{
							deleteFromQueue(q, letter);
							cout << letter << " removed from queue\n";
						}
						else
							cout << "The queue is empty \n";
						break;
			case 'p' :
			case 'P' :  traverseQueue(q);
						break;
			case 'q' :
			case 'Q' : 	cout << "Program terminated\n";
						break;
			default  :	cout << "Unknown command [" << command << "] try again!\n";
			}	// end switch
	 } while (!(command == 'q' || command == 'Q'));
}