/*----------------------------------------------------------------------*/
/*                           LQueue.cpp                                 */
/* Authored By : H.P.Kasmaei                                            */
/* Last Update : November 3, 2007                                       */
/* www.HPKClasses.ir                                                    */
/*----------------------------------------------------------------------*/
#include <iostream.h>
#include <stdlib.h>
#include <conio.h>


typedef int ItemType;


typedef struct Node
{
ItemType Info;
Node * Next;
};

typedef Node * NodePtr;

NodePtr Front, Rear;

int Count;

/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
/*                           ClearQueue                                 */
/* Task:   Clear out all nodes on the list except the dummy.            */
/*	   The list is thus set to an empty list.			*/
/* Given:  Nothing 							*/
/* Return: Nothing    					                */
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

void ClearQueue(void)
   {
   NodePtr Current, Temp;

   Current = Front;
   while (Current != NULL)
      {
      Temp = Current;
      Current = Current->Next;
      delete Temp;
      }

   Front = NULL;
   Rear = Front;
   Count = 0;
   }

/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
/*                           GetNode                                    */
/* Task:   To allocate a new node and place Item and NextPtr in it.     */
/* Given:  Item: A data item to place in the Info field of a new node.  */
/*	   NextPtr: The pointer to place in the Next field of the new   */
/*	   node							        */
/* Return: A pointer to the new node is returned in the function name.	*/
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

NodePtr GetNode(const ItemType & Item, NodePtr NextPtr)
   {
   NodePtr Current;

   Current = new Node;

   if (Current == NULL)
      {
      cerr << "Memory allocation error!" << endl;
      exit(1);
      }
   Current->Next = NextPtr;
   Current->Info = Item;

   return Current;
   }


/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
/*                           CreateQueue                                */
/* Task:   Create an empty list with a dummy node.			*/
/* Given:  Nothing 							*/
/* Return: Nothing    					                */
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

void CreateQueue(void)
   {
   ItemType Item;

   Front = NULL;
   Rear = Front;
   Count = 0;
   }

/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
/*                           AddQueue                                   */
/* Task:   To insert Item into a new node added to the rear of the list.*/
/* Given:  Item   A data item       				        */
/* Return: Nothing							*/
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

void AddQueue(const ItemType & Item)
   {
   NodePtr Current;

   Current = GetNode(Item, NULL);
   if (Front==NULL)
      Front=Current;
   else
      Rear->Next = Current;
   Rear = Current;
   Count++;
   }


/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/
/*                           DelQueue                                   */
/* Task:   To remove first node from the list.                          */
/* Given:  Nothing                  				        */
/* Return: Data item that removed from the list				*/
/*++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++*/

ItemType DelQueue(void)
   {
   NodePtr Current;
   ItemType Item;

   if (Count == 0)
      {
      cerr << "ERROR: there is no item to remove in the list!" << endl;
      exit(1);
      }

   Current = Front;
   Item = Current->Info;
   Front = Current->Next;
   Count--;

   if (Count == 0)
      Rear = Front;

   delete Current;
   return Item;
   }


/*----------------------------------------------------------------------*/
/*                              M A I N                                 */
/*----------------------------------------------------------------------*/

void main ()
{

   ItemType Item;
   NodePtr p;

   clrscr();

   CreateQueue();

   AddQueue(25);
   AddQueue(30);


   Item = DelQueue();
   cout<< Item<< " was removed from list" << endl;


   ClearQueue();
}