功能受限的表结构
一、栈和队列介绍
- 栈和队列是两种重要的线性结构，从数据结构角度，他们都是线性表，特殊点在于它们的操作被限制，也就是所谓的功能受限，统称功能受限的线性表
- 从数据类型角度，它们也可以是看成处理、管理数据的一种规则
二、栈结构
-
栈（stack）是限定在表尾进行数据的插入、删除等操作的线性表(只允许操作一个端口的数据)
-
表尾称为栈顶，表头称为栈底 ，当没有元素的空表称为空栈，当元素的数量到达栈的容量时称为满栈 ，添加数据到栈顶中的动作称为入栈、压栈，把数据从栈顶中拿出的动作称为出栈、弹栈，正因为这个数据的添加、删除的规则，所以栈中元素满足先进后出，简称FILO表、LIFO
-
栈结构可以具备的功能
-
创建
-
销毁
-
是否满栈
-
是否空栈
-
入栈
-
出栈
-
查看栈顶元素
-
查看元素数量
注意：只有顺序栈才有需要判断栈是否满
-
1、栈结构的顺序实现
// 设计顺序栈结构
typedef struct ArrayStack {
TYPE* ptr; // 存储栈元素的内存首地址
size_t cap; // 栈的容量
size_t top; // 栈顶的位置
} ArrayStack;
2、栈结构的链式实现
#define TYPE int
typedef struct ListNode {
TYPE data;
struct ListNode* next;
} ListNode;
// 链式栈结构
typedef struct ListStack {
ListNode* top; // 栈顶指针 指向栈顶节点
size_t size; // 节点数量
} ListStack;
3、栈的应用
- 内存管理，例如栈内存，之所以叫栈内存因为它遵循栈的先进后出原则，函数调用、函数参数的传参、定义，先把数据入栈，等结束时，逆序出栈，函数的调用、结束跳转也是遵循栈结构原则
- 特殊的算法：算术表达式的转换(中缀表达式转后缀表达) 、进制转换、迷宫算法
三、队列结构
1、队列介绍
- 与栈结构相似的是，也只允许在端口处进行添加、删除操作，但是有两个端口，一个负责添加数据，称为入队 ，该端口称为队尾，另一个端口只负责删除数据，称为出队，该端口称为队头，属于一种先进先出结构，称为FIFO
2、队列所具备的功能
- 创建队列
- 销毁队列
- 判断队空
- 判断队满 （只有顺序存储时才有）
- 入队
- 出队
- 查看队头元素
- 查看队尾元素
- 队列元素数量
3、队列的链式实现
#define TYPE int
typedef struct ListNode {
TYPE data;
struct ListNode* next;
} ListNode;
// 设计链式队列结构
typedef struct ListQueue {
ListNode* front; // 队头
ListNode* rear; // 队尾
size_t size; // 节点数量
} ListQueue;
4、队列的顺序实现
- 顺序队列的队尾下标rear会随着入队而增大rear+1，队头下标front会随着出队增大front+1，因为是顺序结构，就有随着入队和出队的进行，可能超出有效的下标范围，如果不进行处理，那么队列无法重复使用。
- 为了避免这种情况，当队尾、队头下标达到存储空间的末尾时，要想办法让它们回到内存的开头位置，相当于把内存想象成一个环形，从而可以循环使用队列，这样的队列称为循环队列
- 因此当队尾、队头下标增加时，都要对队列的容量求余
- rear = (rear+1)%cap
- front = (front+1)%cap
带计数器版本的循环队列
- 很直接地解决了元素数量的问题
- 可以直接解决队空、队满的判断矛盾问题
- 但是在队列结构中会多增加一个数据项，并且每次入队、出队操作都要对其进行修改
typedef struct ArrayQueue {
TYPE* ptr; // 存储元素的内存首地址
size_t cap; // 容量
size_t cnt; // 元素个数 计数器
int front; // 队头下标
int rear; // 队尾下标
} ArrayQueue;