Wie rekursiv das oberste Element des Stapels nach unten tauschen

Question

Ich frage mich, wie das oberste Element eines Stapels rekursiv nach unten vertauschen. Der Stapel sollte am Ende wie folgt suchen:

4 (top) 
3 
2 
1 

wird

3 (top) 
2 
1 
4 

ich die rekursive Funktion die Reihenfolge des Stapels rückgängig herausgefunden. Aber ich versuche, es nur für einen zu tun. Ich gehe davon aus, dass es etwas mit der Änderung des Basisfalls zu tun hat.

public void roll() { 

    if (!isEmpty()){ 
     E temp = getBottom(this); 
     roll(); 
     this.push(temp); 
    } 

} 

private E getBottom(LinkedStack<E> p){ 
    E temp = p.pop(); 
    if (p.isEmpty()){ 
     return temp; 
    } else { 
     E temp2 = getBottom(p); 
     p.push(temp); 
     return temp2; 
    } 
} 

Answer 1

Ich würde es vorziehen, eigentlich ist es iterativ tun, aber da Sie rekursiv angegeben haben, können Sie es tun, indem Sie die Stapelumkehr und dann teilweise wieder rückgängig zu machen. Auch ist einfacher nur direkt an das oberste Element auf dem Boden senden:

public void sendTopToBottom() { 

    if (!isEmpty()){ 
     sendToBottom(pop()); 
    } 

} 

private void sendToBottom(E victim){ 
    if (isEmpty()){ 
     push(victim); 
    } else { 
     E temp = pop(); 
     sendToBottom(victim); 
     push(temp); 
    } 
} 

Answer 2

Sie nur die oberen beiden Elemente tauschen müssen und dann das zweite obere Element außerhalb verlassen, nachdem tauschte alle Elemente dann wieder das Element schieben. Zum Beispiel:

public void roll(Stack<Integer> stack) { 
     if (stack.size() <= 1) { 
      return; 
     } 
     Integer top1 = stack.pop(); 
     Integer top2 = stack.pop(); 
     stack.push(top1); 
     roll(stack); 
     stack.push(top2); 
    }