栈中的元素都是后进先出(Last In First Out, LIFO).用列表可以实现一个栈类。
栈可以在函数调用时存储断点,做递归时也需要用栈。
class StackUnderflow(ValueError): """ 这个是 ValueError的子类,可以抛出自定义的异常 """ pass class SStack(): def __init__(self): self.elems = [] def is_empty(self): return self.elems == [] def top(self): # 取得栈里最后压入的元素,但不删除 if self.elems == []: raise StackUnderflow('in SStack.top()') return self.elems[-1] def push(self, elem): self.elems.append(elem) def pop(self): if self.elems == []: raise StackUnderflow('in SStack.pop()') return self.elems.pop() if __name__ == '__main__': s = SStack() s.push(6) s.push(8) print(s.pop())以上基于列表的栈类不会出现栈满的情况。但是考虑到列表有两个特点:扩大存储需要做一次高代价操作,此外其需要完整的大块的存储区域。可以用基于链表的栈类,来优化以上两个问题。
基于链表来构建栈类,用表头作为栈顶,表尾作为栈底。这样能得到较高的效率。
class StackUnderflow(ValueError): pass class Node: def __init__(self, elem, pnext=None): self.elem = elem self.pnext = pnext class LStack(): def __init__(self): self.top = None def is_empty(self): return self.top is None def top(self): if self.top is None: raise StackUnderflow('in LStack.top()') return self.top.elem def push(self, elem): self.top = Node(elem, self.top) def pop(self): if self.top is None: raise StackUnderflow('in LStack.pop()') p = self.top self.top = p.pnext return p.elem if __name__ == '__main__': s = LStack() s.push(6) s.push(8) print(s.pop())