第3章栈队列.ppt

本章学习目标 栈的定义、栈的“后进先出”的操作规则； 栈的顺序和链式存储结构； 队列的定义、队列“先进先出”的操作规则； 队列的顺序和链式存储结构; 栈和队列的典型应用 3.1.2 栈的顺序存储结构及运算实现 栈的顺序存储结构（顺序栈 ）是利用利用一批地址连续的存储单元依次存放自栈底到栈顶的数据元素。通常用一维数组来实现栈的顺序存储，数组小下标一端做栈底，设一个栈顶指针top指向栈顶元素，它随着插入和删除而变化。 图(a)是空栈，s.top= -1；图(b)是A入栈，s.top=0，s.elem [0]= A；图(c) 是B、C、D、E四个元素依次入栈之后，s.top=4，由于栈已满，若再入栈，则溢出；图(d)是E、D相继出栈，此时栈中还有3个元素，s.top=2，即栈顶指针指向C元素。 例题：假设有3个元素a，b，c，入栈顺序是a，b，c，则它们的出栈顺序有几种可能？ 3.1.3 栈的链式存储结构及运算实现 栈也可以用单链表作为存储结构。一个链栈由它的栈顶指针唯一确定 。假设 top 是StackNode * 类型的变量，则 top 指向栈顶结点，top=NULL时，链栈为空。 ⑸ 取栈顶元素int GetTop(StackNode *top, ElemType *y)  { if ( Empty_LS(top) ) { printf (“Stack underflow.”) ; /* 下溢 */ return OVERFLOW;} else { *y=top-data ;  return OK ; }} 3.2 队列 3.2.1 队列的定义及基本运算 队列(Queue)也是一种操作受限制的线性表，它只允许在表的一端进行插入，通常称为入队，而在另一端进行删除，通常称为出队。允许出队的一端称为队头(front)，允许入队的一端称为队尾(rear)。 队列的例子：（1）如等待购物的顾客总是按先来后到的次序排成队，先得到服务的顾客是站在队头的先来者，而后到的人总是排在队的末尾。 （2）操作系统中的作业队列也是先进先出结构。 3.2.2 队列的顺序存储结构及运算实现 队列的顺序存储结构和顺序栈类似。由于队列的操作是在两端进行的，采用以下的顺序存储结构： typedef struct { ElemType elem[MAXSIZE] ; int rear, front; /* 队头、队尾指针 */ }SeQueue; 问题引入：当队列处于“队满”状况时，队列的实际可用空间并没有占满。 判断队列是空还是满，有两种处理方法： 1）另设一个标志位以区分队列是空还是满。 3.2.3 队列的链式存储结构及运算实现 用链表表示的队列简称为链队列。在单链表的基础上再增加一个队尾指针，指向链表中的最后一个结点，因此一个链队列由一个队头指针和一个队尾指针唯一地确定，链队列的结构描述如下： 3.3 栈和队列的典型应用 【例3-2】表达式求值 操作数可以是常量或变量；算符包括运算符（+，- ，*，/）和界限符(“(”，“)”，“#”)，它们构成的集合命名为OP。 四则运算的规则： (1)先乘除、后加减； (2)先算括号内，后算括号外，多层括号时，由内向外进行； (3)同一个优先级，先左后右。 若当前字符是操作数时，入操作数OPND栈，是算符时，如果这个算符优先级比栈顶算符优先级高则入OPTR栈，继续向后处理；若这个算符优先级比栈顶算符优先级低，则从操作数栈出栈两个运算量，从算符栈出栈一个算符进行运算，并将其运算结果入操作数栈；若这个算符优先级等于栈顶算符优先级，则从算符栈出栈一个运算符，继续处理当前字符。 【例3-3】栈与递归 一个直接的或间接的调用自身的函数成为递归。递归是程序设计中一个非常重要的方法，它可以使许多问题的结果大大简化。它的优点是逻辑性强，结构清晰。缺点是运行效率较低，时空开销较大。 【例3-6】队列的应用举例 汽车入队算法如下：LQueqe q1,q2,q3;InitQueqe(q1); InitQueue(q2); InitQueue(q3);void carinque() { /* 汽车入队 */int i,x; scanf(“%d,%d”,i,x); if(x1 || x3) printf(“输入汽车类型错误\n”) ; else { switch(