elhacker.net cabecera Bienvenido(a), Visitante. Por favor Ingresar o Registrarse
¿Perdiste tu email de activación?.

 

 


Tema destacado: Curso de javascript por TickTack


+  Foro de elhacker.net
|-+  Programación
| |-+  Programación C/C++ (Moderadores: Eternal Idol, Littlehorse, K-YreX)
| | |-+  Implementar una pila con una cola en c++		0 Usuarios y 1 Visitante están viendo este tema.
Páginas: [1] Ir Abajo Respuesta Imprimir
Autor Tema: Implementar una pila con una cola en c++  (Leído 7,861 veces)
alvareteb

Desconectado Desconectado

Mensajes: 8


Ver Perfil
Implementar una pila con una cola en c++
« en: 24 Enero 2012, 14:18 pm »
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
  1. const TElem& cima() const throw (EAccesoIndebido);
  2. 	//pre: !esVacio
  3. 	//post: devuelve la cima
  4. 	//Lanza excepcion si la pila esta vacia
  5.  
  6. Tendrá que ser por recursión pero dentro de esta funcion no puedo usa _cola.quitaPrimero() ni _cola.ponUltimo()porque me da error C2662.
  7.  
  8. alguien me ayuda?
  9.  
  10. Yo había pensado algo así (pero da error C2662)
  11. template <class TElem>
  12. const TElem& TPila<TElem>::cima() const throw (EAccesoIndebido){
  13.  
  14. 	 if(esVacio())
  15.     throw EAccesoIndebido("Error: no existe cima de la pila vacía");
  16. 	 else {
  17. 	 TElem aux;
  18. 	 aux=_cola.primero();
  19. 	 _cola.
  20. 	 cima();
  21. 	 _cola.ponDetras(aux);
  22. 	 return aux;}
  23. 	//fin else
  24. }
  25.  
« Última modificación: 24 Enero 2012, 14:23 pm por alvareteb » En línea
Xandrete

Desconectado Desconectado

Mensajes: 210



Ver Perfil
Re: Implementar una pila con una cola en c++
« Respuesta #1 en: 24 Enero 2012, 16:08 pm »
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
  1. template <class TElem>
  2. const TElem& TPila<TElem>::cima() throw (EAccesoIndebido){
  3.  
  4. 	 if(esVacio()) throw EAccesoIndebido("Error: no existe cima de la pila vacía");
  5. 	 else {
  6. 	 TElem aux;
  7. 	 aux=_cola.primero();
  8. 	 _cola.
  9. 	 cima();
  10. 	 _cola.ponDetras(aux);
  11. 	 return aux;}
  12. 	//fin else
  13. }

Saludos
« Última modificación: 24 Enero 2012, 16:16 pm por Xandrete » En línea
alvareteb

Desconectado Desconectado

Mensajes: 8


Ver Perfil
Re: Implementar una pila con una cola en c++
« Respuesta #2 en: 24 Enero 2012, 16:26 pm »
El caso es que con tipos auxiliares no hay problema pero no me dejan usarlos.
Código
  1. template <class TElem>
  2. const TElem& TPila<TElem>::cima() const throw (EAccesoIndebido){
  3. TCola <TElem> colaAux;
  4. colaAux=_cola;	 
  5. if(esVacio())
  6.     throw EAccesoIndebido("Error: no existe cima de la pila vacía");
  7. 	else	{
  8. 	TElem aux;
  9. 	while (!colaAux.esVacio()) {
  10.  aux=colaAux.primero();
  11.  colaAux.quitaPrim();}
  12. 	return aux;
  13. 	}	//fin else
  14. }
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
  1. template <class TElem>
  2. TElem TPila<TElem>::cimaAux(){
  3. 	TElem aux;
  4. 	aux=_cola.primero();
  5. 	_cola.
  6. 	cimaAux();
  7. 	_cola.ponDetras(aux);
  8. 	return aux;
  9.  
  10. }
  11.  
  12. template <class TElem>
  13. const TElem& TPila<TElem>::cima() const throw (EAccesoIndebido){
  14.  
  15. 	 if(esVacio())
  16.     throw EAccesoIndebido("Error: no existe cima de la pila vacía");
  17. 	 else {	
  18. 		 return cimaAux();}
  19. 	//fin else
  20. }
En línea
Xandrete

Desconectado Desconectado

Mensajes: 210



Ver Perfil
Re: Implementar una pila con una cola en c++
« Respuesta #3 en: 24 Enero 2012, 17:15 pm »
¿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
« Última modificación: 24 Enero 2012, 17:17 pm por Xandrete » En línea
alvareteb

Desconectado Desconectado

Mensajes: 8


