0

Encontré un ejercicio resuelto donde se usan pilas y listas que me generó dudas, es este:

Impleméntese el método no recursivo de la clase dll_t ostream& write_reverse (dll_node_t<T>* n, ostream& os) const que muestra en orden inverso el contenido de la lista enlazada invocante a partir del nodo n con ayuda de una pila que almacene punteros de nodos. Sólo se podrá utilizar el método dll_node_t* get_next() de la clase dll_node_t para acceder al elemento siguiente. En ningún caso se permitirá utilizar el método dll_node_t* get_prev().

El ejercicio resuelto:

 template <class T>
  ostream& dll_t<T>::write_reverse2(dll_node_t<T>* n, ostream& os) const {      

        stack_v_t<dll_node_t<T>*> stack;

        while (n != NULL) {
            stack.push_back(n);
            n = n->get_next();
        }

        while(!stack.empty()){

            stack.top()->write(os);
            stack.pop();
        }

        return os;
    }

    template <class T>
    ostream& dll_t<T>::write_reverse2(ostream& os) const {

        reverse2(head_, os);

        return os;
    }

la clase pila de la que hace uso:

template <class T>
class stack_v_t{
private:
vector_t<T> v_;
int top_;
public:
stack_v_t(int max_sz);
~stack_v_t(void);
bool empty(void);
T top(void);
void pop(void);
void push(T dato);
};

Mi duda: Al crear la pila, ¿no debería tener un tamaño fijo, no le da un tamaño, tendría que tenerlo no?

3
  • 3
    Repetida. el 24 jul. 2017 a las 12:20
  • @PaperBirdMaster Una pregunta,si en vez de mostrar en orden inverso el contenido de la lista, lo quiero mostrar en orden normal, ¿cómo he de manejar la pila para que lo imprima así?
    – AER
    el 25 jul. 2017 a las 11:32
  • 1
    Las pilas no están diseñadas para ser atravesadas en ningún orden, su cometido es apilar o desapilar datos. el 25 jul. 2017 a las 12:42

1 respuesta 1

1

No debería tener un tamaño fijo, La implementacion no tiene un constructor stack_v_t() sin parametros asi que segun esa implementacion de pila la respuesta esta mal.

template <class T>
class stack_v_t{
private:
vector_t<T> v_;
int top_;
public:
stack_v_t(int max_sz);//Constructor
//Necesitaria n constructor:stack_v_t();
~stack_v_t(void);
bool empty(void);
T top(void);
void pop(void);
void push(T dato);
};

El tamaño fijo se debe a una limitacion de la implementacion no que el concepto de pila lo requiera. Si se implementa con arrays el tamaño puede ser importante pero si se implementa con listas enlazadas no.

El metodo tiene fallos que no inicia la clase pila:

 template <class T>
  ostream& dll_t<T>::write_reverse2(dll_node_t<T>* n, ostream& os) const {      

        stack_v_t<dll_node_t<T>*> stack;
        /*stack no es un puntero es un stack del   tipo  
          stack_v_t<dll_node_t<T>*> 
          al inicializarse asi  la clase stack_v_t debe tener un 
          constructor sin parametros y las llamadas a los metodos se 
          hacen con '.' en lugar de ->
         */

        while (n != NULL) {
            stack.push_back(n);
            n = n->get_next();
        }

        while(!stack.empty()){

            stack.top()->write(os);//stack.top() devuelve un objeto 
            // tipo  T como se garantiza que tenga el metodo ->write(os)???
            //Puede ser?: os<<stack.top();
            stack.pop();
        }

        return os;
    }

    template <class T>
    ostream& dll_t<T>::write_reverse2(ostream& os) const {

        reverse2(head_, os);

        return os;
    }

Si la clase de pila que usas es la de esta otra pregunta Error clase vector_t C++ si creas un stack para 20 elementos no puedes usarlo para 21, pero es la implementacion la que es pobre, ya que al sobrepasar la capacidad deberia redimencionar el array y lo que hace es dar error.

Segun esta implementacion (el codigo no esta probado):

const int STACK_CAPACITY= 100;//maxima capacidad de la pila
 template <class T>
  ostream& dll_t<T>::write_reverse2(dll_node_t<T>* n, ostream& os) const   {      

    stack_v_t<dll_node_t<T>*> stack(STACK_CAPACITY);

    while (n != NULL) {
        stack.push_back(n);
        n = n->get_next();
    }

    while(!stack.empty()){

        stack.write(stack.top());//Cambie aqui usando el metodo write de la clase stack_v_t
        stack.pop();
    }

    return os;
}

template <class T>
ostream& dll_t<T>::write_reverse2(ostream& os) const {

    reverse2(head_, os);

    return os;
}

Tu Respuesta

By clicking “Publica tu respuesta”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

¿No es la respuesta que buscas? Examina otras preguntas con la etiqueta o formula tu propia pregunta.