栈
大约 2 分钟
定义
- 栈是限定只在表尾进行插入或删除操作的线性表。
- 栈的尾端称为栈顶，头部称为栈底。
- 栈通常被称为是后进先出（
last in first out）表，简称LIFO表。
表示
顺序表示（顺序栈）
- 栈的顺序存储结构是利用一组地址连续的存储单元，依次存放自栈底到栈顶的数据元素，设 指针
top指示栈顶的位置。 - 栈在使用过程中占用的空间难以估计，为了防止空间不足且尽可能节省空间，应当事先分配一个基本容量，然后在应用过程中，若栈空间不足，再进行逐段扩大。
- 顺序栈主要有两个指针：栈底指针
base和栈顶指针top。base在顺序栈中始终不变，因此base为NULL则表示栈结构不存在。top一开始指向base，可以作为判断空栈的方法。非空栈中的栈顶指针始终在栈顶元素的下一个位置上。
初始化栈和按需扩容的实现：
追加元素：
获取栈顶元素：
应用
数制转换
输入一个非负十进制整数，输出等值的八进制数：
递归
栈的一个重要应用是在程序设计语言中实现递归。一个直接调用自己或通过一系列语句间接调用自己的函数，称为递归函数。