4.4.5 实践演练——使用顺序表方法和单链表方法实现栈

书名：Python算法详解
作者名：张玲玲
本章字数：273字
更新时间：2020-06-27 17:50:52

4.4.5 实践演练——使用顺序表方法和单链表方法实现栈

在Python程序中，栈可以用顺序表方式实现，也可以用链表方式实现。因为Python的内建数据结构太强大，可以用列表直接实现栈，这个方法比较简单快捷。下面的实例文件liazhan.py演示了使用顺序表方法和单链表方法实现栈的过程。

源码路径：daima\第4章\liazhan.py

#链表节点
class Node(object):
     def __init__(self, elem, next_ = None):
          self.elem = elem
          self.next = next_
#用顺序表实现栈
class SStack(object):
     def __init__(self):
          self._elems = []
     def is_empty(self):
          return self._elems == []
     def top(self):
          if self.is_empty():
                raise StackUnderflow
          return self._elems[-1]
     def push(self, elem):
          self._elems.append(elem)
     def pop(self):
          if self.is_empty():
                raise StackUnderflow
          return self._elems.pop()
#用链表实现栈
class LStack(object):
     def __init__(self):
         self._top = None
     def is_empty(self):
          return self._top is None
     def top(self):
          if self.is_empty():
                raise StackUnderflow("in LStack.top()")
          return self._top.elem
     def push(self, elem):
         self._top = Node(elem, self._top)
     def pop(self):
          if self.is_empty():
                raise StackUnderflow("in LStack.pop()")
          result = self._top.elem
          self._top = self._top.next
          return result
if __name__=="__main__":
     st1 = SStack()
     st1.push(3)
     st1.push(5)
     while not st1.is_empty():
         print(st1.pop())
     print("============")
     st2 = LStack()
     st2.push(3)
     st2.push(5)
     while not st2.is_empty():
         print(st2.pop())

执行后会输出：

5
3
============
5
3