如何仅用递归函数和栈操作逆序一个栈

    • 题目：

      一个栈依次压入1，2，3，4，5，那么从栈顶到栈底分别为5，4，3，2，1。将这个栈转置后，从栈顶到栈底为1，2，3，4，5，也就是实现栈中元素的逆序 但是只能用递归函数来实现，不能用其他数据结构。

    • 解题思路

      getAndRemoveLastElement取出栈中的最后一个元素并在栈中移除；实现就是将栈中元素全部出栈，然后在入栈

    __reverse调用上面的函数，不停的将最后一个元素移出来，全部移除后入栈，逆序。

    • 代码实现

      1. class Stack_Reverse:
      2.   def __init__(self, _stack):
      3.       self._stack = _stack
      5.   @property
      6.   def reverse(self):
      7.       self._reverse(_stack=self._stack)
      9.   def _reverse(self, _stack):
      10.       """逆序一个栈"""
      11.       if not _stack:
      12.           return
      13.       else:
      14.           i = self._getAndRemoveLastElement(_stack)
      15.           self._reverse(_stack)
      16.           _stack.append(i)
      18.   def _getAndRemoveLastElement(self, _stack):
      19.       """将栈stack的栈底元素返回并移除"""
      20.       result = _stack.pop()
      21.       if not _stack:
      22.           return result
      23.       else:
      24.           last = self._getAndRemoveLastElement(_stack)
      25.           _stack.append(result)
      26.           return last
      28.   def __str__(self):
      29.       return str(self._stack)
    • 测试代码
      1. if __name__ == '__main__':
      2.   stack = [1, 2, 3, 4, 5]
      3.   New_Stack_Reverse = Stack_Reverse(stack)
      4.   New_Stack_Reverse.reverse
      5.   print(New_Stack_Reverse.__str__()) 
      6.   # [5, 4, 3, 2, 1]