recursive algorithm java stacks

Question

recursive algorithm java stacks

Navigation

#1 by (1 votes)
#2 by (0 votes)

0

someone can explain to me how this exercise works. I can not understand it well. When you enter the reverseStack method, you call the reverseStack method again when you execute the next line, which is a call to another method?

  import java.util.Stack;

class Exercise2 {
  public static<T> void reverseStack (Stack<T> p){
  T e;
   if (!p.empty()) {
    e=p.pop();
    reverseStack(p);
    pushBottom (p,e);
  }
}
public static<T> void pushBottom (Stack<T> p, T e){
  T a;
  if (!p.empty()){
     a=p.pop();
     pushBottom(p,e);
     p.push(a);
   }
else {
    p.push(e);
}
}
public static void main(String[] args){
   Stack s = new Stack ();
   int n=10;
   for (int i=0; i<n; i++){
     s.push(i);
  }

   System.out.println(("Initial stack\n"+ s.toString()));
   reverseStack(s);
   System.out.println(("Final stack\n"+ s.toString()));
 }
}

java

asked by gabriel gomez 04.01.2017 в 21:17

source

2 answers

Obtain user information with APDU commands - Login Priority queue in java

score 1 · Answer 1

Your problem is a simple problem of recursion, to your question, the code will enter the method reverseStack and return to it until the stack has been emptied, from there will be executed 10 pushBottom of such so that this method ends up leaving the elements in reverse.

It is a very bad example to understand the recursion since in addition the complexity of this algorithm could be improved in the following way:

public static<T> void reverseStack (Stack<T> p){
  Stack<T> otraPila = new Stack(); // Creo una nueva pila vacia
  while(!p.empty()) // Mientras quedan elementos
      otraPila.push(p.pop()); // Los meto en la otra pila
  p = otraPila;
}

Or with a recursive algorithm

public static<T> void reverseStack(Stack<T> p){
  Stack<T> otraPila = new Stack();
  reverseStackRec(p, otraPila);
  p = otraPila;
}

public static<T> void reverseStackRec(Stack<T> p, Stack<T> p2){
  if(!p.empty()){
      p2.push(p.pop());
      reverseStackRec(p, otraPila);
  }
}

So you can also see in a somewhat visual way what this recursion consists of:

As you can see in the image, your code will enter 10 times in reverseStack (Call 1, 2 ...) and will return another time 10 times calling pushBotton (Returns 1, 2 ...)

then when you execute the next line that is a call to another method?

When it finishes executing the recursions and the states of the Java recursion stack are retrieved and the execution of the code continues.

score 0 · Answer 2

public static<T> void reverseStack (Stack<T> p){
  T e;
   if (!p.empty()) {
    e=p.pop();
    reverseStack(p);
    pushBottom (p,e);
  }

1) condition if (!p.empty()) { checks if it is not empty, in   case of success takes out an element of the Stack

2) e=p.pop(); flame   again to the method until the Stack is empty

3) reverseStack(p); reverts the Stack

4) pushBottom (p,e); insert   the elements removed from step 1 to the inverted Stack