Ver Perfil
Re: Implementar una pila con una cola en c++
« Respuesta #4 en: 24 Enero 2012, 17:27 pm »
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
  1. template <class TElem>
  2. class TCola {
  3. public:
  4. 	//constructora destructora y operador de asignacion
  5. 	TCola();
  6. 	TCola(const TCola<TElem>&);
  7. 	~TCola();
  8. 	TCola<TElem>& operator=(const TCola<TElem>&);
  9. //Operaciones de las colas
  10.  
  11. 	void ponDetras(const TElem&);
  12. 	//Pre:true
  13. 	//post: se añade elem al final de la cola
  14.  
  15. 	const TElem& primero() const throw (EAccesoIndebido);
  16. 	//Pre:!esVacio()
  17. 	//Post: Devuelve el primer elementos de la Cola
  18. 	//Lanza Excepcion si la cola está vacía
  19.  
  20. 	void quitaPrim() throw (EAccesoIndebido);
  21. 	//Pre !esVacio();
  22. 	//Post Elimina el primer elemento de la cima
  23. 	//Lanza la excepción 
  24.  
  25. 	bool esVacio() const;
  26. 	//Pre true
  27. 	//Posr Devuelve true o false dependiendo de si la cola esta o no vacia
« Última modificación: 24 Enero 2012, 19:59 pm por Eternal Idol » En línea
Xandrete

Desconectado Desconectado

Mensajes: 210



Ver Perfil
Re: Implementar una pila con una cola en c++
« Respuesta #5 en: 24 Enero 2012, 20:03 pm »
¿Recursivamente? ¿Sin acceder a punteros?

Bueno, esta es mi idea:

Código
  1. template <class TElem>
  2. Result TPila<TElem>::cimaAux(){
  3. 	Result r;
  4. 	if (_cola.esVacio()) r.found = true;
  5. 	else {
  6. 		TElem aux = _cola.primero();
  7. 		_cola.quitarPrimero();
  8. 		r = _cola.cimaAux();
  9. 		_cola.ponDetras(aux);
  10. 		if (r.found == true) {
  11. 			r.elem = aux;
  12. 			r.found = false;
  13. 		}
  14. 	}
  15. 	return r;
  16. }
  17.  
  18. template <class TElem>
  19. const TElem& TPila<TElem>::cima() throw (EAccesoIndebido){
  20.  
  21. 	if(esVacio()) throw EAccesoIndebido("Error: no existe cima de la pila vacía");
  22. 	Result r = cola.cimaAux();
  23. 	return r.elem;
  24. }

Previamente tendrías que definir el struct Result:

Código
  1. struct Result {
  2. 	TElem elem;
  3. 	bool found;
  4. };

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 ;D
« Última modificación: 24 Enero 2012, 20:08 pm por Xandrete » En línea
alvareteb

Desconectado Desconectado

Mensajes: 8


Ver Perfil
Re: Implementar una pila con una cola en c++
« Respuesta #6 en: 25 Enero 2012, 01:12 am »
Gracias por tu ayuda pero con un struct tampoco me vale. Alguna otra forma?
En línea
Xandrete

Desconectado Desconectado

Mensajes: 210



Ver Perfil
Re: Implementar una pila con una cola en c++
« Respuesta #7 en: 25 Enero 2012, 10:49 am »
¡!

¡¿Tampoco?!

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

Código
  1. template <class TElem>
  2. void TPila<TElem>::cimaAux(bool &found, TElem &result){
  3. 	if (not _cola.esVacio()) {
  4. 		TElem aux = _cola.primero();
  5. 		_cola.quitarPrimero();
  6. 		_cola.cimaAux();
  7. 		_cola.ponDetras(aux);
  8. 		if (not found) {
  9. 			result = aux;
  10. 			found = true;
  11. 		}
  12. 	}
  13. }
  14.  
  15. template <class TElem>
  16. const TElem& TPila<TElem>::cima() throw (EAccesoIndebido){
  17.  
  18. 	if(esVacio()) throw EAccesoIndebido("Error: no existe cima de la pila vacía");
  19. 	TElem elem;
  20. 	bool b = false;
  21. 	cimaAux(b,elem);
  22. 	return elem;
  23. }

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?
« Última modificación: 25 Enero 2012, 12:22 pm por Xandrete » En línea
alvareteb

Desconectado Desconectado

Mensajes: 8


Ver Perfil
Re: Implementar una pila con una cola en c++
« Respuesta #8 en: 25 Enero 2012, 18:14 pm »
Al final consegui resolverlo implementando una funcion invertir. Muchas gracias por tu ayuda.

Código
  1. template <class TElem>
  2. void TPila<TElem>::invertir() {
  3. 	TElem e;
  4. 	if(!esVacio()){
  5. 		e=_cola.primero();
  6. 		_cola.quitaPrim();
  7. 		invertir();
  8. 		_cola.ponDetras(e);
  9.  
  10. 	}//end if
  11. }
  12.  
  13. template <class TElem>
  14. const TElem& TPila<TElem>::cima() throw (EAccesoIndebido){
  15.  
  16. if(esVacio()) throw EAccesoIndebido("Error: no existe cima de la pila vacía");
  17. else {
  18. 	invertir();
  19. 	TElem e=_cola.primero();
  20. 	invertir();
  21. 	return e;}
  22. }
  23.  
En línea
Xandrete

Desconectado Desconectado

Mensajes: 210



Ver Perfil
Re: Implementar una pila con una cola en c++
« Respuesta #9 en: 25 Enero 2012, 19:36 pm »
¡Muy bien! Entonces, perdona por lo que te dije:

Citar
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  ;D

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!
En línea
Páginas: [1] Ir Arriba Respuesta Imprimir 

Ir a:  

Mensajes similares
Asunto Iniciado por Respuestas Vistas Último mensaje
Pila & Cola
Programación C/C++ 		¡Micronet! 2 5,209 Último mensaje 23 Octubre 2010, 13:02 pm
por Saberuneko
Aporte C++ - Clases Pila y Cola.
Programación C/C++ 		xaps 0 3,359 Último mensaje 21 Diciembre 2013, 17:52 pm
por xaps
Motivos para ordenar una pila y una cola?
Programación General 		milx86 3 3,989 Último mensaje 15 Marzo 2014, 16:57 pm
por milx86
C - Implementar cola de prioridades
Programación C/C++ 		ank3r 1 5,648 Último mensaje 13 Mayo 2014, 16:20 pm
por eferion
[C] (Aporte) Estructura de pila y cola con memoria dinámica
Programación C/C++ 		class_OpenGL 2 4,427 Último mensaje 23 Agosto 2016, 04:56 am
por class_OpenGL
WAP2 - Aviso Legal - Powered by SMF 1.1.21 | SMF © 2006-2008, Simple Machines