数据结构课后练习题 第3章 栈和队列
7. 按照运算符优先数法，画出对下面算术表达式求值时，操作数栈和运算符栈的变化过程：
9-2*4+(8+1)/3。
8. 设栈S＝（1，2，3，4，5，6，7），其中7 为栈顶元素。写出调用algo 后栈S 的状态。
void algo(Stack *S){ int i=0; Queue Q; Stack T;
InitQueue(Q); InitStack(T);
while(!StackEmpty(S)){
if(i%2==0)
Push(T,Pop(S)); else
EnQueue(Q,Pop(S)); i++; }
while(!QueueEmpty(Q))
Push(S,DeQueue(Q)); while(!StackEmpty(T))
Push(S,Pop(T)); }
五、 设计题
1. 在栈顶指针为 HS 的链栈中，写出计算该链栈中结点个数的函数？
2. 已知 Q 是一个非空队列，S 是一个空栈，使用C 语言编写一个算法，仅用队列和栈的ADT 函数和少量工作
变量，将队列Q 中的所有元素逆置。
栈的ADT 函数有:
void SetEmpty(stack s); //置空栈
void Push(stack s,ElemTye value); //新元素value 进栈 ElemType Pop(stack s); //出栈，返回栈顶值 Boolean IsEmptyS(stack s); //判断栈空否 队列ADT 的函数有：
void EnQueue(Queue q,ElemType value); //元素入队 ElemType DeQueue(Queue q); //出队列返回队头值 Boolean IsEmptyQ(Queue q); //判断队列是否为空
3. 用单链表实现队列，如下图所示，并令 front=rear=NULL 表示队列为空，编写实现队列的如下五种运算的函数。
Setnull:将队列置成空队列。
getfirst:返回队列的第一个元素。 enqueue:把元素插入队列的后端。 dequeue:删除队列的第一个元素。 empty:判定队列是否为空。
6/7
北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1
数据结构课后练习题 第3章 栈和队列
4. 有 A,B,C 三个塔座，A 上套有n 个直径不同的圆盘，按直径从大到小叠放，形如宝塔,编号1,2,3??n。要求
将n 个圆盘从A 移到C，叠放顺序不变，移动过程中遵循下列原则：
a) 每次只能移一个圆盘
b) 圆盘可在三个塔座上任意移动
c) 任何时刻，每个塔座上不能将大盘压到小盘上
5. 回文游戏：顺读与逆读字符串一样（不含空格）
6. 数制转换：对于输入的任意一个非负十进制数,打印输出与其等值的八进制数。（利用栈） 7. 括号匹配检验：假设在表达式中有三种括号（ ）{ } [ ]，检查表达式括号是否配对。
8. 行编辑程序问题：在用户输入一行的过程中，允许用户输入出差错，并在发现有误时可以及时更正。
要求： 设立一个输入缓冲区，用以接受用户输入的一行字符，然后逐行存入用户数据区，并假设“#”为退
格符，“@”为退行符。（利用栈来完成）
7/7
北京理工大学珠海学院计算机学院 “数据结构”课程组编制 2011-3-1