03-3.1.1 栈的基本概念

• 👋 Hi, I’m @Beast Cheng
• 👀 I’m interested in photography, hiking, landscape…
• 🌱 I’m currently learning python, javascript, kotlin…
• 📫 How to reach me --> 458290771@qq.com

喜欢《数据结构》部分笔记的小伙伴可以订阅专栏，今后还会不断更新。🧑‍💻
此外，《程序员必备技能》专栏和《程序员必备工具》专栏（该专栏暂未开设）日后会逐步更新，感兴趣的小伙伴可以点一下订阅、收藏、关注！🚀
谢谢大家！🙏

定义

线性表是具有相同数据类型的n(n >= 0)个数据元素的有限序列，其中n为表长，当n=0时，线性表是一个空表。若用L命名线性表，则其一般表示为：
$$L=(a_1,a_2,...,a_i,a_{i+1},...,a_n)$$
栈（Stack） 是只允许在一端进行插入或删除操作的线性表
也就是说我们如果要执行插入操作的时候，只能在表尾进行插入，不能在表的中间进行插入，这是栈这种数据结构所不允许的

重要术语：栈顶、栈底、空栈

• 栈顶：允许插入和删除的一端
• 栈底：不允许插入和删除的一端

示例：

• 进栈顺序：$a_1->a_2->a_3->a_4->a_5$
• 出栈顺序：$a_5->a_4->a_3->a_2->a_1$

特点：后进先出 Last In First Out(LIFO)
栈其实就是一种特殊的线性表：

• 逻辑结构：与普通的线性表相同
• 数据的运算：插入、删除操作有区别

基本操作

再看栈的基本操作之前，先回顾线性表的基本操作[[线性表——知识总览#^0a30c4]]
栈的基本操作：

• 创 InitStack(&S)：初始化栈——构造一个空栈S，分配内存空间
• 销 DestroyStack(&L)：销毁栈——销毁并释放栈S所占用的内存空间
• 增 Push(&S, x)：进栈——若栈S未满，则将x加入使之成为新栈项
• 删 Pop(&S, &x)：出栈——若栈S非空，则弹出栈项元素，并用x返回
• 查 GetTop(S, &x)：读栈顶元素——若栈S非空，则用x返回栈顶元素
• 其他常用操作：
  • StackEmpty(S)：判断一个栈S是否为空。若S为空，则返回true，否则返回false

栈的常考题型

进栈顺序：a->b->c->d->e
有哪些合法的出栈顺序？

n个不同元素进栈，出栈元素不同排列的个数为$\frac{1}{n+1}{C}_{2n}^n$
上述公式称为卡特兰数（Catalan），可采用数学归纳法证明（不要求掌握）
如：$\frac{1}{5+1}{C}_{10}^5=\frac{10\ast 9\ast 8\ast 7\ast 6}{6\ast 5\ast 4\ast 3\ast 2\ast 1}=42$