Yxd's Blog

个人博客

0%

递归反转栈

发表于 更新于 分类于 Valine：

题目描述

翻转栈的所有元素，例如输入栈 {1,2,3,4,5}，其中 1 处在栈顶，翻转之后的栈为 {5,4,3,2,1}，其中，5 处在栈顶，注意使用递归

解题思路

递归算法不需要考虑中间过程，上一层的递归可以直接使用下一层的递归结果，即假设下一层已经完成了我们的要求就行了，最后只需要考虑最后一层递归退出的条件就行了


递归函数结束的条件：是当栈为空或者栈里只有一个元素的时候，return。

解题代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
def reverse_stack(s):
    if not s:
        return
    if len(s) == 1:
        return
    temp1 = s.pop()
    reverse_stack(s)
    temp2 = s.pop()
    reverse_stack(s)
    s.append(temp1)
    reverse_stack(s)
    s.append(temp2)
    return


if __name__ == '__main__':
    stack = [1, 2, 3, 4, 5]
    reverse_stack(stack)
    print('翻转后出栈的顺序为：')
    print(stack)