原题（来源：牛客网）
一个栈依次压入1,2,3,4,5那么从栈顶到栈底分别为5,4,3,2,1。将这个栈转置后，从栈顶到栈底为1,2,3,4,5，也就是实现了栈中元素的逆序，请设计一个算法实现逆序栈的操作，但是只能用递归函数来实现，而不能用另外的数据结构。
解法
思想
设计一个函数getAndRemoveLastElement用于获取并移除栈底元素，当栈空的时候进行回溯，并将获取的元素压入栈，就能达到逆序的效果。
这样做的时间复杂度肯定是没一个辅助队列来的快的，好处是没有使用额外的空间（除了递归栈空间）
时间复杂度计算：设栈的大小为n，每一次获取栈底元素的时间复杂度是O(n)，栈的大小要从n->0，就是O(n)+O(n-1)+O(n-2)+...+O(1)=O(n^2)
代码
class Solution {
public void reverse(Stack<Integer> stack){
if(stack.isEmpty()){
return;
}
//每次获取栈底元素，最后一次获取的即是栈顶元素
int i = getAndRemoveLastElement(stack);
reverse(stack);
//回溯的时候将获取的元素压入
stack.push(i);
}
public int getAndRemoveLastElement(Stack<Integer> stack){
//获取并移除栈顶元素
int result = stack.pop();
//获取栈底元素
if(stack.isEmpty()){
return result;
}else{
int last = getAndRemoveLastElement(stack);
//回溯的时候将获取的元素压入
stack.push(result);
return last;
}
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/%e4%bd%bf%e7%94%a8%e9%80%92%e5%bd%92%e5%87%bd%e6%95%b0%e9%80%86%e5%ba%8f%e4%b8%80%e4%b8%aa%e6%a0%88/
