Implementar una pila con una cola en c++

[alvareteb]

Buenas, estoy intentando resolver un ejercicio en el que hay que implementar una pila usando como único atributo una cola y junto con la restricción de no poder usar TADs auxiliares.

Mi problema es que no se como obtener la cima sin utilizar una cola auxiliar. La definición de la operación es esta:

Código (cpp) [Seleccionar] Expandir


const TElem& cima() const throw (EAccesoIndebido);
//pre: !esVacio
//post: devuelve la cima
//Lanza excepcion si la pila esta vacia

Tendrá que ser por recursión pero dentro de esta funcion no puedo usa _cola.quitaPrimero() ni _cola.ponUltimo()porque me da error C2662.

alguien me ayuda?

Yo había pensado algo así (pero da error C2662)
template <class TElem>
const TElem& TPila<TElem>::cima() const throw (EAccesoIndebido){

if(esVacio())
   throw EAccesoIndebido("Error: no existe cima de la pila vacía");
else {
TElem aux;
aux=_cola.primero();
_cola.
cima();
_cola.ponDetras(aux);
return aux;}
//fin else
}


[Xandrete]

http://msdn.microsoft.com/en-us/library/2s2d2tez%28v=vs.80%29.aspx

Estas usando acciones que modifican la cola en una función en que es referencia constante. Necesariamente, la cola se ha de modificar en la función cima(), luego ha de ser referencia no constante.

Código (cpp) [Seleccionar] Expandir

template <class TElem>
const TElem& TPila<TElem>::cima() throw (EAccesoIndebido){

if(esVacio()) throw EAccesoIndebido("Error: no existe cima de la pila vacía");
else {
TElem aux;
aux=_cola.primero();
_cola.
cima();
_cola.ponDetras(aux);
return aux;}
//fin else
}

Saludos

[alvareteb]

El caso es que con tipos auxiliares no hay problema pero no me dejan usarlos.

Código (cpp) [Seleccionar] Expandir


template <class TElem>
const TElem& TPila<TElem>::cima() const throw (EAccesoIndebido){
TCola <TElem> colaAux;
colaAux=_cola;
if(esVacio())
    throw EAccesoIndebido("Error: no existe cima de la pila vacía");
else {
TElem aux;
while (!colaAux.esVacio()) {
aux=colaAux.primero();
colaAux.quitaPrim();}
return aux;
} //fin else
}
Existe alguna forma de hacerlo sin tipos auxiliares y sin cambiar la definición de la operación?
Quizás con una función auxiliar?? Yo lo he intentando pero tampoco me deja.

Código (cpp) [Seleccionar] Expandir

template <class TElem>
TElem TPila<TElem>::cimaAux(){
TElem aux;
aux=_cola.primero();
_cola.
cimaAux();
_cola.ponDetras(aux);
return aux;

}

template <class TElem>
const TElem& TPila<TElem>::cima() const throw (EAccesoIndebido){

if(esVacio())
    throw EAccesoIndebido("Error: no existe cima de la pila vacía");
else {
return cimaAux();}
//fin else
}

[Xandrete]

¿Sin cambiar la definición de la función? Hombre, en ese caso sería útil que nos pusieras la implementación y/o la especificación de la clase cola que usas (que claramente no es la estándar). Lo normal es que una cola tenga un puntero hacia el primer nodo, y que cada nodo tenga un puntero hacia el nodo que le sucede. El elemento que buscas (la cima) es el último de la cola, por lo que su puntero al siguiente elemento tendrá valor NULL. Puedes ir navegando a través de la cola hasta que te encuentres un nodo que no apunte a nadie (valor NULL). En este caso no modificas nada y no tendría que producirse el error C2662.

Cuando la cola es referencia constante, no puedes modificarla. Ni en la misma función ni en funciones auxiliares. Por eso no te deja.

Saludos

[alvareteb]

La historia es que tampoco puedo acceder a los atributos ni operaciones privadas de la cola (prohibido por el ejercicio en cuestión).

La cola es el único atributo de la clase TPila y sólo puedo acceder a su parte pública.

En caso de cambiar la definición de la cima como lo harías (recursivamente)?
Me estoy volviendo loco...

EI: juntando mensajes.

De la cola puedo acceder a esto.

Código (cpp) [Seleccionar] Expandir


