python-翻转栈中的元素-递归法

给定一个栈stack，利用较低的空间复杂度将栈中的元素位置翻转。

这里我用了两个递归实现，外层递归：每次调用除栈顶以外的子栈；内层递归：将栈低元素移到栈顶，直到栈中只有一个元素。

这个思想是：每次递归调用当前栈除弹出栈顶元素的子栈，每一次都将这个栈的栈底元素放到栈顶，其他元素不变；然后保存这个栈顶，这个栈顶其实是最初栈的栈底元素；在调用除了这个栈顶元素的子栈，继续把栈底元素拿到栈顶，保存这个栈顶，这个栈顶是倒数第二个栈底元素。然后一直递归下去，直到栈为空。

说它是两个递归是因为在把栈底元素放到栈顶的这个操作也是用递归实现的。

学了一整天，lay了。就这样吧，反正我理解了。这种方法时间复杂度较高，达到了O(n^2)，但是空间复杂度是O(n)。时间换空间。

class LNode:
    def __init__(self,arg):
        self.data=arg
        self.next=None
class MyStack:
    #模拟栈
    def __init__(self):
        #phead=LNode(None)
        self.data=None
        self.next=None
    #判断栈是否为空,如果为空返回True，否则返回false
    def isEmpty(self):
        if self.next is None:
            return True
        else:
            return False
    #返回栈的大小
    def size(self):
        size=0
        p=self.next
        while p is not None:
            size+=1
            p=p.next
        return size
    #返回栈顶元素
    def top(self):
        if not self.isEmpty():
            return self.next.data
        else:
            print("栈为空")
            return None

    #返回栈底元素
    def bottom(self):
        if not self.isEmpty():
            p=self.next
            while p.next is not None:
                p=p.next
            return p.data
        else:
            print("栈为空")
            return None
    #弹栈
    def pop(self):
        if not self.isEmpty():
            p=self.next
            self.next=self.next.next
            print("弹栈成功")
            return p.data
        else:
            print("栈已为空")
            return None
    #压栈
    def push(self,item):
        tmp=LNode(item)
        p=self.next
        self.next=tmp
        tmp.next=p
        print("入栈成功")
    #清空栈
    def destroy(self):
        self.next=None
        print("栈已清空")

    # 打印栈
    def showStack(self):
        p = self.next
        while p is not None:
            print(p.data)
            p = p.next

"""
功能：将栈底元素移至栈顶
"""
def MoveBottomToTop(stack):
    #保存栈顶元素
    StackTop=stack.top()
    #弹出栈顶元素
    stack.pop()
    #处理不包含栈顶元素的子栈
    if not stack.isEmpty():
        MoveBottomToTop(stack)
        SonStackTop=stack.top()
        stack.pop()
        #交换栈顶与子栈顶元素
        stack.push(StackTop)
        stack.push(SonStackTop)
    else:
        stack.push(StackTop)
"""
功能：递归调用除栈顶以外的子栈
"""
def RecursionInvokoingSonStark(stack):
    if not stack.isEmpty():
        #保存栈顶元素
        MoveBottomToTop(stack)
        StackTop=stack.top()
        #弹出栈顶元素
        stack.pop()
        print("\n")
        #递归调用除栈顶以外的子栈
        RecursionInvokoingSonStark(stack)
        stack.push(StackTop)
    else:
        return

        
if __name__ == '__main__':
    stack=MyStack()
    a="abcdefg"
    #将“abcdefg"存栈中
    for i in a:
        stack.push(i)
    #打印栈中元素---从后往前
    stack.showStack()
    #递归调用
    RecursionInvokoingSonStark(stack)
    print("\n")
    #打印栈中元素---从后往前
    stack.showStack()

这以前的代码写的是真的丑啊!
lay了，lay了，不写了。睡觉了。@！！！！