Description

实现一个栈的逆序，但是只能用递归函数和这个栈本身的pop操作来实现，而不能自己申请另外的数据结构。

给定一个整数数组A即为给定的栈，同时给定它的大小n，请返回逆序后的栈。

测试样例：

[4,3,2,1],4
返回：[1,2,3,4]

Solutions

1. Recursion

　　

# -*- coding:utf-8 -*-
# Time: O(n^2)
# Space: O(1)
class StackReverse:
    def get(self, stack):
        """remove the number on the bottom and return it"""
        top = stack.pop()
        if not stack:
            return top
        else:
            bottom = self.get(stack)
            stack.append(top)
            return bottom

    def reverseStack(self, stack, n):
        if not stack:
            return
        bottom = self.get(stack)
        self.reverseStack(stack, n-1)
        stack.append(bottom)
        return stack

References

  1. 4.5 递归实现栈反转