第3章 栈和队列.ppt

1、第3章 栈和队列,3.1 栈 3.2 栈的应用举例 3.3 栈与递归的实现(不讲) 3.4 队列,学习要点,1理解栈的逻辑结构定义及特点 2掌握栈的顺序存储结构的描述 3重点掌握顺序栈上的基本运算 4了解栈的广泛应用 5理解队列的逻辑结构定义及特点 6掌握顺序队列存储结构及其的描述方法 7掌握循环顺序队列的结构 8. 重点掌握循环队列的基本运算 9. 掌握顺序队列和循环队列判断“满”和空的条件,3.1 栈,3.1.1 抽象数据类型栈的定义 1. 栈的定义：仅在表尾插入和删除的线性表。 LIFO(Last-in First -out)的线性表 栈底：表头； 栈顶：表尾。 2.栈的基本操作： 初始

2、化，判空，入栈，出栈， 取栈顶元素，置空，求长度,栈底,栈顶,a1,a2,an,出栈,进栈,3.1.2 栈的表示和实现,typedef struct SElemType * base; SElemType * top; int stacksize; SqStack;,# define STACK_INIT_SIZE 100; # define STACKINCREMENT 10;,栈的基本运算有如下几种： （1）InitStack(S) 主要功能是：初始化操作，构造一个空栈操作。 （2）DestroyStack(S) 主要功能是：将已经存在的栈销毁。 （3）ClearStack(S) 主要功能

3、是：将已经存在的栈清空。 （4）StackEmpty(S) 主要功能是：判断栈是否为空，若S为空，则返回TRUE,否则返回FALSE。 （5）StackLength(S) 主要功能是：返回当前栈中元素的个数。,（6）GetTop(S) 主要功能是：若栈S不空，则取栈顶元素的值，注意栈顶元素不被删除，栈顶指针top也不被改变。 （7）Push(S, x) 主要功能是：入栈操作，在S栈的顶部插入一个元素x，栈顶位置由top指针指出。 （8）Pop(S) 主要功能是：出栈操作，若栈S不空，则在栈顶删除栈顶元素，并返回被删除元素的值。 （9）DisplayStack 主要功能是：栈的遍历操作，即从栈底

