// making a linked list
#include<iostream.h>
#include<stdio.h>
#include<conio.h>
extern "C" int exit(int st);
class dblink {                    // Decleration of the linked list.
int a;
dblink *next;
public:
void   List(void);                // Makes a new empty linked list.
int    Size(void);                // Returns the size of the list.
int    Delete(int value);         // Deletes a given value (if exists).
int    ldelete(int pos);          // Deletes element at position specified.
void   Print_List();              // Prints an entire linked list.
void   make_null();               // Makes the list empty.
int    Find_Kth(int pos);         // Returns the value at position specified.
int    Find(int value);           // Returns 1st position of element .
void   Insert(int value,int x );  // Inserts a value after a specified pos.
} *list;
		/* End of the body of the class */
//----------------------------------------------------
		/* BUILDING OF THE FUNCTIONS */
//----------------------------------------------------
void dblink::List(void)
{
list=new dblink;
list->a=0;
list->next=NULL;
}
		/*   End of procedure   */
//---------------------------
int dblink::Size(void)
{
  dblink *last;
  int i;
  i=0;
  last=list;
  if (last->next==NULL) return 0;
  while (last->next !=NULL) {i++;last=last->next;};
  return i;
}
		/* End of procedure  */
//-----------------------------
int dblink::Delete(int value)
{
 dblink *extra,*last;
 last=list;
 if (list->next->a==value)
	{delete(list);return 1;}
	last=list;
	while ((last->next->a !=value) && (last->next !=NULL))
		last=last->next;
		if (last->next->a==value)
		   {
			extra=last->next;
			last->next=extra->next;
			delete(extra);
			return 1;
		   }
		if ((last->next==NULL)&&(last->a !=value))  return 0;
		return 0;

}
//-----------------------------
int dblink::ldelete(int pos)
{
 int i,k;
 dblink *extra,*last;
 last=list;
 k=Size();
	   if (pos<=k)
	   {  for (i=1;i<pos;i++) last=last->next;
	      extra=last->next;
	      last->next=extra->next;
	      delete extra;
	      return 1;
	   }
	   else return 0;
 }
 //----------------------------------------

void dblink::Print_List()
{dblink *last;
 last=list->next;
 if (last==NULL) cout<<"  list is empty\n";
 else

   { while      (last !=NULL)
		{cout<<"\n"<< last->a<<"\n";last=last->next;};

   }
}
//-----------------------------------------
void dblink::make_null()
{
 dblink *last,*extra;
 last=list->next;
 list->next=NULL;
 while(last !=NULL)
       {
	 extra=last->next;
	 delete last;
	 last=extra;
       }
}
//-----------------------------
int dblink::Find_Kth(int pos)
{
 int i;
 dblink *last;
 i=0;last=list;
	      if (Size()==0)
		   {
		     cout<<" empty\n";
		     exit(1);
		   }
	       while ((i !=pos) && (last->next !=NULL))

	       {  i++;
		  last=last->next;
	       }
	       return last->a;
}
//---------------------------
int dblink::Find(int value)
{int i;
 dblink *last;
 last=list;i=0;
 if (Size()==0)
	    {
	    cout<<" empty\n";
	    exit(1);
	    }
 if     (last->a==value) return 1;
 else   while  ((last->a !=value) && (last->next !=NULL))
	{      i++;
	       last=last->next;
	}
  if      (last->a==value) return i;
  else    return 0;
}
//---------------------------------------
void dblink::Insert(int value,int x)
{
 dblink *extra,*last,*llast;
 int i;
 if (x==1) {
		llast=list;
		if (llast->next==NULL)
		   {
			extra=new dblink;extra->a=value;
			extra->next=NULL;
			llast->next=extra;
		   }
		else {
		      extra=new dblink;
		      extra->a=value;
		      extra->next=llast->next;
		      llast->next=extra;
		  };
 }
 else if (x>1) {
		     extra=new dblink;
		     last=list->next;i = 1;
		     while ((last->next !=NULL) && ( i<x))
			   {
			     last=last->next;
			     ++i;
			   }
			if (i <= x){
					   extra->a=value;
					   extra->next=last->next;
					   last->next=extra;
				     }
			else
			{
				extra->a=value;
				extra->next=NULL;
				last->next=extra;
			};
		 };
};

//-----------------------------------
//-----------------------------------
//-----------------------------------
		    /* DECLERATION OF THE STACK CLASS */
//-----------------------------------
class Stack:public dblink
{
/* private:
 int a;             // MEMBORS OF THE STACK
 Stack *next; */
 public:
 void NewStack();  // MAKING A NEW EMPTY STACK
 int  Empty();     // CHEKS THE STACK IF EMPTY
 void Push(int value);   // PUSHS AN ELEMENT IN THE STACK
 int Pop();
}*stack;
//------------------------------------
			/* END OF THE BODY OF THE STACK */
