【练习题】二.栈和队列

1.蒋编号为0和[的两个栈存放于一个数组空间 V[m]中，栈底分别处于数组的两端。当第0号栈的栈顶播针 top[0]等F-1 时该戍为空:当第1号栈的栈顶指针 top[I]等于 m 时，该栈为空两个栈均从两端向中间增长 (见图 3.2)。试编写双栈初始化，判渐栈空、栈满、进栈和出栈等算法的两数。双栈数据结构的定义如下:
typedet atruet{
int top[2]， bot[21;
SElemType *V;
int m;

}Dblstack;
//栈顶和栈底指针
//栈数组
//栈最大可容纳元素个数

图 3.2 双栈结构的表示
2.回文是指正读反读均相同的字符序列，如“abba”和“abdba”均是回文，但“good”不回文。试写一个算法判定给定的字符序列是否为回文。( 提示:将一半字符入栈。)

3.设从键盘输人一整数的序列:a，a2，a3，··，an，试编写算法实现:用栈结构存储输人的整数，当a;-1 时，将a;进栈;当a=-1 时，输出栈顶整数并出栈。算法应对异常情况 (人栈满等 )给出相应的信息。

4.从键盘上输人一个后级表达式，试编写算法计算表达式的值。

规定:后缀表达式的长度不超过一行，以“3”作为输人结束，操作数之间用空格分隔，操作符只可能有+、-、*、/四种运算例如:234 34 +2x$。

5. 假设以I和 O 分别表示人栈和出栈操作。栈的初态和终态均为空，人栈和出栈的操作序列可表示为仅由I和 O 组成的序列，称可以操作的序列为合法序列，否则称为非法序列。

(1)下面所示的序列中哪些是合法的?
A.IOIIOIOO  B. IoOIOIIO  C. IIOIOIO   D. mooIoO

(2) 通过对(1)的分析，写出一个算法，判定所给的操作序列是否合法。若合法，返回 true否则返回 false ( 假定被判定的操作序列已存人一维数组中)。

6.假设以带头结点的循环链表表示队列，并且只设一个指针指向队尾元素结点 ( 注意:不设头指针 )，试编写相应的置空队列、判断队列是否为空、人队和出队等算法。

7.假设以数组 2[m]存放循环队列中的元素，同时设置一个标志 tag，以 tag=0和 tag=1来区别在队头指针( front)和队尾指针 (rear)相等时，队列状态为“空”还是“满”。试编写与此结构相应的插人( EnQueue)和删除(DeQueue)算法.

8.如果允许在循环队列的两端都可以进行插人和删除操作。要求:
() 写出循环队列的类型定义;
(2)写出“从队尾删除”和“从队头插人”的算法

9，已知 Ackermann 函数定义如下:n+l
当m=0时
Ack(m,n)=dek(m-1.0)
当m去0,n=0时
Ack(m=l.Ack(m.n-)) 当m去0,n去0时
(1) 写出计算 Aek(m.d)的递归算法、并根据此算法给出 Ack(2,1)的计算过程
(2) 写出计算 aek(m.n)的非递归算法。

10.已知广为单键表的表头指针、链表中存储的都是整型数据，试写出实现下列运算的递归
算法:
(1)求键表中的最大整数:
(2)求链表的结点个数;
(3)求所有整数的平均值。