4、到栈顶逐次显示栈中的元素。,3.1.2 栈的表示和实现,顺序栈的操作, 1. 入栈,status push(SqStack /push, 2. 出栈,status pop(SqStack /pop, 其他操作的实现由同学们自己完成,思考题：如果进栈的数据元素序列为A、B、C、D，则可能得到的出栈序列有多少种？写出全部可能的序列。,3.2 栈的应用举例,3.2.1 数制转换 十进制N和其它进制数的转换是计算机实现计算的基本问题,其解决方法很多,其中一个简单算法基于下列原理: N=(n div d)*d+n mod d ( 其中:div为整除运算,mod为求余运算) 例如 (1348)10=(25

5、04)8，其运算过程如下：,n n div 8 n mod 8 1348 168 4 168 21 0 21 2 5 2 0 2,结果,3.2.2 括号匹配的检验,假设表达式中充许括号嵌套,则检验括号是否匹配的方法可用“期待的急迫程度”这个概念来描述。例： （）（） （） 在算法中设置一个栈，每读入一个括号，若是左括号则将其压入栈中，若是右括号，则弹出栈顶元素，或是不合法的情况。 算法开始与结束时都应该为空。,3.2.3 行编辑程序,在编辑程序中，设立一个输入缓冲区，用于接受用户输入的一行字符，然后逐行存入用户数据区。允许用户输入错误，并在发现有误时可以及时更正。 例如：用一个退格符“#”表示

6、前一个字符无效；用一个退行符“”表示当前行字符无效。 假如从终端接收了以下两行字符： whli#ilr#e(s#*S) outchaputchar(*s=#+); 则实际有效的是下列两行： while(*S) putchar(*s+)；,行编辑程序算法如下: void lineedit( ) initstack(s); ch=gether( ); while(ch!=eof) while(ch!=eof / switch,ch=getchar( ); / second while clearstack(s); if(ch!=eof) ch=gethar( ); / first while de

7、stroystack(s); / end of lineedit,3.2.4 迷宫求解,入口,出口,3.2.5 算术表达式求值,算符优先法,2 + - * / ( ) # 1 + - * / ( # =,算符间的优先关系,两个工作栈：OPTR-寄存运算符；OPND-寄存操作数或运算结果,算法基本思想,（1）置OPND为空栈，“#”为OPTR的栈底元素； （2）依次读入表达式中字符，若是操作数则进OPND栈；若是运算符则与OPTR的栈顶元素比较：若运算符栈顶元素，则运算符进OPTR栈；若运算符=栈顶元素，则栈顶元素出栈；若运算符栈顶元素，则OPND出栈两个元素， OPTR出栈一个元素，运算后再入

8、OPND栈。,表达式 3*（7-2）求值过程,算术表达式求值算法,OperandType EvaluateExpression() InitStack(OPTR); Push(OPTR,#); InitStack(OPND); c=getchar(); while (c!=# | GetTOp(OPTR)!= # ) if (! In(c,OP) Push(OPND,c); c=getchar(); else switch (Precede(GetTOp(OPTR),c) case ; Pop(OPTR,theta); Pop(OPND,b); Push(OPND,Operate(a,thet

9、a,b); break; return GetTop(OPND); ,3.4 队 列,3.4.1 抽象数据类型队列的定义 队列(Queue)也是一种运算受限的线性表。它只允许在表的一端进行插入，而在另一端进行删除。允许删除的一端称为队头(front)，允许插入的一端称为队尾(rear)。 因此队列亦称作先进先出(First In First Out)的线性表，简称FIFO表。 当队列中没有元素时称为空队列。在空队列中依次加入元素a1,a2,an之后，a1是队头元素，an是队尾元素。显然退出队列的次序也只能是a1,a2,an ，也就是说队列的修改是依先进先出的原则进行的。,下图是队列的示意图：

10、a1a2an,出队,入队,队头,队尾,队列的抽象数据定义见书59,3.4.2 链队列-队列的链式表示和实现,用链表方式表示的队列称为链队列。,data next,元素入队： Status EnQueue(LinkQueue ,3.4.3 循环队列队列的顺序表示和实现,队列的顺序存储结构称为顺序队列，顺序队列实际上是运算受限的顺序表，和顺序表一样，顺序队列也是必须用一个向量空间来存放当前队列中的元素。由于队列的队头和队尾的位置是变化的，因而要设两个指针和分别指示队头和队尾元素在队列中的位置，它们的初始值在队列初始化时均应置为。入队时将新元素插入所指的位置，然后将尾指针加。出队时，删去所指的元素，

11、然后将加头指针并返回被删元素。由此可见，当头尾指针相等时队列为空。在非空队列里，头指针始终指向队头元素，而尾指针始终指向队尾元素的下一位置。,5 4 3 2 1 0,Q.front,Q.rear,5 4 3 2 1 0,Q.front,Q.rear,Q.rear,5 4 3 2 1 0,Q.front,Q.rear,Q.front,5 4 3 2 1 0,空队列,a,b,c相继入队,a,b相继出队,d,e,f相继入队之后，c,d相继出队,Q.front,Q.rear,1,0,maxsize-1,循环队列示意图,0,1,2,3,4,5,J5,J4,J3,Q.front,Q.rear,0,1,2,3,4,5,Q.front,Q.rear,0,1,2,3,4,5,J5,J4,J3,Q.front,Q.rear,J6,J7,J8,队列满,队列空,一般情况,如何判断队列是 “空”还是 “满”? (1)另设一个标志位 (2) 少用一个元素空间,循环队列的顺序存储结构,# define MAXQSIZE 100; typedef struct QElemType *base; int front; int rear;