//Syed Rais Ahmad
//Assignment # 5 Quest 2
//Empty,insert remove of dyna queu

#include<iostream.h>

//A node in a queue
class llistItem
{
public:
	int item;
	llistItem * nxtItem;
};


//Queue
class Queue
{
private:
	llistItem *rear;
public:
	Queue(); 
	~Queue() {delete rear;}; 

	bool Insert(int);
	int Remove();
	bool Empty();
};


//create rear and put NULL values in it.
Queue::Queue()
{
	rear = new llistItem;
	rear->nxtItem=NULL;//Empty Queue
}



//Return an item is on stack Top. -1 if stack is empty
int Queue::Remove()
{
	
	if (!Empty())
	{
		llistItem * front,* temp;
		int i=0;
//front gets the address of next node from rear		
		front=rear->nxtItem->nxtItem;
//if only one node is remaining then front = rear;
		if (front==rear->nxtItem) 
		{
			i=front->item; 
			delete front;
			rear->nxtItem=NULL; //empty the Queue
			return i;
		}
//temp gets the about-to-be front node's address.
		temp=front->nxtItem;
		i=front->item;
//rear node now points to a new front node.
		rear->nxtItem->nxtItem=temp;
		delete front;
		return i;
		
	}
	return -1;
}



//Insert an int to a Queue
bool Queue::Insert(int insInt)
{
	llistItem * ptr,*temp;
//insert will always need new node with new integer value in it.		
	ptr=new llistItem;
	ptr->item=insInt;

	if (Empty())
	{
//node points to itself
		ptr->nxtItem=ptr;
		rear->nxtItem=ptr;
		
	}
	else
	{
//temp holds value for node next to rear node.
		temp=rear->nxtItem->nxtItem;
//rear is now the new node, just inserted.
		rear->nxtItem->nxtItem=ptr;
		ptr->nxtItem=temp;
//rear points to a newly inserted node.
		rear->nxtItem=ptr;
	}
		return true;
}

//is Queue Empty
bool Queue::Empty()
{
	return (rear->nxtItem==NULL)? true : false;
}


//------- Program's main flow starts ---------------------------

main()
{
	Queue q;int i=0;
	
	q.Insert(3);
	q.Insert(5);
	q.Insert(8);
	cout << "\nInserted 3,5,8 to a Q\n";
	cout << "\n1st Remove returns: " << q.Remove();
	cout << "\n2nd Remove returns: " << q.Remove();
	cout << "\n3rd Remove returns: " << q.Remove();
	cout << "\n4th Remove returns: " << q.Remove() << '\n';

	return 0;

}