栈和队列b

栈

• 只允许在一端插入和删除的线性表。允许插入和删除的一端称为栈顶(top)，另一端称为栈底(bottom)。

• 当表中没有元素时称为空栈。

• 进栈（Push）：在栈顶位置插入元素的操作。

• 出栈（Pop）：删除栈顶元素的操作

• 特点：后进先出（LIFO, Last In First Out ）或者先进后出（FILO, First In Last Out）。

顺序栈

• 栈的顺序存储结构简称为顺序栈，可用数组来实现顺序栈。

• 栈底位置是固定不变的，可以将栈底位置设置在数组的两端的任何一个端点。

• 栈顶位置随着进栈和退栈操作而变化，用一个整型变量top（栈顶指针）来指出栈顶。

• 顺序栈面临溢出问题
• 上溢（Overflow）
当栈中已经有maxSize个元素时，如果再做进栈运算，所产生的现象
• 下溢（Underflow）
对空栈进行出栈运算时所产生的现象
📌
如何合理进行栈空间分配，以避免栈溢出或空间的浪费？
1. 双栈共享一个栈空间（多栈共享栈空间）
2. 栈的链接存储方式—— 链式栈
• 双栈共享一个栈空间
• 两个栈共享一个数组空间V[maxSize]
• 该空间的两端分别设置为两个栈的栈底 b[0] = -1, b[1] = maxSize
• 两个栈的栈顶都向中间延伸，直到相遇
• 栈满条件：t[0]+1 == t[1] //栈顶指针相遇
• 栈空条件：t[0] = b[0]或t[1] = b[1]//栈顶指针退到栈底
• 栈的链接表示 — 链式栈
• 链式栈无栈满问题，空间可扩充
• 插入与删除仅在栈顶处执行
• 链式栈的栈顶在链头
• 适合于多栈操作

• 应用：
• 括号序列
左括号进栈，右括号出栈，最后看剩多少。
• 表达式计算
• 中缀(infix)表示
<操作数> <操作符> <操作数>，如 A+B；
计算步骤
1. 从左向右扫描表达式。
1. 遇到操作数时，直接压入操作数栈。
2. 遇到运算符时，比较当前运算符和运算符栈顶的优先级：
1. 如果当前运算符优先级较高，则直接压入运算符栈。
2. 否则，弹出运算符栈顶的运算符并对操作数栈的顶部两个操作数进行运算，将结果压入操作数栈，再将当前运算符压入运算符栈。
3. 遇到左括号时，直接压入运算符栈；遇到右括号时，不断弹出运算符栈的运算符并对操作数栈计算，直到遇到左括号。
4. 扫描完成后，清空运算符栈。
• 前缀(prefix)表示
<操作符> <操作数> <操作数>，如 +AB；
前缀表达式是一种运算符在操作数前面的表达方式，例如 + 3 4 表示 3 + 4。计算前缀表达式时，我们从右向左扫描表达式。
计算步骤【
1. 从右向左扫描表达式。
2. 遇到操作数时，将其压入栈中。
3. 遇到运算符时，从栈中弹出两个操作数，进行相应运算，并将结果压回栈。
4. 最终栈中的唯一值即为表达式的结果。
• 后缀(postfix)表示
<操作数> <操作数> <操作符>，如 AB+；
在后缀表达式的计算顺序中已隐含了加括号的优先次序，括号在后缀表达式中不出现。
计算步骤
1. 从左到右扫描表达式。
2. 遇到操作数时，压入栈中。
3. 遇到运算符时，从栈中弹出两个操作数，计算结果并将结果压入栈。
4. 最终栈中的唯一值即为结果。

栈和递归

• 构成递归的条件
不能无限制地调用本身，必须有一个出口，化简为非递归状况直接处理。

• 递归工作栈
• 每一次递归调用时，需要为过程中使用的参数、局部变量等另外分配存储空间。
• 每层递归调用需分配的空间形成递归工作记录，按后进先出的栈组织。

• 递归过程到非递归过程
• 递归过程简洁、易编、易懂
• 但有的时候递归过程效率低，重复计算多（例如Fib数列的计算）
• 改为非递归过程的目的是提高效率
• 递归改非递归的方法：
• 通过迭代实现非递归过程（高效）
• 借助栈实现非递归过程 （功能等价）

队列

• FIFO结构，先进先出，队尾进队首出。

• 一端称为rear，一端称为front。

• 最基本的操作包含进队和出队。
• 进队: rear = rear + 1，新元素在rear处加入。
• 出队: front = front + 1，取出下标为 front 的元素
• 队空时:rear == front
• 队满时:rear == maxSize – 1（假溢出）
因为此时前面可能有位置，但是你不知道
解决假溢出的办法之一：将队列元素存放数组首尾相接，形成循环（环形）队列。

循环队列

• 一个首尾相衔的队列，前后挨着，通过rear和front指针的移动进行操作。

链式队列

• 用链表结构来实现的队列。

• 队头、队尾指针加1时从maxSize-1直接进到0,

• 可用语言的取模(余数)运算实现。

• 队头指针进1: front = (front+1) % maxSize;

• 队尾指针进1: rear = (rear+1) % maxSize;

• 队列初始化: front=rear = 0;

• 队空条件: front==rear;

• 队满条件: (rear+1) % maxSize==front;

优先队列

• 是不同于先进先出队列的另一种队列。每次从队列中取出的是具有最高优先权的元素

• 优先权是根据问题而定的

• 出现相同的优先级的元素时，按FIFO的方式处理

• 优先队列的存储表示与实现
• 数组
• 堆