数据结构与算法入门 - 栈

在计算机科学中，为了处理大量的、复杂的数据，便需要引入两个具有一定逻辑关系的概念（或工具）来帮助我们，即数据结构、算法. 本文介绍常见的数据结构之一——栈.

数据结构

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

常见的数据结构

栈(Stack)

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

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

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

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

$f_n = \frac{1}{n+1} C^{n}_{2n}$

参考

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