fly6022
文章12
标签22
分类3
数据结构与算法入门 - 栈

数据结构与算法入门 - 栈

在计算机科学中,为了处理大量的、复杂的数据,便需要引入两个具有一定逻辑关系的概念(或工具)来帮助我们,即数据结构、算法.

本文介绍常见的数据结构之一——栈.

数据结构

数据结构是一种具有一定逻辑关系,在计算机中应用某种存储结构,并且封装了相应操作的数据元素集合。数据结构包含三方面的内容,逻辑关系、存储关系及操作.

常见的数据结构

栈(Stack)

栈,又称作堆栈,栈是数据暂时存储的地方,是一种特殊的线性表,它只允许在它的一个固定端进行数据结点的插入和删除.

我们把栈比作一个无盖的圆柱状薯片桶,把数据比作薯片,我们只能在薯片桶的上方放入或拿出薯片,且在上方的薯片最先被拿出,最后被放入;在下方的薯片最后被拿出,最先被放入,这也引出了栈的另一个性质——栈的先进后出性.

如何对栈进行操作?在上方的例子中,我们向薯片桶中放入一枚薯片,这个过程叫做进栈操作(PUSH),我们再从薯片桶中拿出这枚薯片,这个过程叫做退栈操作(POP).此时,薯片桶中最上方的薯片称为栈顶元素,进栈操作是把新元素放置在栈顶元素之上,并使之成为新的栈顶元素的操作;退栈操作则相反,是把栈顶元素移除,并使栈顶元素之下的元素成为新的栈顶元素的操作.

将栈抽象为数学结构:当$n$个元素满足以某种顺序进栈,并在满足先进后出的前提之下,可任意时刻出栈,所获得的元素排列数目满足函数$Catalan() (卡塔兰数)$的计算,即:

参考

[1] 无聊的CairBin.栈的概念及性质[EB/OL].简书网( https://www.jianshu.com/p/540064de9b63 ).2021.09.28-21:40:21

本文作者:fly6022
本文链接:https://blog.fly6022.fun/posts/%E6%95%B0%E6%8D%AE%E7%BB%93%E6%9E%84%E4%B8%8E%E7%AE%97%E6%B3%95%E5%85%A5%E9%97%A8%20-%20%E6%A0%88/
版权声明:本文采用 署名-非商业性使用-禁止演绎 4.0 国际 (CC BY-NC-ND 4.0) 协议进行许可,转载请注明原出处。
×