栈与队列
一、栈
栈（stack）是限定仅在表尾（栈顶）进行插入和删除操作的线性表。
后进先出(LIFO)：
进栈、出栈
栈的抽象数据类型
栈的顺序储存结构（数组）
栈的结构定义
两栈共享空间
两栈共享空间
关键思路：它们是数组两端，向中间靠拢。top1和top2分别是栈1和栈2的栈顶指针。
栈1为空，top1 = -1,;栈2为空，top2 = n;
判断栈满，top1+1 == top2
两栈共享空间结构
栈的链式储存：链栈
栈顶指针在头部，单链表中的比较常用的头结点失去意义，通常链栈无需头节点。
//单链表基础结构
template<class DataType>
struct Node{
DataType data;
Node<DataType> *next;
};
//使用时需多声明一个栈顶指针top
Node<DataType> *top = new Node<DataType>;
image.png
栈的应用——递归
斐波那锲数列：前面相邻两项之和，构成后一项。
Fibonacci数学定义
执行过程
递归与栈
- 递归：函数直接或间接调用自身（反复调用，建立大量函数副本；但结构清晰、简洁）。
- 迭代：无需反复调用和占用额外内存。
栈的应用——四则运算表达式求值
后缀（逆波兰）表示法：
-
将中缀表达式转化为后缀表达式（栈用来进出运算的符号）；
-
将后缀表达式进行运算得出结果（栈用来进出运算的数字）
二、队列（queue）
队列：先进先出（FIFO）
- 入队（插入）：新元素始终添加在队列的末尾；
- 出队（删除）：发生在队头，只能移除第一个元素；
应用非常频繁：键盘输入“god”,若使用栈，输出“dog”;使用队列，输出“god”
为避免队头、队尾处理麻烦：front指针指向队头元素，rear指针指向超尾元素。
左图为队列空，右图为元素入队后
存在问题：“假溢出”现场，队尾满了，但队头还是空闲。
尾指针溢出，但队列仍未满
循环队列：头尾相接的顺序储存结构。
循环队列及指针重合问题
存在问题：当
front与rear指针重合时，队列存在空或满两种情况。
解决方法：
- 设标志变量
flag，当front==rear,flag=0,队列为空；当front==rear,flag=1,队列满，- 队列空时，
front==rear；队列满时，保留一个元素空间。
★:-队列满的条件是(rear+1)%QueueSize == front；
★:-通用计算队列长度公式:(rear - front + QueueSize)%QueueSize
☆:-采用%QueueSize防止长度溢出——最多一整圈。
循环队列顺序储存结构
链队列：只能尾进头出的线性表的单链表。
链队列结构
链队列的入队、出队操作示意图
若可以确定队列长度最大值，建议用循环队列 ；无法预估队列长度，则使用链队列。
