~~~
package stackAndQueue;
import java.util.Stack;
import org.junit.Test;
/**
* 僅用遞歸函數和棧逆序一個棧：ReverseStack【2】
*
* 【一個棧依次壓入1、2、3，將棧轉置，使棧頂到棧底依次是1、2、3，只能用遞歸函數，不能借用額外的數據結構包括棧】
*
* 算法思想：兩個遞歸函數（getAndRemoveBottom、reverse）
*
* @author xiaofan
*/
public class ReverseStack {
/**
* 返回并移除當前棧底元素（棧內元素<棧底>1、2、3<棧頂>變為2、3<棧頂>）.
*/
private int getAndRemoveBottom(Stack<Integer> stack) {
int result = stack.pop();
if (stack.empty()) {
return result;
} else {
int bottom = getAndRemoveBottom(stack);
stack.push(result);
return bottom; // 第一輪時，返回棧底元素1
}
}
/**
* 每層遞歸取出棧底的元素并緩存到變量中，直到棧空；
*
* 然后逆向將每層變量壓入棧，最后實現原棧數據的逆序。
*
* @param stack
*/
public void reverse(Stack<Integer> stack) {
if (stack.empty()) {
return;
}
int i = getAndRemoveBottom(stack); // 依次返回1、2、3
reverse(stack);
stack.push(i); // 依次壓入3、2、1
}
///////// 測試方法////////
@Test
public void test() {
Stack stack = new Stack(); // Stack繼承Vector，默認容量是10
stack.push(1);
stack.push(2);
stack.push(3);
ReverseStack rStack = new ReverseStack();
rStack.reverse(stack);
while (!stack.empty()) {
System.out.println(stack.pop());
}
}
}
~~~
代碼地址：[https://github.com/zxiaofan/Algorithm/blob/master/src/stackAndQueue/ReverseStack.java](https://github.com/zxiaofan/Algorithm/blob/master/src/stackAndQueue/ReverseStack.java)
