栈的代码实现（python语言）

缺乏、安全感 2022-05-24 11:58 150阅读 0赞

- 栈和队列都是（临时性的）保存数据元素的容器
     - 栈是保证缓冲元素后进先出
     - 队列是保证缓冲元素的先进先出

*  栈

# 定义一个连续表（list）实现的栈
    class ContinuityStack():
        def __init__(self):  # 建立空栈
            self.elems = []
    
        def is_empty(self):  # 栈的判空
            return self.elems == []
    
        def top(self):  # 取当前（最新）元素的值，不删除
            if self.elems == []:
                raise StackUnderflow
            return self.elems[len(self.elems)-1]
    
        def push(self, elem):  # 栈的压入
            self.elems.append(elem)
    
        def pop(self):  # 尾端弹出元素
            if self.elems == []:
                raise StackUnderflow
            return self.elems.pop()  # 空栈时报错
    
    
    # 采用链接技术，实现一个链接栈
    class LinkStack():
        def __init__(self):  # 建立链表
            self.top = None
    
        def is_empty(self):  # 链表的判空
            return self.top is None
    
        def top(self):  # 取当前（最新）元素的值，不删除
            if self.elems == []
                raise StackUnderflow
            return self.top.elem
    
        def push(self, elem):  # 栈的压入
            self.top = LinkStack(elem, self.top)
    
        def pop(self):  # 尾端删除元素
            if self.top is None:
                raise StackUnderflow
            p = self.top()
            self.top = p.next
            return p.elem

*  应用举例

# 括号配对问题
    def check_pares(text):
        pares = "()[]{}"
        open_pares = "([{"
        opposite = {
       ")": "(", "]": "[", "}": "{"}  # 表示配对关系的字典
    
        def pare_theses(text):  # 括号生成器
            i,text_len = 0,len(text)
            while True:
                while i<text_len and text[i] not in pares:
                    i += 1
                    if i>=text_len:
                        return
                    yield text[i],i
                    i += 1
    
        st = ContinuityStack()
        for pr,i in pare_theses(text):  # 对text里各括号和位置迭代
            if pr in open_pares:  # 开括号，压进栈并继续
                st.push(pr)
            elif st.pop() != opposite[pr]  # 不匹配就是失败，退出
                print("Unmatching is found at",i,"for",pr)
                return False
            # else # 是一次括号配对成功，不执行，继续
        print("All pare_theses are correctly matched.")
        return True

*  用栈来解决递归问题

# 递归函数
    def fact(n):
        if n == 0:
            return 1
        else:
            return n * fact(n - 1)
    
    
    # 用自己定义的栈模拟系统的运行栈
    def norec_fact(n):
        res = 1
        st = LinkStack()  # st为链表类的栈
        while n > 0:  # 栈的压入
            st.push()
            n -= 1
        while not st.is_empty():  # 尾端弹出元素
            res *= st.pop()
        return res  # 返回所有栈元素的乘积