使用递归函数逆序一个栈

原题(来源:牛客网)

一个栈依次压入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/

发表回复

登录后才能评论