#include <iostream>
#include <stdlib.h>
using namespace std;

//const int MAX=10;
typedef struct tnodo *pnodo;

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

typedef struct tcola{
          pnodo inicio;
          int cont;
          pnodo fin;
};

void iniciar_cola(tcola &lis)
{
    lis.inicio=NULL;
    lis.fin=NULL;
    lis.cont=0;

}

//Creación del nodo
void crear(pnodo &nuevo, char valor)
{
    nuevo=new tnodo;
    if(nuevo!=NULL)
    {
        nuevo->dato=valor;
        nuevo->sig=NULL;
        nuevo->ant=NULL;
    }
    else
        cout<<"Memoria llena"<<endl;
}
bool cola_llena(tcola lis)
{
	return lis.cont==MAX;
}
//Agregar elemento
void agregar_cola(tcola &lis, char valor) //agregar inicio
{pnodo nuevo;
  if(cola_llena(lis)==true)
     cout<<"No se puede agregar mas nodos"<<endl;
  else{
      crear(nuevo,valor);
    if(lis.inicio==NULL) //lis.cont==0 lis.fin==NULL
    {
      lis.inicio=nuevo;
      lis.fin=nuevo;
      lis.cont++;
    }
    else{
      nuevo->sig=lis.inicio;
      lis.inicio->ant=nuevo;
      lis.inicio=nuevo;
      lis.cont++;
    }
  }
}
bool cola_vacia(tcola lis)
{
  return lis.cont==0;
}
/*
void agregar_final(tlista &lis, pnodo nuevo)
{
	if(lista_llena(lis)==true)
		cout<<"No se puede agregar mas nodos"<<endl;
	else{
		if(lis.inicio==NULL) //lis.cont==0 lis.fin==NULL
		{
			lis.inicio=nuevo;
			lis.fin=nuevo;
			lis.cont++;
		}
		else{
			lis.fin->sig=nuevo;
			nuevo->ant=lis.fin;
			lis.fin=nuevo;
			lis.cont++;
		}
	}
}
*/
char quitar_cola(tcola &lis) //quitar final
{  pnodo aux;
  char eliminado;
	if(lis.inicio==NULL) //cola_vacia(lis)==true
		{aux=NULL;
		 eliminado='@';
		}
	else
	{   if(lis.inicio==lis.fin)
		{
			aux=lis.inicio; //aux=lis.fin
			eliminado=aux->dato;
			lis.inicio=NULL;
			lis.fin=NULL;
			aux->sig=NULL;
		}
		else
		 {
			aux=lis.fin;
			eliminado=aux->dato;
			lis.fin=lis.fin->ant;
			lis.fin=aux->ant;
			lis.fin->sig=NULL;
			aux->ant=NULL;
		}
	lis.cont--;
	}
	delete(aux);
	return eliminado;
}
/*
pnodo quitar_inicio(tlista &lis)
{ pnodo aux, i;
    if(lis.inicio==NULL)//lis.cont==0  lis.fin==NULL
        aux=NULL;
    else
    { if(lis.inicio->sig==NULL) //lis.cont==1 o lis.inicio==lis.fin
        {
            aux=lis.inicio; //aux=lis.fin
            lis.inicio=NULL;
            lis.fin=NULL;
        }
        else
        {
		  aux=lis.inicio;
		  lis.inicio=lis.inicio->sig;
		  lis.inicio->ant=NULL;
		  aux->sig=NULL;
        }
       lis.cont--;
    }
    return aux;
}

void mostrar_lista(tlista lis)
{
    pnodo i;
    for(i=lis.inicio; i!=NULL; i=i->sig)
        cout<<i->dato<<endl;
}

*/

char consultar_primero(tcola lis)
{
  char valor;
  if(cola_vacia(lis)!=true)
    valor=lis.fin->dato;
  else
    valor='@';
  return valor;
}

char consultar_ultimo(tcola lis)
{
  char valor;
  if(cola_vacia(lis)!=true)
    valor=lis.inicio->dato;
  else
    valor='@';
  return valor;
}