Comment échanger récursivement l'élément supérieur de la pile vers le bas

Question

Je me demande comment échanger de façon récursive l'élément supérieur d'une pile vers le bas. La pile devrait finir par ressembler à ceci:

4 (top) 
3 
2 
1 

devient

3 (top) 
2 
1 
4 

je me suis dit la fonction récursive pour inverser l'ordre de la pile. Mais je suis coincé à essayer de le faire pour un seul. Je suppose que cela a quelque chose à voir avec la modification du scénario de base.

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

Je serait en fait préférer le faire de manière itérative, mais depuis que vous avez spécifié récursive, vous pourriez le faire en inversant la pile, puis partiellement inverser à nouveau. Encore plus simple est de simplement envoyer directement l'élément haut en bas:

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

Vous ne devez échanger les deux premiers éléments, puis laisser le second élément supérieur à l'extérieur, après permutés tous les éléments puis pousser cet élément arrière. Par exemple:

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