#include <iostream>

using namespace std;

typedef struct tnodo *pnodo;
typedef struct tnodo{
	char dato;
	pnodo sig;
};

typedef struct tlista{ // definición de lista considerando puntero inicial y contador de elementos
	pnodo inicio;
	int contador;
};


void iniciar_lista(tlista &lista);
void crear_nodo(pnodo &nuevo);
void agregar_inicio(tlista &lista,pnodo nuevo);
pnodo quitar_final(tlista &lista);
void mostrar(tlista lista);
bool buscar(tlista lista,char valor);

main()
{ int op;
  tlista milista; // variable lista (puntero inicial y contador de elementos)
  pnodo nuevo; // puntero para guardar la dirección de un nuevo nodo
  pnodo aux; // puntero para guardar la dirección de un nuevo nodo
  char valor;
  iniciar_lista(milista);
  do{ system("cls");
	cout << "1-Agregar nodo" << endl;
	cout << "2-Quitar nodo" << endl;
	cout << "3-Mostrar" << endl;
	cout << "4-Buscar" << endl;
	cout << "5-Salir" << endl;
	cout << "Ingrese opcion: ";
	cin >> op;
	switch (op)
	{ case 1: cout << "### AGREGANDO DATOS ###" << endl;
			crear_nodo(nuevo);
			if (nuevo!=NULL)
				agregar_inicio(milista,nuevo);
			else
				cout << "No hay espacio suficiente en memoria" << endl;
			break;
	case 2: cout << "### EXTRAYENDO DATOS ###" << endl;
			aux=quitar_final(milista);
			if (aux!=NULL)
			{ cout << "se extrajo: " << aux->dato << endl;
			  delete(aux);	
			}
			else
			  cout << "no se realizo la extraccion" << endl;
			break;
	case 3: cout << "### MOSTRANDO DATOS ###" << endl;
			mostrar(milista);
			break;
	case 4: cout << "### BUSCANDO DATOS ###" << endl;
			cout << "Ingrese valor a buscar:";
			cin >> valor;
			if (buscar(milista,valor)==true)
				cout << valor << " existe en la lista" << endl;
			else
				cout << valor << " no pertenece a la lista" << endl;
			break;
	case 5: cout << "FIN DE PROGRAMA" << endl;
			break;
	default: cout << "Error de opcion" << endl;
	}
	system("pause");
  } while(op!=5);
}

void iniciar_lista(tlista &lista)
{
	lista.inicio=NULL; // inicialización del puntero del primer elemento
	lista.contador=0; // inicialización del contador de elementos
}

void crear_nodo(pnodo &nuevo)
{
	nuevo=new tnodo;
	if (nuevo!=NULL)
	{ cout << "Ingrese el caracter: ";
	  cin >> nuevo->dato;
	  nuevo->sig=NULL;		
	}
}

void agregar_inicio(tlista &lista,pnodo nuevo)
{ 
	if (lista.inicio==NULL) // también se podría usar (lista.contador==0)
		lista.inicio=nuevo;
	else
	{   nuevo->sig=lista.inicio;
	    lista.inicio=nuevo;
	}
	lista.contador++; // actualización del contador
}				

pnodo quitar_final(tlista &lista)
{ pnodo extraido,i;
  if (lista.inicio==NULL) // también se podría usar (lista.contador==0)
	extraido=NULL;
  else
  {	if (lista.contador==1)// también se podría usar (lista.inicio->sig==NULL)
    { extraido=lista.inicio;
      lista.inicio=NULL;
	}
	else
    { for(i=lista.inicio;(i->sig)->sig!=NULL;i=i->sig);
       extraido=i->sig; // extraido apunta al último;
	   i->sig=NULL; // el sig de penúltimo apunta a nulo
    }
    lista.contador--;  // actualización del contador
  }
  return extraido;
}

void mostrar(tlista lista)
{ pnodo i;
cout << "cantidad de elementos de la lista: " << lista.contador << endl;
if (lista.inicio==NULL)
	cout << "vacio" << endl;
else
	for(i=lista.inicio;i!=NULL;i=i->sig)
	  cout << i->dato << endl;
}	


bool buscar(tlista lista,char valor)
{ pnodo i;
  bool existe=false;
  if (lista.contador!=0)
	for(i=lista.inicio;i!=NULL && existe==false;i=i->sig)
	  if (i->dato==valor)
		existe=true;
  return existe;
}