栈与队列抽象数据类型的实验探索

# 栈与队列抽象数据类型的实验探索 ## 1. 栈抽象数据类型（Stack ADT）实验 ### 1.1 桥接练习 在这个练习中，我们可以使用`test5.cpp`文件中的测试程序来交互式地测试栈抽象数据类型（Stack ADT）的实现。以下是测试程序支持的命令： | 命令 | 操作 | | ---- | ---- | | +x | 将数据项 x 压入栈顶 | | - | 弹出栈顶数据项并输出 | | E | 报告栈是否为空 | | F | 报告栈是否已满 | | C | 清空栈 | | Q | 退出测试程序 | 操作步骤如下： 1. 编译并链接测试程序，这将编译`stackarr.cpp`文件中的栈的数组实现，生成字符栈的数组实现。 2. 完善测试计划，添加以下测试用例： - 从仅包含一个数据项的栈中弹出一个数据项。 - 将数据项压入通过一系列弹出操作清空的栈。 - 从已满的栈（数组实现）中弹出一个数据项。 - 清空栈。 3. 执行测试计划，如果发现栈的数组实现存在错误，进行修正并再次执行测试计划。 4. 修改测试程序，将`stacklnk.cpp`文件中的栈的链表实现替换数组实现。 5. 重新编译并链接测试程序，这将编译`stacklnk.cpp`文件中的栈的链表实现，生成字符栈的链表实现。 6. 使用测试计划检查栈的链表实现，如果发现实现存在错误，进行修正并再次执行测试计划。 以下是栈操作的测试计划示例： | 测试用例 | 命令 | 预期结果 | 检查情况 | | ---- | ---- | ---- | ---- | | 一系列压入操作 | +a +b +c +d | a b c d | | | 一系列弹出操作 | - - - | a | | | 更多压入操作 | +e +f | a e f | | | 更多弹出操作 | - - | a | | | 检查空和满状态 | E F | False False | | | 清空栈 | - | 空栈 | | | 再次检查空和满状态 | E F | True False | | ### 1.2 实验内练习 1：后缀算术表达式求值 通常，我们习惯使用中缀形式编写算术表达式，例如`(3 + 4) * (5 / 2)`。然而，中缀形式的缺点是需要使用括号来指示运算符的计算顺序，这会大大增加计算过程的复杂性。 后缀形式的算术表达式则更易于计算，在后缀形式中，每个运算符紧跟在其操作数之后，例如上述表达式的后缀形式为`3 4 + 5 2 / *`。 对于由一位非负整数和四个基本算术运算符（加、减、乘、除）组成的后缀算术表达式，可以使用以下算法结合浮点数栈进行求值： 1. 逐个字符读取表达式。 - 如果字符对应一位数字（字符 '0' 到 '9'），则将对应的浮点数压入栈中。 - 如果字符对应算术运算符（字符 '+'、'-'、'*' 和 '/'），则： - 从栈中弹出一个数字，称为操作数 1。 - 从栈中再弹出一个数字，称为操作数 2。 - 使用算术运算符组合这些操作数，结果 = 操作数 2 运算符 操作数 1。 - 将结果压入栈中。 2. 当到达表达式末尾时，弹出栈中剩余的数字，该数字即为表达式的值。 操作步骤如下： 1. 创建一个程序，读取后缀形式的算术表达式，对其进行求值并输出结果。假设表达式由一位非负整数（'0' 到 '9'）和四个基本算术运算符（'+'、'-'、'*' 和 '/'）组成，并且表达式从键盘输入，所有字符在一行上。将程序保存为`postfix.cpp`文件。 2. 完善以下测试计划，填写每个算术表达式的预期结果，也可以在测试计划中包含其他算术表达式。 3. 执行测试计划，如果发现程序存在错误，进行修正并再次执行测试计划。 以下是后缀算术表达式求值程序的测试计划示例： | 测试用例 | 算术表达式 | 预期结果 | 检查情况 | | ---- | ---- | ---- | ---- | | 一个运算符 | 34+ | | | | 嵌套运算符 | 34+52/* | | | | 不均匀嵌套 | 93*2+1– | | | | 所有运算符在末尾 | 4675–+* | | | | 零被除数 | 02/ | | | | 一位数字 | 7 | | | ### 1.3 实验内练习 2：向下增长的栈数组实现 可以构建一个从数组条目`maxSize - 1`开始向下增长到条目 0 的栈的数组实现，将这种“向下”的数组实现与之前创建的“向上”数组实现结合，形成双栈抽象数据类型的实现，前提是两个栈中的数据项总数不超过`maxSize`。 操作步骤如下： 1. 创建一个使用数组的栈抽象数据类型的实现，其中栈向下增长。基于`stackdwn.h`文件中的声明进行实现，`show5.cpp`文件中给出了`showStructure`操作的实现。 2. 将栈的“向下”数组实现保存为`stackdwn.cpp`文件。 3. 修改测试程序`test5.cpp`，将`stackdwn.cpp`文件中的栈的“向下”数组实现替换“向上”数组实现。 4. 使用实验内练习 1 中创建的测试计划检查栈的“向下”数组实现，如果发现实现存在错误，进行修正并再次执行测试计划。 ### 1.4 实验内练习 3：表达式分隔符配对检查 编译器和解释器经常需要判断表达式分隔符对是否正确配对，即使它们嵌套多层。栈由于其后进先出（LIFO）的特性，在解决这类问题时非常有用。 操作步骤如下： 1. 将`delim.cs`文件保存为`delim.cpp`文件，并在`delim.cpp`程序文件中实现`delimitersOk`操作。 2. 完善以下测试计划，添加检查`delimitersOk`操作实现是否能正确检测输入表达式中不正确配对的分隔符的测试用例。注意，输入不要求是有效的 C++ 表达式，只要求分隔符使用正确。 3. 执行测试计划，如果发现`delimitersOk`函数的实现存在错误，进行修正并再次执行测试计划。 以下是`delimitersOk`操作的测试计划示例： | 测试用例 | 命令 | 预期结果 | 检查情况 | | ---- | ---- | ---- | ---- | | 带括号的有效表达式 | 3 * (a+b) | true | | | 带混合分隔符的有效表达式 | f[3 * (a+b)] | true | | | 带混合分隔符的无效表达式 | (f[b)–(c+d])/2; | false | | | 空表达式 | 空字符串<换行> | true | | | 括号配对不正确 | a = f[b + 3 | | | ### 1.5 实验后练习 1：字符串排列 给定输入字符串“abc”，判断以下排列哪些可以通过仅包含以下语句对的代码片段输出： ```cpp cin >> ch; permuteStack.push(ch); ``` 和 ```cpp ch = permuteStack.pop(); cout << ch; ``` 其中`ch`是字符，`permuteStack`是字符栈。每个语句对可以在代码片段中重复多次，并且语句对可以按任意顺序排列。 #### 部分 A 对于以下每个排列，给出输出该排列的代码片段或简要解释为什么无法生成该排列： - “abc” - “acb” - “bac” - “bca” - “cab” - “cba” #### 部分 B 给定输入字符串“abcd”，哪些以字符 'd' 开头的四字符排列可以通过上述形式的代码片段输出？为什么只能生成这些排列？ ### 1.6 实验后练习 2：栈抽象数据类型的其他应用 在实验内练习 1 中，我们使用栈来计算算术表达式。思考另一个可以使用栈抽象数据类型的应用，并说明该应用在每个栈数据项中存储的信息类型。 ## 2. 队列抽象数据类型（Queue ADT）实验 ### 2.1 概述 队列是另一种受