首页 > 编程语言 >python:栈的理解与应用

python:栈的理解与应用

时间:2023-01-12 12:08:48浏览次数:39  
标签:入栈 python 复杂度 数组 链表 括号 理解 应用 操作


如何理解“栈”?

关于“栈”,我有一个非常贴切的例子,就是一摞叠在一起的盘子。我们平时放盘子的时候,都是从下往上一个一个放;取的时候,我们也是从上往下一个一个地依次取,不能从中间任意抽出。后进者先出,先进者后出,这就是典型的“栈”结构。

 

python:栈的理解与应用_字符串

 

从栈的操作特性上来看,栈是一种“操作受限”的线性表,只允许在一端插入和删除数据。

我第一次接触这种数据结构的时候,就对它存在的意义产生了很大的疑惑。因为我觉得,相比数组和链表,栈带给我的只有限制,并没有任何优势。那我直接使用数组或者链表不就好了吗?为什么还要用这个“操作受限”的“栈”呢?

事实上,从功能上来说,数组或链表确实可以替代栈,但你要知道,特定的数据结构是对特定场景的抽象,而且,数组或链表暴露了太多的操作接口,操作上的确灵活自由,但使用时就比较不可控,自然也就更容易出错。

当某个数据集合只涉及在一端插入和删除数据,并且满足后进先出、先进后出的特性,我们就应该首选“栈”这种数据结构。

如何实现一个“栈”?

从刚才栈的定义里,我们可以看出,栈主要包含两个操作,入栈和出栈,也就是在栈顶插入一个数据和从栈顶删除一个数据。理解了栈的定义之后,我们来看一看如何用代码实现一个栈。

实际上,栈既可以用数组来实现,也可以用链表来实现。用数组实现的栈,我们叫作顺序栈,用链表实现的栈,我们叫作链式栈

不管是顺序栈还是链式栈,我们存储数据只需要一个大小为 n 的数组就够了。在入栈和出栈过程中,只需要一两个临时变量存储空间,所以空间复杂度是 O(1)。

注意,这里存储数据需要一个大小为 n 的数组,并不是说空间复杂度就是 O(n)。因为,这 n 个空间是必须的,无法省掉。所以我们说空间复杂度的时候,是指除了原本的数据存储空间外,算法运行还需要额外的存储空间。

空间复杂度分析是不是很简单?时间复杂度也不难。不管是顺序栈还是链式栈,入栈、出栈只涉及栈顶个别数据的操作,所以时间复杂度都是 O(1)。

支持动态扩容的顺序栈

如果要实现一个支持动态扩容的栈,我们只需要底层依赖一个支持动态扩容的数组就可以了。当栈满了之后,我们就申请一个更大的数组,将原来的数据搬移到新数组中。

 

python:栈的理解与应用_链表_02

 

实际上,支持动态扩容的顺序栈,我们平时开发中并不常用到。

入栈、出栈的时间复杂度:

对于出栈操作来说,我们不会涉及内存的重新申请和数据的搬移,所以出栈的时间复杂度仍然是 O(1)。但是,对于入栈操作来说,情况就不一样了。当栈中有空闲空间时,入栈操作的时间复杂度为 O(1)。但当空间不够时,就需要重新申请内存和数据搬移,所以时间复杂度就变成了 O(n)。

也就是说,对于入栈操作来说,最好情况时间复杂度是 O(1),最坏情况时间复杂度是 O(n)。那平均情况下的时间复杂度又是多少呢?

如果当前栈大小为 K,并且已满,当再有新的数据要入栈时,就需要重新申请 2 倍大小的内存,并且做 K 个数据的搬移操作,然后再入栈。但是,接下来的 K-1 次入栈操作,我们都不需要再重新申请内存和搬移数据,所以这 K-1 次入栈操作都只需要一个 simple-push 操作就可以完成。

 

python:栈的理解与应用_python_03

 

你应该可以看出来,这 K 次入栈操作,总共涉及了 K 个数据的搬移,以及 K 次 simple-push 操作。将 K 个数据搬移均摊到 K 次入栈操作,那每个入栈操作只需要一个数据搬移和一个 simple-push 操作。以此类推,入栈操作的均摊时间复杂度就为 O(1)。

