如何遞歸交換堆棧的頂部元素到底部

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