第三章栈和队列栈栈的基本定义及运算栈的顺序结构及运算例：堆栈的插入、删除操作。入栈操作程序段：voidpush(stack,x)structstack_strustack;intx;{if(stack.top==m)printf(“Thestackisoverflow!\n”);else{stack.top++;stack.s[stack.top]=x;}}多个栈共享邻接空间为了尽量避免上溢(栈满)、下溢(栈空)，充分利用存储空间，采用多个栈共享同一块内存空间。栈的链式结构及运算链表结构的出栈操作程序如下：typedefstructnode{intdata;structnode*next;};voidpop_link(top,y)structnode*top;int*y;{structnode*p;if(top==NULL)printf(“Thestackisempty!\n”);else{p=top;*y=p→data;top=p→next;free(p);}}链表结构入栈操作程序段：voidpush_link(top,x)structnode*top;intx;{structnode*p;p=(structnode*)(malloc(sizeof(structnode)));p→data=x;p→next=top;top=p;}栈的应用运算符的优先关系处理：由于运算符存在优先关系，对表达式求值时，遇到一个运算符g1时，不能马上执行计算，需向右扫描下一个运算符g2，通过比较其优先关系，才能决定如何操作:(如5＋3×2－1)1）g1>g2：g2优先级低于g1，此时执行g1的运算；2）g1＝g2：g2优先级等于g1，此时执行g1的运算；3）g1<g2：g2优先级高于g1，此时不执行运算，继续扫描下一个运算符。求值过程中栈的变化：实现运算符优先法需要两个栈：1）一个运算符栈OPR，存放暂时不能处理的运算符；2）一个操作数栈OPD，存放操作数和中间结果。栈的处理规则：1）遇到操作数时，将其压入操作数栈；2）遇到运算符时，栈外当前运算符g2要与栈顶运算符g1比较优先级，分情况处理：高于栈顶g1，则当前运算符g2入栈；低于栈顶g1，则栈顶运算符g1出栈，且在OPD栈依次弹出两个操作数a、b，执行“c＝bg1a”规定的运算，并将运算结果c压入操作数栈OPD；3）当运算符栈为空时，表达式求值结束，此时求值结果在操作数栈中。OPDOPR二、递归递归函数的特点：由两部分组成：1)一个是递归调用部分，每递归调用一次使问题规模减小；2)一个是递归终止条件来结束递归过程。阶乘中的n＝＝0即是递归终止条件。因此，递归函数的一般形式：if(终止条件)执行语句；else递归调用；在高级语言编制的程序中，调用函数与被调用函数之间的控制转移和信息交换是通过栈来进行的。函数嵌套调用的实现方法：在程序运行期间，当一个函数调用另一个函数时，调用之前，需先完成三件事:1).将所有的实在参数、返回地址等信息传递给被调用函数保存;2).为被调用函数的局部变量分配存储区;3).将控制转移到被调用函数的入口。另一方面，被调用函数执行后需返回到调用函数，在返回之前，应该完成:1).保存被调函数的计算结果;2).释放被调函数的数据区;3).依照被调函数保存的返回地址将控制转移到调用函数。递归与函数嵌套调用的关系四、可利用空间表队列的定义及运算队列的运算：Create(Queue):初始化操作；Empty(Queue):判空函数；Full(Queue):判满函数；EnQueue(Queue,e):入队列操作；DeQueue(Queue,e):出队列操作；Length(Queue):求队列所含元素数目。队列的顺序存储不能充分利用存储容量m的分析从图中队列中队头、队尾指针的变化状态分析，在当F＝3，R＝4时，队尾指向最后一个存储单元，队尾已经没有空间了，无法继续进行入队操作，即发生了“上溢”。但是，很明显，整个存储空间中还有三个单元是空的，因此这种溢出称为“假溢出”。如何解决这种“假溢出”现象呢？－－循环队列循环队列F=3例如：把如右图所示的队列，转换成循环队列的形式。循环队列：设向量Q(0:m-1)表示队列，Q(0)表示队首，Q(m-1)表示队尾，而Q(0)接在Q(m-1)后面形成一个环，顺时针方向旋转，头指针F总是在顺时针方向上落后于队列中第一个元素位置，而尾指针R总是指向最后加入的那个元素位置。循环队列的指针状态变化：当F＝（R＋1）modm时，为满队，不能插入，此方法少用一个元素空间。1）3＝(2＋1)modm2）0＝[(