通过这个例子的实战分析,也印证了前面讲到的,均摊时间复杂度一般都等于最好情况时间复杂度。因为在大部分情况下,入栈操作的时间复杂度 O 都是 O(1),只有在个别时刻才会退化为 O(n),所以把耗时多的入栈操作的时间均摊到其他入栈操作上,平均情况下的耗时就接近 O(1)。

栈在括号匹配中的应用

我们可以借助栈来检查表达式中的括号是否匹配。

我们同样简化一下背景。我们假设表达式中只包含三种括号,圆括号 ()、方括号[]和花括号{},并且它们可以任意嵌套。比如,{[] ()[{}]}或[{()}([])]等都为合法格式,而{[}()]或[({)]为不合法的格式。那我现在给你一个包含三种括号的表达式字符串,如何检查它是否合法呢?

这里也可以用栈来解决。我们用栈来保存未匹配的左括号,从左到右依次扫描字符串。当扫描到左括号时,则将其压入栈中;当扫描到右括号时,从栈顶取出一个左括号。如果能够匹配,比如“(”跟“)”匹配,“[”跟“]”匹配,“{”跟“}”匹配,则继续扫描剩下的字符串。如果扫描的过程中,遇到不能配对的右括号,或者栈中没有数据,则说明为非法格式。

当所有的括号都扫描完成之后,如果栈为空,则说明字符串为合法格式;否则,说明有未匹配的左括号,为非法格式。

内容小结

栈是一种操作受限的数据结构,只支持入栈和出栈操作。后进先出是它最大的特点。栈既可以通过数组实现,也可以通过链表来实现。不管基于数组还是链表,入栈、出栈的时间复杂度都为 O(1)。除此之外,我们还讲了一种支持动态扩容的顺序栈.

标签:入栈,python,复杂度,数组,链表,括号,理解,应用,操作
From: https://blog.51cto.com/u_8238263/6003936

相关文章

  • Python:类
    太久没写Python的程序了类的内容忘记了,这里写下回忆一下1Python-类属性类有一个特殊的方法叫做构造函数,用作定义实例对象的属性,其必须被命名为__innit__()(注意其前后......
  • Python-wxauto自动发送消息或文件
    1、安装wxauto和pyautogui库,pip安装即可。pipinstallwxautopipinstallpyautogui2、登录微信 3、编写代码importtimefromwxautoimportWeChatimportpya......
  • 用python虚拟环境安装jupyter notebook
    一、安装python虚拟环境以及在虚拟环境中安装jupyter1、创建python虚拟环境,命名为py_venv-onepython-m-venvpy_venv-one2、进入并激活虚拟环境进入Scripts文件夹ac......
  • Python 包离线使用
    导出本地依赖的所有包,并下载到packages目录下piplistpipfreeze>requirements.txtpipdownload-dpackages-rrequirements.txt将packages文件夹和requireme......
  • python--操作excel表格,openpyxl模块
    简介openpyxl是一个非常强大的读写Excel2010xlsx/xlsm/xltx/xltm的Python库,简单易用,功能广泛,单元格格式/图片/表格/公式/筛选/批注/文件保护等等功能应有尽有官方......
  • python false和False
    true=Falsedefwazzup():"""假亦真时真亦假"""false=TrueorFalsedeftrue():nonlocalfals......
  • tomcat 设置 ip 端口访问 以及 多应用设置
    Q:web应用想省去应用名,使用ip加端口的方式访问,怎么设置?A:使用一个巧办法,也是最省力的办法:apache->conf->server.xml中<Hostname="localhost"appBase="webapps"......
  • 局域网搭建IOS应用在线安装环境
    前言一般公司在开发IOS的APP,发布测试版本,这是一个很繁琐的过程,对于一般的公司基本上就是把测试机加入开发列表中,然后打包APP,发布到网盘,或者发到QQ上,供测试人员下载安装测试......
  • 全面了解Python的变量与基本数据类型
    (全面了解Python的变量与基本数据类型)1保留字和标识符1.1保留字保留字是Python语言中已经被赋予了特定意义的单词,写代码或开发过程中不能使用这些单词作为用户的变......
  • ubuntu下配置django+apache+mysql+mod_python+Python
    网上有N种安装方法,我都试过,没有一个最后能成功,浪费了一下午的时间,终于搞定,1.installPython最新的Ubuntu操作系统是含有Python的,可以通过Python--version查看的:lab@lab:~......