江苏龙网

  1. 主页 > 生活百科 > >

Python 实现栈的几种方式及其优劣

Python

本文介绍了栈这一数据结构，并介绍了在现实生活中的程序中如何使用它的情况 。在文章的中，介绍了 Python/ target=_blank class=infotextkey>Python 中实现栈的三种不同方式，知道了 对于非多线程程序是一个更好的选择，如果你要在多线程编程环境中使用栈的话，可以使用。1 栈的概念栈由一系列对象对象组织的一个集合，这些对象的增加和删除操作都遵循一个“后进先出”（Last In First Out，LIFO）的原则 。
在任何时刻只能向栈中插入一个对象，但只能取得或者删除只能在栈顶进行 。比如由书构成的栈，唯一露出封面的书就是顶部的那本，为了拿到其他的书，只能移除压在上面的书，如图：

Python 实现栈的几种方式及其优劣

文章插图
栈的实际应用实际上很多应用程序都会用到栈，比如：
  • 网络浏览器将最近浏览的网址存放在一个栈中 。每当用户访问者访问一个新网站时，这个新网站的网址就被压入栈顶 。这样，每当我们在浏览器单击"后退"按钮时（或者按键盘快捷键  ，大部分撤销快捷键），就可以弹出当前最近一次访问的网址，以回到其先前访问的浏览状态 。CTRL+Z
  • 文本编辑器通常会提供一个"撤销"机制以取消最近的编辑操作并返回到先前状态 。这个撤销操作也是通过将文本的变化状态保存在一个栈中得以实现 。
  • 一些高级语言的内存管理，JVM 的栈、Python 栈还用于内存管理、嵌套语言特性的运行时环境等
  • 回溯（玩游戏，寻找路径，穷举搜索）
  • 在算法中使用，如汉诺塔、树形遍历、直方图问题，也用于图算法，如拓扑排序
语法处理：
  • 参数和局部变量的空间是用堆栈在内部创建的 。编译器对大括号匹配的语法检查对递归的支持在编译器中像后缀或前缀一样的表达式
2 栈的抽象数据类型任何数据结构都离不开数据的保存和获得方式，如前所述，栈是元素的有序集合，添加和操作与移除都发生在其顶端（栈顶），那么它的抽象数据类型包括：
  • Stack():创建一个空栈，它不需要参数，且会返回一个空栈
  • push(e)：将一个元素 e 添加到栈 S 的栈顶，它需要一个参数 e，且无返回值
  • pop(): 将栈顶端的元素移除，它不需要参数，但会返回顶端的元素，并且修改栈的内容
  • top(): 返回栈顶端的元素，但是并不移除栈顶元素；若栈为空，这个操作会操作
  • is_empty(): 如果栈中不包含任何元素，则返回一个布尔值True
  • size()：返回栈中元素的数据 。它不需要参数，且会返回一个整数 。在 Python 中，可以用 这个特殊方法实现 。__len__

Python 实现栈的几种方式及其优劣

文章插图
Python 栈的大小可能是固定的，也可能有一个动态的实现，即允许大小变化 。在大小固定栈的情况下，试图向已经满的栈添加一个元素会导致栈溢出异常 。同样，试图从一个已经是空的栈中移除一个元素，进行  操作这种情况被称为下溢 。pop()
3 用 Python 的列表实现栈在学习 Python 的时候，一定学过 Python 列表，它能通过一些内置的方式实现栈的功能：list
  • 通过  方法用于添加一个元素到列表尾部，这种方式就能模拟  操作Appendpush()
  • 通过  方法用于模拟出栈操作pop()
  • 通过  模拟 操作L[-1]top()
  • 通过判断  模拟  操作len(L)==0isEmpty()
  • 通过  函数实现  函数len()size()

Python 实现栈的几种方式及其优劣

文章插图
代码如下：
class ArrayStack:""" 通过 Python 列表实现 LIFO 栈"""def __init__(self):self._data = https://www.isolves.com/it/cxkf/yy/Python/2023-05-08/[]def size(self):""" return the number of elements in the stack"""return len(self._data)def is_empty(self):""" return True if the stack is empty"""return len(self._data) == 0def push(self, e):""" add element e to the top of the stack"""self._data.append(e)def pop(self):""" remove and return the element from the top of the stack"""if self.is_empty():raise Exception('Stack is empty')return self._data.pop()def top(self):"""return the top of the stackRaise Empty exception if the stack is empty"""if self.is_empty():raise Exception('Stack is empty')return self._data[-1]# the last item in the listarrayStack = ArrayStack()arrayStack.push("Python")arrayStack.push("Learning")arrayStack.push("Hello")print("Stack top element: ", arrayStack.top())print("Stack length: ", arrayStack.size())print("Stack popped item: %s" % arrayStack.pop())print("Stack is empty?", arrayStack.is_empty())arrayStack.pop()arrayStack.pop()print("Stack is empty?", arrayStack.is_empty())# arrayStack.pop()


推荐阅读


上一篇：从简单到复杂，密码学让我们的信息更安全

下一篇：除了推出大模型，AI发展还应做什么