Doubt exercise stack based on lists

Question

Doubt exercise stack based on lists

Navigation

#1 by (1 votes)

0

I found a solved exercise where batteries and lists are used that generated doubts, this is:

Implement the non-recursive method of class dll_t ostream& write_reverse (dll_node_t<T>* n, ostream& os) const that shows in reverse order the content of the invoked linked list from node n with help from a stack that stores node pointers. Only the dll_node_t* get_next() method of the class dll_node_t can be used to access the next element. In no case will the method dll_node_t* get_prev() be allowed.

The exercise solved:

 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;
    }

the class stack he uses:

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);
};

My doubt: When creating the stack, should not it have a fixed size, does not give it a size, would it have to have it not?

lista c++ pilas

asked by AER 24.07.2017 в 13:53

source

1 answer

No data sent by post in php Calculate successors of a node in a directed graph

score 1 · Accepted Answer

It should not have a fixed size, The implementation does not have a constructor stack_v_t() without parameters so according to that stack implementation the answer is wrong.

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);
};

The fixed size is due to a limitation of the implementation, not that the concept of the stack requires it. If it is implemented with arrays the size can be important but if it is implemented with linked lists no.

The method has failures that the stack class does not start:

 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;
    }

If the kind of stack you use is this other question Error class vector_t C ++ if you create a stack for 20 elements you can not use it for 21, but it is the implementation that is poor, since when exceeding the capacity it should redimension the array and what it does is give error.

According to this implementation (the code is not tested):

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;
}