# 栈和队列的定义和特点

# 栈的定义和特点

1. 定义：栈式限定于插入和删除只能在表的尾端点进行的线性表
2. 特点：先入后出
3. 栈的相关概念：
   1. 栈顶 Top：插入元素插入到栈顶，称为入栈，删除元素删除栈顶元素，称为出栈
   2. 栈底 Base：最先入栈的元素

# 队列的定义和特点

1. 定义：队列限定于插入元素插入在队尾，删除元素删除在对头
2. 特点：先进先出
3. 队列的相关概念：
   1. 队头：删除元素在队头进行操作
   2. 队尾：添加元素在队尾进行操作

# 栈和队列的比较

# 栈的表示和操作实现

# 栈的抽象数据类型定义

ADT Stack {

​ 数据对象：定义对象结构

​ 数据关系：规定栈顶，栈底元素

​ 基本操作：初始化，进栈，出栈，取栈顶元素等

} ADT Stack

# 栈的基本操作思路

1. InitStack(&S)：
   1. 操作结果：构造一个空栈 S
2. DestroyStack(&S)：
   1. 初始条件：栈 S 已经存在
   2. 操作结果：栈 S 被销毁
3. StackEmpty(S)：
   1. 初始条件：栈 S 已经存在
   2. 操作结果：若栈 S 为空栈，则返回 true ，否则 false
4. StackLength(S)：
   1. 初始条件：栈 S 已经存在
   2. 操作结果：返回 S 的元素个数，即栈的长度
5. GetTop(S,&e)：
   1. 初始条件：栈 S 已经存在
   2. 操作结果：用 e 返回 S 的栈顶元素
6. ClearStack(&S)
   1. 初始条件：栈 S 已经存在
   2. 操作结果：将 S 清为空栈
7. Push(&S,e)：
   1. 初始条件：栈 S 已经存在
   2. 操作结果：插入元素 e 为新的栈顶元素
8. Pop(&S,&e)：
   1. 初始条件：栈 S 已经存在且非空
   2. 操作结果：删除 S 的栈顶元素，并用 e 返回其值

# 顺序栈

1. 存储方式：同一线性表的顺序存储结构完全相同
2. 栈顶指针（top）：指示栈顶元素在顺序栈中的位置
3. 栈底指针（base）：指示栈底元素在顺序栈中的位置（为了方便入栈操作，通常 top 指向栈顶元素之上的下标地址）
4. 用 stacksize 表示栈可使用的最大容量
5. 空栈：base == top 是栈空的标志
6. 栈满：top - base == stacksize
7. 栈满时处理方法：
   1. 报错，返回操作系统
   2. 分配更大的空间，作为栈的存储空间，将原栈的内容移入新栈
8. 上溢（overflow）：栈已经满，又要压入元素
9. 下溢（underflow）：栈已经空，还要弹出元素

# 链栈

1. 定义：链栈式运算受限的单链表，只能在链表头部进行操作
2. 栈顶：栈顶指针即为头指针（采用头插法创建链表）

# 栈与递归

# 递归的定义

1. 若一个对象部分地包含它自己，或用它自己给自己定义，则称这个对象是递归，则称这个对象是递归的
2. 若一个过程直接地或间接地调用自己，则称这个过程是递归的过程
3. 分治法：对于一个复杂的问题，能够分解成几个相对简单的且解法相同或类似的子问题来求解
4. 优点：结构清晰，程序易读
5. 缺点：每次调用都要生成工作记录，保存状态信息，入栈；返回时要出栈，恢复状态信息，时间开销大

// 递归求 n 的阶乘

long Fact(long n) {

    if(n == 0) {

        return 1;

    } else {

        return n * Fact(n - 1);

    }

}

# 借助栈改写递归

1. 设置一个工作栈存放递归工作记录
2. 进入非递归调用入口将调用程序传来的实在参数和返回地址入栈
3. 进入递归调用入口：当不满足递归结束条件时，逐层递归，将实参，返回地址及局部变量入栈，这一过程可用循环语句来实现模拟递归拆解过程
4. 递归结束条件满足，将到达递归出口的给定常数作为当前函数值
5. 返回处理：在栈不空的情况下，返回退出栈顶记录，根据栈顶记录的返回地址进行题意规定的操作，即逐层计算当前函数值，直至栈空为止，模拟递归求值过程

# 队列的表示和操作实现

# 相关术语

1. 队列（Queue）：仅在表尾进行插入操作，在对头进行删除操作的线性表
2. 队尾：最后进入队列的元素
3. 队头：最先进入队列的元素
4. 入队：插入元素到队尾
5. 出队：删除元素在队头

# 队列的抽象数据类型定义

ADT Queue {

​ 数据对象：操作的数据的对象

​ 数据关系：规定队头和队尾

​ 基本操作：入队，出队，判断队列是否为空等

}

# 顺序队列

1. 定义队头指针（front）： int front = 0 （每删除一个元素 front++）
2. 定义队尾指针（rear）： int rear = 0 （每插入一个元素 rear++，一半让 rear 指向队尾元素下标值 + 1）
3. 初始： front = rear = 0
4. 入队： base[rear] = x; rear++;
5. 出队： x = base[front]; front++;
6. 空队标志： front == rear
7. 发生溢出： rear == MAXQSIZE
8. 真溢出： front == 0 && rear == MAXQSIZE ，再入队，真正溢出
9. 假溢出： front != 0 && rear == MAXQSIZE ，再入队，假溢出

# 循环队列

1. 定义：为了解决普通队列的假上溢问题
2. 解决方法：base [0] 接在 base [MAXQSIZE - 1] 之后，若 rear + 1 == M，则令 rear = 0
3. 插入元素：
   1. Q.base[Q.rear] = x
   2. Q.rear = (Q.rear + 1)%MAXQSIZE
4. 删除元素：
   1. x = Q.base[s.front]
   2. Q.front = (Q.front + 1)%MAXQSIZE
5. 解决队满时判断方法：少用一个元素空间， (rear + 1)%MAXQSIZE == front
6. 队空： front == rear

# 链式队列

1. 队头：头节点指向的地址
2. 队尾：最后一个节点的地址
3. 优点：动态生成队列的节点，防止顺序队列中的队满，溢出