1. 代码段小站首页
  2. 算法

使用递归函数逆序一个栈

彭晨涛 • • 算法 • 阅读 25

原题（来源：牛客网）

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

赞 (0)
彭晨涛彭晨涛管理者
0 0
上一篇 2020年4月19日 14:09
下一篇 2020年4月20日 15:03

相关推荐

发表回复

登录后才能评论