【数据结构实践】手把手带你简单实现 Python 自定义栈
前言
何为栈?
栈又叫堆栈,它是一个有序集合.栈跟队列一样,也是一种呈线性排列的数据结构,而且两者极其相似,队列是先进先出(FIFO),而栈是后进先出(LILO).即像栈这种结构是最后添加的数据最先被取出,而且在这种结构中,我们只能访问最新添加的数据.栈就像一摞书,拿到新书时,我们就会把新书放在书堆上,取书的时候也只能从最上面的新书开始取.可看出它是是一种操作受限的线性表,所以往栈中添加和删除元素都是发生在同一端,通常称作发生操作的这一端为顶部,对应的端为底部.其实栈更像一个桶,你把东西放进桶里,你每次只能从最上面去拿,因为底下是封闭的,如果你想取下面的东西,就必须得先把上面的东西拿走.将目标物体暴露在最上面(栈顶)才行
栈有两种存储方式,即线性存储和链接存储(链表)。栈的一个最重要的特征就是栈的插入和删除只能在栈顶进行,所以每次删除的元素都是最后进栈的元素,故栈也被称为后进先出(LIFO)表。每个栈都有一个栈顶指针,它初始值为-1,且总是指向最后一个入栈的元素,栈有两种处理方式,即进栈(push)和出栈(pop),因为在进栈只需要移动一个变量存储空间,所以它的时间复杂度为 O(1),但是对于出栈分两种情况,栈未满时,时间复杂度也为 O(1),但是当栈满时,需要重新分配内存,并移动栈内所有数据,所以此时的时间复杂度为 O(n)。以下举例栈结构的两种实现方式,线性存储和链接存储。
1.下图是线性存储的栈.这也是我们最常见的栈的存储方式,这也是本文的重点
2.下图是是链链式存储的栈
栈的操作演示
入栈操作
出栈操作
整个流程
入栈:也叫压栈.就是向一个栈插入新元素.它是把新元素放到栈顶元素上面,使其成为新的栈顶元素
若 Top>=n,则给出溢出信息,作为出错处理(入栈前检查栈是否已满,满则溢出;就像桶装满水后,继续加水就会溢出,不满则入栈)
设置 Top=Top+1,栈指针加 1.指向入栈地址
S(Top) =X,结束(X 为新入栈的元素)
出栈:也加退栈,其实就是删除栈顶元素.是其相邻的元素成为栈顶元素
若 Top<=0,则给出溢出信息,作为出错处理(出栈前先检查栈是否已空,空则下溢,不空则出栈)
X=S(Top),出栈后的元素赋给 X
Top=Top-1,结束.栈指针减 1,指向栈顶
栈的设计流程
创建自定义类 NStack
添加栈属性
创建入栈,出栈,显示栈当前(栈顶)元素等方法
代码实现
1.创建 NStack 类,并设置其元素
2.设置栈大小
3.实现出入栈相关操作方法
4.设置当前元素展示方法 show()
5.其他方法:清空栈,判断栈是否已空或已满
6.验证 NStack 类:实例化并调用类的相关方法操作栈
执行结果如下:
总结
栈只能在一端操作这一点看起来似乎非常不方便.但是在只需要访问最新数据时,使用栈就方便多了.比如,规定(A B ( C (D E) F ) (G ((H) I J) K))这一串字符中括号的处理方式如下:首先从左边开始读取字符,读到左括号就将其入栈,读到右括号就将栈顶的左括号出栈,此时,出栈的括号便与当前读取的右括号相匹配.通过这种处理方式,我们就能得知配对括号的具体位置
版权声明: 本文为 InfoQ 作者【迷彩】的原创文章。
原文链接:【http://xie.infoq.cn/article/4aa3489c4986ac4761e4dde38】。文章转载请联系作者。
评论