数据结构 栈和队列

栈

顺序栈

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. 共享栈
2. 双端队列

• 输入受限：一端皆可，一端只输出
• 输出受限： 一端皆可，一端只输入

应用：

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

双端队列

在某一端进行输入或输出的限制

• 毫无限制
• 输入限制
• 输出限制
  不可能的序列为：全排列-卡特兰数