文章目录
一. 思维导图
二. 栈的概念
1. 定义
- 栈（stack）只允许在一端进行插入和删除操作的线性表
- 或者说是一种可以实现“先进后出”的存储结构
- 栈是一种操作受限的线性表
2. 栈的内存分配
#include <stdio.h>
{
void f(int k){
int m;
double * p = (double *)malloc (200);
}
int main(void){
int i = 10;
int * p = (int *)malloc(100);
return 0;
}
}
-
m，q，i，p变量是栈分配
静态分配（由OS分配）压栈出栈 或局部变量分配 -
200，100存储是堆分配
动态分配（程序员手动分配） 堆排序方式分配内存
3. 栈的分类
(1). 顺序栈（静态栈）
- 类数组
(2). 链栈（动态栈）
- 类链表
三. 栈的存储结构
1. 顺序栈
(1). 定义
- 采用顺序存储结构（用一组地址连续的存储单元存放栈底到栈顶的元素）
(2). 顺序栈的数据结构表示
(3). 顺序栈的基本操作
(4). 顺序栈的特例（共享栈）
定义
- 两个栈的栈底分别设置在共享空间的两端，栈顶向共享空间的中间延伸，共享一个一维数组空间
共享栈的算法基本操作
放代码
2. 链栈
(1). 定义
- 采用链式存储的栈，一般采用单链表实现
优点：
- 便于多个栈共享存储空间和提高效率，不存在栈满上溢
(2). 链栈数据结构表示
(3). 链栈算法的操作
四. 栈的应用
1. 函数调用
2. 中断
3. 表达式求值
4. 缓冲处理
5. 走迷宫
未完待续…