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

1.题目

一个栈依次压入1,2,3,4,5之后,那么从栈底到栈顶的顺序为:1,2,3,4,5,将这个栈倒置之后,栈底到栈顶的顺序为5,4,3,2,1,整个过程只能使用递归函数来实现,不能用其他数据结构

2.解答

需要设计两个递归函数,一个是getAndRemoveLastElement,用来返回每次栈底数据,得到之后进行返回,并将之前弹出来的数据重新压入栈中

image

另外一个是reverse,得到栈底元素,再将栈进行倒置,递归进行,直到栈中没有元素时,再将各个栈底 i 依次压入,实现了导入功能。

总的来说还是使用了两个栈的,其中一个是显式的stack,另外递归函数都是在一个栈里面进行返回的,那么要实现倒序功能,就要使stack栈和递归函数栈中的元素顺序是一样的,这样再将递归函数栈里面的元素压入stack栈时,才能实现倒序功能,这道题聪明的做法就是使用另外一个递归函数用来获得每一次栈底元素。

image

package java1;

import java.util.Stack;

public class Solution {
    //获得当前栈的栈底元素,并返回
    private Stack<Integer> stack;
    public Solution(){
        stack = new Stack<>();
        stack.push(1);
        stack.push(2);
        stack.push(3);
    }
    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;
        }
    }
    public void reverse(Stack<Integer> stack){
        if(stack.isEmpty())
            return;
        int i = getAndRemoveLastElement(stack);
        reverse(stack);
        stack.push(i);
    }
}