栈、队列和哈希存储（20250211）

        函数功能实现原则：对修改关闭，对增加开放

1.栈（后进先出       FILOO）

1.1栈区

1. 存储局部变量
2. 函数的形参和返回值地址
3. 函数调用关系（保护现场和恢复现场）

1.2堆区

        开发人员手动管理的区域，使用完手动释放

1.3数据区

1. data段（只读数据区）：1.已初始化的全局变量        2.已初始化的静态变量
2. bss段：1.未初始化的全局变量        2.未初始化的静态变量（bss段对于未初始化的全局静态变量，按位清零）
3. 字符串常量区：存储字符串常量

1.4文本区

1.代码指令

2.常量

1.5内核

2.1栈结构

        只允许从一段进行数据的插入和删除的线性存储结构

        应用：四则混合运算求值

2.2链式栈、顺序栈

1. 链式栈：非连续空间的栈结构
2. 顺序栈：连续空间的栈结构

        一般是头插、头删

2.3关于满、空栈和增、减栈

1. 关于满、空栈：栈顶所在位置是否存有元素
2. 关于增、减栈：按照栈的生长方向区分（栈底到栈顶的方向是否是由低到高）

2.队列（先进先出        FIFO）

2.1队列结构

        从一端进行数据插入，另一端进行数据删除的线性存储结构

        应用：缓存数据

2.2顺序表

        对于空队列：队头和队尾位于同一位置

1. 顺序队列：假溢出（尽管队列中还有空余的空间，但由于队列的操作方式，导致新元素无法加入队列的现象）
2. 循环队列：[队头，队尾)

问：如何判断空队列和满队列

        空：队头和队尾相遇

        满：队尾的下一个元素与队头位于同一位置（牺牲一个存储空间）得到

2.2链式队列

1. 一般链表队列是头删尾插
2. 队列一般包含指向队头和队尾的两个指针、统计队列元素的clen
3. 当仅有唯一节点入队时，队头和队尾指向同一元素，当唯一节点出队时，队头和队尾同时指向NULL

3.哈希存储/散列存储

3.1哈希存储

        将要存储数据的关键字和数据的存储位置之间建立对应的函数关系（哈希函数），存储数据时，按照函数关系寻找存储位置；数据查找是，根据关键字进行函数映射得到数据的存储置。

3.2哈希表：一段连续内存空间

        目的：提高数据的查找效率

3.3哈希函数

1. 求余法
2. 数学分析法

3.4哈希冲突/哈希矛盾

1. 开放定址法：往下寻找空地址存放数据，对存储空间有所要求
2. 链地址法：数组 + 链表