首页 > 其他 > 详细

栈的倒置(递归法)

时间:2018-09-20 11:47:22      阅读:297      评论:0      收藏:0      [点我收藏+]

 

 

将栈中的元素倒置,一种最简单的办法是利用数组存储栈弹出的元素,而后再压入栈中,空间复杂度O(N),时间复杂度O(2N)。

 

另一种方法是利用递归将栈中的元素倒置。

假设原栈中的元素为

5(5在栈顶)

4

3

2

1

那么倒置后栈中的元素应为

1

2

3

4

5

 

如果已经将1,2倒置了,即栈中的元素为

1

2

如何将3压入栈低,可以先将1、2弹出,而后压入3,再依次压入2,1.

实现代码如下

    private static void push(Stack<Integer> st, int data) {
        if (st.isEmpty()) {
            st.push(data);
            return;
        }
        int temp = st.pop();
        push(st, data);
        st.push(temp);
    }

 

所以对于整个栈的实现为
将1压入栈底;

将1弹出,将2压入栈底,再将1压入栈

将1、2弹出,将3压入栈底,再依次压入2、1

将1、2、3弹出,将4压入栈底,再依次压入3、2、1.

 

 

实现代码如下

    private static void push(Stack<Integer> st, int data) {
        if (st.isEmpty()) {
            st.push(data);
            return;
        }
        int temp = st.pop();
        push(st, data);
        st.push(temp);
    }

    public static void reverseStack(Stack<Integer> st) {
        if (st.isEmpty()) return;
        int temp = st.pop();
        reverseStack(st);
        push(st, temp);
    }

 

复杂度分析

空间复杂度是O(N),不是O(1),这时由于递归函数reverseStack每次调用时都会产生变量temp=st.pop(),这些变量会存储在栈中,同样占用空间。

 

时间复杂度是O(N^2)

每次调用push()函数,都会将栈中的元素弹出,在压入,这个过程会进行N次。

 

故栈的倒置,最简单的数组法,也是复杂度最低的。

 

栈的倒置(递归法)

原文:https://www.cnblogs.com/deltadeblog/p/9679911.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!