#include <iostream>

using namespace std;

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

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

main()
{ int op;
  pnodo inicio; // puntero al primer elemento de la lista
  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(inicio);
  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(inicio,nuevo);
			else
				cout << "No hay espacio suficiente en memoria" << endl;
			break;
	case 2: cout << "### EXTRAYENDO DATOS ###" << endl;
			aux=quitar_final(inicio);
			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(inicio);
			break;
	case 4: cout << "### BUSCANDO DATOS ###" << endl;
			cout << "Ingrese valor a buscar:";
			cin >> valor;
			if (buscar(inicio,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(pnodo &lista)
{
	lista=NULL;
}

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

void agregar_inicio(pnodo &lista,pnodo nuevo)
{ 
	if (lista==NULL)
		lista=nuevo;
	else
	{   nuevo->sig=lista;
		lista=nuevo;
	}
}				
				
pnodo quitar_final(pnodo &lista)
{ pnodo extraido,i;
	if (lista==NULL)
		extraido=NULL;
	else
	{	if (lista->sig==NULL)
	      { extraido=lista;
			lista=NULL;
	      }
		else
		{  for(i=lista;(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
		} 
    }
	return extraido;
}

void mostrar(pnodo lista)
{ pnodo i;
	if (lista==NULL)
		cout << "vacio" << endl;
	else
	  for(i=lista;i!=NULL;i=i->sig)
		cout << i->dato << endl;
}	
	
	
bool buscar(pnodo lista,char valor)
{ pnodo i;
  bool existe=false;
  if (lista!=NULL)
	for(i=lista;i!=NULL && existe==false;i=i->sig)
	  if (i->dato==valor)
		  existe=true;
  return existe;
}