[项目009] 栈和队列的综合 显示答案 | 返回首页
作者：欧新宇（Xinyu OU）
当前版本：Release v1.0
开发平台：gcc 13.1.0, g++ 13.1.0, gdb 13.2
运行环境：Intel Core i7-13700KF CPU 3.4GHz, 32GB RAM
本教案所涉及的数据及代码仅用于教学和交流使用，请勿用作商用。
最后更新：2023年9月30日
作业要求：将【课后作业】的题目及程序代码整理成实验报告，并以PDF格式，或直接拍照上传到【雨课堂】（不要使用word文档进行上传）。
【课后作业】
1. 对中缀算法表达式，可以借助运算符栈OPTR和运算数栈OPND进行求值，按照四则运算加、减、乘、除优先关系的惯例，以表格形式完成表达式3×(6-5)的求值过程，要求给出OPTR和OPND栈的具体变化过程。
算法提示：
- 在OPTR运算符栈中，运算符×、(、)将依次入栈；
- 在OPND运算数栈中，运算数3、6、5将依次入栈；
- 每当运算符和运算数满足计算规则，将执行计算（Push(OPND, Operate(OPND, OPTR, OPND))），并将运算结果写入运算数栈中。
| 步骤 | OPTR栈 | OPND栈 | 读入数据 | 主要操作 |
|---|---|---|---|---|
| 1 | # | # | 3×(6-5)# | Push(OPND, 3) |
| 2 | # | 3 | ×(6-5)# | Push(OPTR, '×') |
| 补齐后续内容 | ||||
| 10 | # | 3 | # | return(GetTop(OPND)) |
2. 回文是指正读反读均相同的字符序列，例如“level”和“eye”都是回文，但“Good”不是回文。试写一个算法判定给定的字符序列是否是回文。
算法提示：
- 回文可以通过比较中心元素两边等距离的元素是否相等来判定。需要注意的是，当字符串为奇数时，需要跳过中心元素；而当字符串为偶数时，直接对比字符串中间的两个元素。
- 在进行元素比较时，可以先用一个堆栈来对字符串前一半的元素进行入栈。在进行对比的时候，再逐个将堆栈中的元素进行出栈操作，此时从堆栈中获得的元素刚好是逆序的。
- 最后，通过从中间字符开始扫描后一半元素，并将其和堆栈栈顶弹出的元素进行对比。
- 若扫描完整个字符串后，所有对比元素均相等，则说明该字符串为回文。
bool isPalindrom(char *t){
// 在此处填入代码
}
3. Q是一个队列，S是一个空栈，试实现将该队列中的元素进行逆置。
算法提示：
- 队列具有先进先出的特点，无法实现将元素逆置；而栈具有先进后出的特点，可以实现将元素逆置。因此，可以将队列Q和栈S进行结合，通过栈S实现将队列Q中的元素逆置。
- 具体操作上，可以先逐元素将队列中的元素全部输出到栈中；然后再将栈中的元素逐个输出到队列中。
Status Inverser(Stack &S, Queue &Q, ElementType &e){
// 在此处填入代码
}
4. 假设存在一个如下图所示的车厢调度系统，其左右两侧铁道均为单向行驶道，调度站有一个用于调度的栈道。火车调度站的入口处有n节硬座(H)和软座(S)车厢的火车。试编写一个算法，输出对这n节车厢进行调度的操作序列，以使所有的软座车厢都被调整到硬座车厢之前。
算法提示：
- 两侧的铁道均为单向行驶，因此，调度站只能从左侧铁道进入，然后从右侧铁道离开。此时，我们可以将两侧铁道看作是一个中间可进出的队列。
- 在队列的中间，存在一个堆栈，用于将软座车厢调整到硬座车厢之前。
- 算法的基本思想是让所有车厢依次在队列中前进，并逐一进行检查，若发现有硬座车厢则将其入栈，等待最后调度；其余车厢顺着队列前移动。
- 等所有车厢都完成检查后，将栈中的硬座车厢全部出栈，并跟随在前面的车厢之后，形成一个完整的队列。
void Train_Conductor(char *train){
// 在此处填入代码
}
【选做题】[奖励分：0~1]
某汽车轮渡口，过江渡船每次能载10辆车过江。过江车辆分为客车类和货车类，上渡船有如下规定：同类车先到先上船；客车先于货车上传，且每上4辆客车，才允许放上1辆货车；若等待客车不足4辆，则以货车代替；若无货车等待，允许客车都上传。试设计一个算法模拟渡口管理。
算法提示：
- 假定数组q的最大小标10为每次载渡的最大量。定义三个队列，分别用于存放渡船（Q）、客车（Q1）、货车（Q2）上车辆的数量；
- 根据题意，车辆调度可分为两种情况：
2.1 若Q1充足，则每取4个Q1的元素后，取一个Q2的元素，直到Q中的元素个数达到上限10；当取Q2元素时，每次完成后都对客车计数器清零。
2.2 若Q1不充足，则直接用Q2进行补齐。退出时，需要对客车计数器进行清零。
void vehicle_scheduling(Queue Q, Queue Q1, Queue Q2){
// 在此处填入代码
}
【扩展练习】
1.用栈实现将中缀表达式 8-(3+5)*(5-6/2) 转换成后缀表达式，试给出栈变化过程的表格形式。
算法提示：
- 在OPTR运算符栈中，运算符 -、(、+、)、*、(、-、/、) 将依次入栈；
- 在Postfix后缀表达式栈中，运算数 8、3、5、5、6、2 将依次入栈；
- 每当运算符和运算数满足计算规则，将运算符从OPTR栈移入PostFix栈；
- 需要注意的是，括号"()"不需要写入后缀表达式中。
| 步骤 | OPTR栈 | Postfix栈 | 读入数据 | 主要操作 |
|---|---|---|---|---|
| 1 | # | Null | 8-(3+5)*(5-6/2)# | Push(Postfix, '8') |
| 2 | # | 8 | -(3+5)*(5-6/2)# | Push(OPTR, '-') |
| 补齐后续内容 | ||||
| 8 | #-( | 835+ | *(5-6/2)# | PoP(OPTR){消除一对括号} |
| 补齐后续内容 | ||||
| 16 | #-*(-/ | 835+562 | # | Pop(OPTR, '/'); Push(Postfix, '/') |
| 补齐后续内容 | ||||
| 20 | #- | 835+562/-* | # | Pop(OPTR, '-'); Push(Postfix, '-') |
| 21 | # | 835+562/-*- | # | return Postfix |
2. 设单链表的表头指针为L，节点结构由data和next两个域构成，其中data域为字符型。试设计算法判断该链表的全部n个字符是否中心对称。例如xyx、xyyx都是中心对称字符。
算法提示：
- 本题考察的问题实际上是在做回文判断，回文可以通过比较中心元素两边等距离的元素是否相等来判定。需要注意的是，当字符串为奇数时，需要跳过中心元素；而当字符串为偶数时，直接对比字符串中间的两个元素。
- 注意本题使用单链表来进行操作，其中p->data为栈链中的指，p->next为栈链中的指针。
- 在进行元素比较时，可以先用一个数组做为栈链来对保存字符串前一半的元素。在进行对比的时候，再逐个将栈链中的元素进行出栈操作，此时从堆栈中获得的元素刚好是逆序的。注意以数组保存的栈链出栈操作应从数组的末尾开始反向进行遍历。
- 最后，通过从中间字符开始扫描后一半元素，并将其和栈链栈顶弹出的元素进行对比。
- 若扫描完整个字符串后，所有对比元素均相等，则说明该字符串为回文。
bool CentralSymmetry(LinkList L, int n){
// 在此处填入代码
}
3. 将编号为0和1的两个栈存放于一个数组空间V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶指针top[0]等于-1时，该站为空；当第1号栈的栈顶指针top[1]等于m时，该栈为空。两个栈均从两端向中间增长。试编写双栈初始化，判断栈空、栈满、进栈和出栈的算法函数。双栈的数据结构定义如下：
typedef struct DblStack{
int top[2], bottom[2]; // 定义栈顶和栈底指针
SElementType *V; // 定义栈数组
int m; // 定义栈的最大容量
} //DblStack
算法提示：
- 对于初始化函数，需要对两个栈的栈顶和栈底指针都进行初始化。初始时，左栈栈顶指针为-1，右栈栈顶指针为m；同时，栈底指针与栈顶指针处于相同位置。
- 栈空的条件是左栈栈顶和栈底指针都为-1，右栈栈顶和栈底指针都为m。
- 栈满条件为左栈栈顶指针top[0]的下一个位置top[0]+1等于右栈栈顶指针top[1]。
- 进栈操作时，先判断栈是否满，若满则返回错误信息。否则，执行入栈操作。对于左栈的插入操作将向右扩展，对于右栈的插入将向左扩展。
- 出栈操作时，先判断栈是否空，若空则返回错误信息。否则，执行出栈操作。对于左栈的删除操作指针将向左移动，对于右栈的删除操作指针将向右进行移动。
// 初始化一个大小为m的双向栈 Status InitDblStack(DblStack &S, int m){ // 在此处填入代码 } // 判断第i号栈是否为空，空则返回truen，非空则返回 bool IsDblStackEmpty(DblStack &S, int i){ // 在此处填入代码 } // 判断是否栈满，未满返回false，满返回true bool IsDblStackFull(DblStack &S){ // 在此处填入代码 } // 向第i号栈中插入元素e Status DblPush(DblStack &S, int i, SElementType e){ // 在此处填入代码 } // 将第i号栈的栈顶元素弹出，存入e中 Status DblPop(DblStack &S, int i, SElementType &e){ // 在此处填入代码 }