template <class TElem>
class TCola {
public:
//constructora destructora y operador de asignacion
TCola();
TCola(const TCola<TElem>&);
~TCola();
TCola<TElem>& operator=(const TCola<TElem>&);
//Operaciones de las colas

void ponDetras(const TElem&);
//Pre:true
//post: se añade elem al final de la cola

const TElem& primero() const throw (EAccesoIndebido);
//Pre:!esVacio()
//Post: Devuelve el primer elementos de la Cola
//Lanza Excepcion si la cola está vacía

void quitaPrim() throw (EAccesoIndebido);
//Pre !esVacio();
//Post Elimina el primer elemento de la cima
//Lanza la excepción

bool esVacio() const;
//Pre true
//Posr Devuelve true o false dependiendo de si la cola esta o no vacia

[Xandrete]

¿Recursivamente? ¿Sin acceder a punteros?

Bueno, esta es mi idea:

Código (cpp) [Seleccionar] Expandir

template <class TElem>
Result TPila<TElem>::cimaAux(){
Result r;
if (_cola.esVacio()) r.found = true;
else {
TElem aux = _cola.primero();
_cola.quitarPrimero();
r = _cola.cimaAux();
_cola.ponDetras(aux);
if (r.found == true) {
r.elem = aux;
r.found = false;
}
}
return r;
}

template <class TElem>
const TElem& TPila<TElem>::cima() throw (EAccesoIndebido){

if(esVacio()) throw EAccesoIndebido("Error: no existe cima de la pila vacía");
Result r = cola.cimaAux();
return r.elem;
}

Previamente tendrías que definir el struct Result:

Código (cpp) [Seleccionar] Expandir

struct Result {
TElem elem;
bool found;
};

Lo puedes definir en los atributos públicos de la clase, en los privados, o fuera de la clase (lo que en este último caso tienes que usar la plantilla). Asegúrate de que he usado los nombres correctos de las funciones, porque estoy tan acostumbrados a los de la librería estándar que casi me ha costado ponerlos en español.

Saludos

P.S. ¿Por qué no os dicen también que tenéis que hacerlo sin mirar la pantalla del ordenador, con una mano, y cantando "¿Donde vas Alfonso XII?" ? Mira que son rebuscados 

[alvareteb]

Gracias por tu ayuda pero con un struct tampoco me vale. Alguna otra forma?

[Xandrete]

¡!

¡¿Tampoco?!

Pues no uses un struct. Haz lo mismo, pero mediante paso de parámetros por referencia:

Código (cpp) [Seleccionar] Expandir

template <class TElem>
void TPila<TElem>::cimaAux(bool &found, TElem &result){
if (not _cola.esVacio()) {
TElem aux = _cola.primero();
_cola.quitarPrimero();
_cola.cimaAux();
_cola.ponDetras(aux);
if (not found) {
result = aux;
found = true;
}
}
}

template <class TElem>
const TElem& TPila<TElem>::cima() throw (EAccesoIndebido){

if(esVacio()) throw EAccesoIndebido("Error: no existe cima de la pila vacía");
TElem elem;
bool b = false;
cimaAux(b,elem);
return elem;
}

Saludos

P.S. De todas formas, y lo digo sin mal rollo: ¿era totalmente necesario que fuera yo (o cualquier otro) quien te planteara esta alternativa? ¿Si no podías emplear structs, no era posible que pensaras en esto por tu cuenta?

[alvareteb]

Al final consegui resolverlo implementando una funcion invertir. Muchas gracias por tu ayuda.

Código (cpp) [Seleccionar] Expandir


template <class TElem>
void TPila<TElem>::invertir() {
TElem e;
if(!esVacio()){
e=_cola.primero();
_cola.quitaPrim();
invertir();
_cola.ponDetras(e);

}//end if
}

template <class TElem>
const TElem& TPila<TElem>::cima() throw (EAccesoIndebido){

if(esVacio()) throw EAccesoIndebido("Error: no existe cima de la pila vacía");
else {
invertir();
TElem e=_cola.primero();
invertir();
return e;}
}


[Xandrete]

¡Muy bien! Entonces, perdona por lo que te dije:

P.S. De todas formas, y lo digo sin mal rollo: ¿era totalmente necesario que fuera yo (o cualquier otro) quien te planteara esta alternativa? ¿Si no podías emplear structs, no era posible que pensaras en esto por tu cuenta?

Me había precipitado. Has creado tu propia solución 

Tu forma de hacerlo es un poco ineficiente, porque reordenas la cola dos veces, pero bueno. La idea de implementar una pila con una cola ya es bastante ineficiente >.< (está claro que este es un ejercicio con fines más académicos que prácticos).

¡Saludos!