스택의 맨 위 요소를 아래쪽으로 재귀 적으로 교환하는 방법

Question

스택의 맨 위 요소를 맨 아래로 재귀 적으로 스왑하는 방법을 알고 싶습니다. 스택이처럼 보이는 결국해야합니다

4 (top) 
3 
2 
1 

내가 스택의 순서를 반대로하는 재귀 함수를 알아 냈

3 (top) 
2 
1 
4 

된다. 그러나 나는 단지 그것을 위해 노력하는 것에 붙어있다. 기본 케이스를 변경하는 것과 관련이 있다고 가정합니다.

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

는 사실은 반복적으로 그 일을 선호하지만 재귀 적으로 지정한 이후, 당신은 다시 반전 부분적으로 다음 스택을 반대하고 그것을 할 수 있습니다. 심지어 간단한은 직접 바닥에 최상위 요소를 보내는 것입니다 : 당신은 상단 두 요소를 교환 한 후 외부에서 두 번째 최고 요소를 탈퇴 한 후 모든 요소가 다시 그 요소를 밀어 교환이 필요

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

. 예 :

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