数据结构 （5）栈
一、基本概念
栈是一种运算受限的线性表，它只允许在表的一端进行插入和删除操作，这一端被称为栈顶（Top），而另一端则被称为栈底（Bottom）。栈的插入操作被称为入栈（Push），删除操作被称为出栈（Pop）。栈具有后进先出（Last In First Out，LIFO）或先进后出（First In Last Out，FILO）的特性，即最后插入的元素会最先被删除。
二、抽象数据类型定义
栈的抽象数据类型定义通常包括数据对象、数据关系以及基本操作。数据对象是栈中元素的集合，数据关系则定义了元素之间的顺序。栈的基本操作包括初始化、入栈、出栈、取栈顶元素以及判断栈是否为空等。
三、实现方式
- 数组实现：使用一组连续的内存空间来存储栈中的元素，并通过栈顶指针来指示栈顶元素的位置。入栈时，将新元素存储在栈顶指针的下一个位置，并更新栈顶指针；出栈时，将栈顶元素移动到栈顶指针的位置，并释放该空间，同时更新栈顶指针。数组实现的栈具有访问速度快、实现简单的优点，但存在空间利用率不高的问题，因为数组的大小在初始化时就已确定，当栈中元素数量超过数组大小时，需要进行扩容操作。
- 链表实现：使用一组节点来存储栈中的元素，每个节点包含一个数据域和一个指向下一个节点的指针。入栈时，将新元素添加到链表尾部，并更新栈顶指针；出栈时，将栈顶元素从链表中移除，并更新栈顶指针。链表实现的栈具有空间利用率高、可以动态增长或缩小的优点，但实现相对复杂一些。
四、基本操作及实现
- 初始化：创建一个空栈，并初始化栈顶指针和栈底指针。
- 入栈：将新元素添加到栈顶，并更新栈顶指针。
- 出栈：将栈顶元素移除，并更新栈顶指针。如果栈为空，则出栈操作失败。
- 取栈顶元素：返回栈顶元素的值，但不移除它。如果栈为空，则取栈顶元素操作失败。
- 判断栈是否为空：检查栈顶指针是否等于栈底指针，如果相等，则栈为空。
五、应用场景
- 函数调用：在函数调用过程中，系统会使用栈来保存函数的调用信息，如参数、局部变量和返回地址等。当函数执行完毕后，系统会从栈中弹出这些信息，以恢复调用函数的状态。
- 表达式求值：在表达式求值过程中，栈可以用来存储操作数和操作符。通过逆波兰表达式或中缀表达式求值算法，可以利用栈的后进先出特性来正确计算表达式的值。
- 深度优先搜索：在深度优先搜索算法中，栈可以用来存储待访问的节点。每次从栈顶取出一个节点进行访问，并将其相邻节点依次入栈。这样可以保证按照深度优先的顺序访问所有节点。
- 括号匹配：在检查字符串中的括号是否匹配时，可以使用栈来存储左边的括号。当遇到右边的括号时，从栈顶弹出一个元素进行匹配。如果栈为空或括号不匹配，则说明字符串中的括号不匹配。
结语
不甘于平庸
还在为梦想奋斗
！！！
