用递归函数和栈操作逆序一个栈

题目描述

一个栈依次压入1、2、3、4、5，那么从栈顶到栈底分别为5、4、3、2、1。将这个栈转置后，从栈顶到栈底为1、2、3、4、5，也就是实现栈中元素的逆序，但是只能运用递归函数来实现，不能使用其他数据结构。

image

分析

我们知道递归实质也是一种栈，要通过递归来实现压入5、4、3、2、1，那么递归中获得这些数据的顺序应该是1、2、3、4、5，也就是需要依次获得原栈的栈底元素。

而获得栈底元素也可以通过另一个递归来实现。

于是我们可以通过两个递归函数来实现整个过程：

public class Solution {
    public int getLast(Stack<Integer> s) {
        int current = s.pop();
        if(s.isEmpty()) {
            return current;
        }
        else {
            int last = getLast(s);
            s.push(current);
            return last;
        }
    }
    public void reverse(Stack<Integer> s) {
        if(s.isEmpty()) {
            return;
        }
        else {
            int current = getLast(s);
            reverse(s);
            s.push(current);
        }
    }
}

函数getLast来获得原栈的栈底元素，将栈底元素从原栈中删除且不破坏其他元素。

函数reverse依次获得栈底元素，通过递归特性将最先获得的元素最后压入，最后获得元素最先压入。