数据结构 栈和队列
栈
顺序栈
top = -1
链栈
- 初始化
- 判断队空
- 入队: 头插法
- 出队: 单链表删除
队列
顺序队
front, rear
%MAXSIZE
链队
若有头节点 则队头在头节点后，队尾在链表尾部
基本操作：
- 初始化
- 判断队空
- 入队： lqu->rear->next = p; lqu->rear = p;
- 出队: p = lqu->front; lqu->front = p->next; x = p->data; free(p);
其他
- 共享栈
- 双端队列
- 输入受限：一端皆可，一端只输出
- 输出受限： 一端皆可，一端只输入
应用：
1. 表达式转换
中缀 -> 后缀
- 左 -> 右
- 数字写，空栈入，大于入，左括号入，栈顶左括号入，右括号出 直到左括号，小于等于出 左括号入
- image
中缀 -> 前缀
- 右 -> 左
- 数字写，空栈入，大于等于入，右括号入，栈顶右括号入，左括号出 直到右括号，小于出 右括号入
- image
- 图标题有误！
后缀 -> 前缀
- 数入 数入 组合后符号提前入
2. 表达式求值
注意顺序， 建立两个栈
中缀
- 数字入 符号大于入 左括号入 小于等于出2数1号 栈空依次出
后缀
- (左 -> 右)
- 数字入栈
- 遇到符号出栈 2个数，并将计算结果入栈
- 重复
前缀
- (右 -> 左)
- 数字入栈
- 遇到符号出栈 2个数，并将计算结果入栈
- 重复
3. 用栈模拟队列
限制：只能全入再全出，不能中断
队满：s1满且s2不空
队空：s1,s2空
入队规则：
- 若s1未满，直接入栈s1
- 若s1满，s2为空，将s1全部倒入s2，再入栈s1
出队规则：
- 若s2不空，直接出栈
- 若s2空，s1倒入s2后，再出栈
正常配置
正常配置：入队-先移动指针再入队元素，出队-先移动指针再取元素
- 队满： front = (rear+1) % maxSize
- 元素个数： ( rear - front + maxSize ) % maxSize
非正常配置
非正常配置： 入队-先入队元素再移动指针，出队-先移动指针再取元素 etc... !还有其他
- 队满： front = (rear+1) % maxSize
- 元素个数： ( rear - front + maxSize ) % maxSize
双端队列
在某一端进行输入或输出的限制
- 毫无限制
- 输入限制
- 输出限制
不可能的序列为：全排列-卡特兰数
