实验二栈与队列操作实验目的：(1)理解栈与队列的结构特征和运算特征，以便在实际问题背景下灵活运用。
(2)了解复杂问题的递归算法设计。
本次实验中，下列实验项目选做一。
1、顺序栈的基本操作[问题描述]设计算法，实现顺序栈的各种基本操作[基本要求]（1）初始化栈s。
（2）从键盘输入10个字符以$结束，建立顺序栈。
（3）从键盘输入1个元素，执行入栈操作。
（4）将栈顶元素出栈。
（5）判断栈是否为空。
（6）输出从栈顶到栈底元素。
要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。
2、链栈的基本操作[问题描述]设计算法，实现链栈的各种基本操作[基本要求]（1）初始化栈s。
（2）从键盘输入10个字符以$结束，建立带头结点的链栈。
（3）从键盘输入1个元素，执行入栈操作。
（4）完成出栈操作。
（5）判断栈是否为空。
（6）输出从栈顶到栈底元素。
（7）输出链栈的长度。
要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。
3、循环队列的基本操作[问题描述]设计算法，实现循环顺序队列的建立、入队、出队等操作。
[基本要求]（1）从键盘输入10个字符以$结束，建立循环队列，并显示结果。
（2）从键盘输入1个元素，执行入队操作，并显示结果。
（3）将队头元素出队，并显示结果。
（4）要求程序通过一个主菜单进行控制，在主菜单界面通过选择菜单项的序号来调用各功能函数。
4、只用尾指针表示的循环链表队列的综合操作[问题描述]假设以带头结点的的循环链表表示队列，并且只设一个指针指向队尾元素的结点（注意不设头指针），试编写队列初始化、入队、出队函数。
[基本要求及提示]（1）首先定义链表结点类型。
（2）编写带头结点的循环链表的初始化函数，只用尾指针表示。
（3）编写入队函数、出队函数。
（4）在主函数中编写菜单（1.初始化；2.入队；3.出队；4.退出），调用上述功能函数。
5、用标志域表示队空队满状态的循环队列的综合操作[问题描述]要求循环队列不损失一个空间全部都得到利用，设置一个标志域tag，以0和1来区分当队头与队尾指针相同时队列状态的空和满，试编写与此结构相对应的入队和出队操作。
[基本要求及提示]（1）教材中为区分当队头与队尾指针相同时队列状态的空和满，以牺牲一个空间的代价来实现的，空：Q->front==Q->rear,满：（Q->rear+1）%MAXSIZE==Q->front。
（2）本题不损失一个空间全部都得到利用，为此如下定义循环队列类型：Typedef struct{ QueueElementType element[MAXSIZE];int front;int rear;int tag;}SeqQueue;此时，循环队列空和满的条件分别为： Q->front==Q->rear&&tag==0 和Q->front==Q->rear&&tag==1（3）编写入队函数、出队函数。
（4）在主函数中编写菜单（1.入队；2.出队；3.退出），调用上述功能函数。
6、利用辅助数组进行栈的逆置[问题描述]利用辅助栈将栈中的元素逆置。
[基本要求及提示]在主函数中编写菜单（1.入栈；2.出栈；3.逆置；4.退出）调试运行程序。
7、利用辅助栈进行队列的逆置[问题描述]利用辅助栈进行队列元素逆置。
[基本要求及提示]在主函数中编写菜单（1.入队；2.出队；3.逆置；4.退出）调试运行程序。
8、Hanoi塔问题[问题描述]现在有三根相邻的柱子，标号为A,B,C。
A柱子上从下到上按金字塔状叠放着n个不同大小的圆盘，现在把所有盘子一个一个移动到柱子B上，并且每次移动同一根柱子上都不能出现大盘子在小盘子上方，请问至少需要多少次移动。
[基本要求及提示]Hanoi塔问题。
（要求4个盘子移动，输出中间结果）9、数制转换问题[问题描述]将十进制数N转换为d进制数。
[基本要求及提示]对于键盘输入的任意一个非负的十进制整数，打印输出与其等值的八进制数。
算法提示:十进制数N转换为d进制数，基于如下原理：即除d取余法。
例如：（1348）10=（2504）8N N div 8 N mod 81348 168 4168 21 021 2 52 0 2由于上述的计算过程是从低位到高位顺序产生的八进制数的各个数位。
而打印输出时，应从高位到低位进行，恰好和计算过程相反。
因此可以先将计算过程中得到的八进制数的各个位进栈，待相对应的八进制数的各位均产生以后，再使其按顺序出栈，并打印输出。
即得到了与输入的十进制数相对应的八进制数。
10、回文判断[问题描述及提示]编写程序，判断依次读入的一个以@为结束符的字母序列是否为回文，即是否为形如“序列1&序列2”模式。
其中序列1与序列2中都不含字符“&”，且序列2是序列1的逆序列。
例如，“a+b&b+a”属于该模式的字符序列，而“1+3&3-1”则不属于该模式。
算法提示：从左到右扫描字符序列,序列1首先进栈，然后序列1出栈并与序列2的字符依次比较。
11、括号匹配的检验[问题描述]从键盘输入任意括号序列，编程判断括号是否匹配。
假设允许有三种括号：圆括号()、方括号[]和花括号{}，其嵌套的顺序随意。
如：{}(()[]）或[([][])]等为正确嵌套格式，{[(])}或{(((])为不正确的格式。
[基本要求及提示]输入{2*[3+4]+（4+5）-10}，输出结果“此序列括号匹配”。
输入 {[（）]，输出结果“此序列括号不匹配”。
算法提示：为了正确检验输入序列的括号匹配问题，要使用栈结构来实现。
（1）在检验算法中建立一个栈，读入圆括号、方括号和大括号组成的序列；（2）若是左括号直接入栈，等待同类的右括号与之匹配；若读入的是右括号，不入栈，若与当前栈顶的左括号为同类括号，则二者匹配，将栈顶的左括号出栈，否则属于不合法的情况；（3）如果序列已读尽，而栈中仍有待匹配的左括号，或读入一个右括号，而栈已空，则均属不合法情况。
（4）当输入序列与栈同时变空，则说明所有括号完全匹配。
12、表达式求值[问题描述]编程求算术表达式的值。
[基本要求及提示]程序能根据表达式中运算符的优先级处理表达式，正确输出运算结果。
简化问题，表达式中出现的操作数可用变量代替。
算法提示：（1）规定运算符的优先级。
（2）设置两个栈：OVS（运算数栈）、OPTR（运算符栈）。
（3）自左向右扫描表达式，进行如下处理：①遇到运算数，则进OVS栈；②遇到运算符，则与栈顶运算符进行优先级比较：大于（>）栈顶运算符，则将当前运算符进OPTR的栈;不大于（<=）栈顶运算符，则OPTR退栈一次，得栈顶运算符θ，将OVS栈退栈了两次，得运算数a和b，执行aθb运算，得到结果T，将T进OVS栈。
13、打印杨辉三角[问题描述]利用队列打印杨辉三角。
如图2-1所示。
11 11 2 11 3 3 11 4 6 4 11 5 10 10 5 11 6 15 20 15 6 1图2-1 杨辉三角形[基本要求]按三角形的形式输出N=7时的杨辉三角。
14、模拟医院患者排队候诊[问题描述]患者医院看病过程：先在诊室外等候，再看病治疗。
排队过程中做两件事：患者到达诊室时将病历交给护士，排入等候的队列的尾部候诊（队尾入队）；二是护士从等候的队列中取出下一个患者的病历（队头元素出队），让患者进入诊室就诊。
[基本要求及提示]在排队时，按照“先到先服务”的原则。
“患者到达”用a表示；“护士让下一位患者就诊”用n表示；“不再接收患者排队”用q表示。
（1）当有“患者到达”命令时，则执行入队操作；（2）当有“护士让下一位患者就诊”命令时，则对头元素出队，进行诊疗；（3）当有“不再接收患者排队”命令时，则队列中所有元素出队，程序结束。
（4）要求程序通过主菜单进行控制，通过选择菜单项的序号来调用各功能函数。
15、键盘输入缓冲区的问题[问题描述]有两个进程同时存在于一个程序中。
其中第一个进程在屏幕上连续显示‘A’字符，与此同时，程序不断检测是否有键盘输入，如果有，就读如用户键入的字符并保存到输入缓冲区中。
在用户输入时键入的字符不立即显示在屏幕上。
当用户渐入’;’或’,’时，第一个进程结束，第二个进程从缓冲区中依次读取用户输入的字符，并显示在屏幕上。
第二个进程结束后，程序又进入第一个进程，重新显示‘A’，同时用户又可以继续键入字符，直到用户键入‘.’时，第二个进程结束。
另外，当输入缓冲区满后，强行中止第一个进程，进入第二个进程。
[基本要求及提示]（1）输入缓冲区采用循环队列模拟。
（2）首先定义循环队列类型，编写队列的基本操作函数，如初始化、判空、判满、入队、出队等。
编写主函数。
参考教材p98算法3.25。