題目：
一個棧依次壓入 1送矩、2蚕甥、3、4栋荸、5菇怀，那么從棧頂?shù)綏５追謩e為5、4蒸其、3、2库快、1.將這個棧轉(zhuǎn)置后摸袁，從棧頂?shù)綏５椎?、2义屏、3靠汁、4、5闽铐，也就是實現(xiàn)棧中元素的逆序蝶怔。
要求：
只能使用遞歸函數(shù)，不能使用其他數(shù)據(jù)結(jié)構(gòu)
思路：
我們需要設(shè)計兩個遞歸方法
遞歸函數(shù)一：用來把棧底元素返回并移除getAndRemoveLastElement()方法的示意圖.png
遞歸函數(shù)二：也就是題目要求寫的遞歸函數(shù)兄墅，逆序一個棧reverse()方法的示意圖.png
代碼演示
package com.itz.zcy.stackAndQueue;
import java.util.Stack;
/**
* 一個棧依次壓入 1踢星、2、3隙咸、4沐悦、5，那么從棧頂?shù)綏５追謩e為5五督、4藏否、3、2充包、1.將這個棧轉(zhuǎn)置后副签，
* 從棧頂?shù)綏５椎?、2基矮、3缘薛、4严肪、5，也就是實現(xiàn)棧中元素的逆序。
* 只能使用遞歸函數(shù)立润，不能使用其他數(shù)據(jù)結(jié)構(gòu)
*/
public class ReverseStack {
private static Stack<Integer> stack = new Stack<>();
public static void main(String[] args) {
stack.push(1);
stack.push(2);
stack.push(3);
stack.push(4);
stack.push(5);
reverse(stack);
for (int i=0;i<5;i++){
System.out.println(stack.pop());
}
}
/**
* 該方法返回棧底元素并移除
*
* @param stack 要查找的棧
* @return 返回的棧底元素
*/
private static int getAndRemoveLastElement(Stack<Integer> stack) {
int result = stack.pop();
if (stack.isEmpty()) {
return result;
} else {
int last = getAndRemoveLastElement(stack);
stack.push(result);
return last;
}
}
/**
* 棧逆序方法
* @param stack 需要逆序的棧
*/
public static void reverse(Stack<Integer> stack) {
if (stack.isEmpty()) {
return;
}
int i = getAndRemoveLastElement(stack);
reverse(stack);
stack.push(i);
}
}
總結(jié)
該方法實現(xiàn)較為簡單，使用遞歸對空間和時間就是一個考驗
文獻：左程云著 《程序員代碼面試指南IT名企算法與數(shù)據(jù)結(jié)構(gòu)題目最優(yōu)解》（第二版）
版權(quán)聲明：此文版權(quán)歸作者所有矢沿！