//------------------------------------
			/* BUILDING FUNCTIONS OF THE STACK */
//------------------------------------
void Stack::NewStack()
 { List();
 }
//------------------------------------
int Stack::Empty()
{
 return (Size()==0);
}
//------------------------------------
void Stack::Push(int value)
{
 if (Empty()) List();
 Insert(value,1);
}
//-----------------------------------
int Stack::Pop()
{
 int value;
 if (Empty())
     {
     cout<<" empty \n";
     exit(1);
     } else

 {
 value=Find_Kth(1);
 ldelete(1);
 }
 return value;


}
//===================================
		/*  DECLERATION OF THE QUEUE */
//===================================

class Queue:public dblink
{
/* private:
 int a;
 Queue *next; */
 public:
 void NewQueue();
 int  Empty();
 void EnQueue(int value);
 int  DeQueue();
} *queue;
//-----------------------------------
		       /* BUILDING OF THE QUEUE PROCEDURES */
//-----------------------------------
void Queue::NewQueue()
{
  List();
}
//----------------------------------
int Queue::Empty()
{
 return(Size()==0);
 }
//============================
void Queue::EnQueue(int value)
{
 if (Empty()) List();
 Insert(value,Size()+1);
 }
//=============================
int Queue::DeQueue()
{
int value;
if (Empty())
	  { cout<<" empty \n";
	    exit(1);
	  } else
     {
       value=Find_Kth(1);
       ldelete(1);
     }
       return value;

}
//==============================
	     /* MAIN BODY OF THE PROGRAM */
//==============================

main()
{
char ch,chh,chr,cha;
int  n,k1,k2,k3,k4,a1,k5,k6,a,s,q,b,w,w1;
clrscr();
list->List();


while (chr !='n' && chr !='N')
{
clrscr();
cout<<"\n"<<"	    making null        : press  1";cout<<"\n";
cout<<"\n"<<" 	    finding position   : press  2";cout<<"\n" ;
cout<<"\n"<<"           finding element at a given position   : press  3\n";
cout<<"\n"<<" 	   inserting element  : press  4";cout<<"\n";
cout<<"\n"<<"  	   deleting element at a given position  : press  5 \n";
cout<<"\n"<<"           finding the size   : press  6";cout<<"\n";
cout<<"\n"<<"           printing the list  : press  7";cout<<"\n";
//cout<<"\n"<<"           deleting element   : press  8";cout<<"\n";
cout<<"\n"<<"           update the stack   : press  9";cout<<"\n";
cout<<"\n"<<"           update the queue   : press  0";cout<<"\n";


cin>>chh;

if (chh=='1')  list->make_null(); else
if (chh=='2')  {
		cout<< " enter the element to find position \n";
		cin>>k1;
		a=list->Find(k1);cout<<"\n"<<"position is : "<<a<<"\n";
	      }else
if (chh=='3')  {
		cout<<" enter the position \n";
		cin>>k2;
		b=list->Find_Kth(k2);cout<<"\n"<<b;
	      }else
if (chh=='4')   {
		cout<<"enter element and position \n";
		cin>>k3>>k4;
		list->Insert(k3,k4);
	      }  else
if (chh=='5')   {
		cout<<"enter position to delete \n";
		cin>>k5;
		list->ldelete(k5);
	      }else
if (chh=='6')   {
		 a1=list->Size();
		 cout<<"\n"<<" size is : "<<a1<<"\n";
		 }
		 else
if (chh=='7')   list->Print_List();else
/*if (chh=='8')  {       cout<<" element to delete \n";
		     cin>>k6;
		     list->Delete(k6);
		 }else    */
if (chh=='9') {
	       clrscr();
	       cout<<"         push   :    press  0 "<<"\n";
	       cout<<"         pop    :    press  1 "<<"\n";
	       cin>>cha;
	       if (cha=='0')
		     { cout<<"    enter your value  "<<"\n";
		       cin>>s;
		       stack->Push(s);
		     }
	      if (cha=='1')
			   {
			    w=stack->Pop();
			    cout<< "  value is : "<<w;
			   }
	     }else
if (chh=='0') {clrscr();
	       cout<<"        enqueue   :  press   2"<<"\n";
	       cout<<"        dequeue   :  press   3"<<"\n";
	       cin>>cha;
	       if (cha=='2')
			{ cout<<"   enter your value  "<<"\n";
			  cin>>q;
			  queue->EnQueue(q);
			}
	      if (cha=='3')
			    {
			     w1=queue->DeQueue();
			     cout<<"    value is : "<<w1;
			    }
	    }


cout<<"      continue   :   if not press n  or  N \n" ;
cout<<"                        else press any other key \n";
chr=getch(); }
ch=getche();
return 0;
}