[文学]第四章栈和队列.ppt

第4章 栈和队列,4.1 栈 ( Stack ) 4.1.1栈的定义,栈：一种运算受限的线性表 只允许在一端插入和删除 栈顶(top) 栈底(bottom) 具有后进先出(LIFO)特点,4.1.2 栈的抽象数据类型 ADT STACK IS Data： 一个栈S，假定用标识符StackType表示栈对象类型 Operation: void InitStack (StackType /清空 end STACK,InitStack(a); /初始化a Push(a,18); /18进栈 int x=46; Push(a,x); /46进栈 Push(a,x/3); /15进栈 x=Pop(a); /15出栈，x=15 coutPeek(a); /读取栈顶元素46并输出 Pop(a); / 46出栈 EmptyStack (a); /返回false，因为栈非空 coutPop(a);endl; /屏幕显示18，18出栈 x=EmptyStack (a); /返回x=1，因为栈空,练习： 1.有a,b,c三个元素依次进栈，任何时候都可以出栈，共有多少种出栈次序？ a,b,c a,c,b b,a,c b,c,a c,b,a 2.P173习题4-1,4.2栈的顺序存储结构和操作实现,top - 栈顶 栈空 top =-1 栈满 top=MaxSize-1 Struct Stack ElemType stackMaxSize; int top; 进栈/出栈都在栈顶进行 时间复杂度为O（1）,动态分配数组空间,Struct Stack ElemType *stack; int top; int MaxSize; ,1.初始化栈S为空 void InitStack(Stack ,2.元素item进栈，即插入到栈顶 void Push(Stack ,2.元素item进栈，即插入到栈顶 void Push(Stack ,3. 删除栈顶元素并返回 ElemType Pop(Stack ,4.读取栈顶元素的值 ElemType Peek(Stack ,5.判断S是否为空,若是则返回ture，否则返回false bool EmptyStack (Stack ,6.清除栈S中的所有元素，释放动态存储空间 void ClearStack(Stack ,链栈：是一个单链表，表头结点是栈顶，表尾结点 是栈尾，只能对表头进行操作。,4.2栈的链接存储结构和操作实现,栈的运算在链接存储结构上的实现 （1）初始化链栈 void InitStack(SNode * ,（2）向链栈中插入一个元素 void Push(SNode* ,newptr,（3）从链栈中删除一个元素并返回 ElemType Pop(SNode* ,data next,HS,（4）读取栈顶元素 ElemType Peek(SNode * HS) if(HS=NULL) cerrdata; ,HS,（5）检查链栈是否为空 bool EmptyStack (SNode * HS) return HS=NULL; （6）清除链栈为空 void ClearStack(SNode * ,HS,4.5 算术表达式的计算,4.5.1 算术表达式的两种表示,1. 中缀算术表达式： 双目运算符出现在两个操作数中间的表达式 如：a+b 中缀算术表达式计算必须遵守以下三条规则： （1）先计算括号内，后计算括号外； （2）先乘除，后加减； （3）同一优先级运算，从左向右依次进行；,2. 后缀算术表达式（逆波兰式）： 双目运算符出现在两个操作数后面的表达式。 如:a b + 特点：不存在括号，不存在优先级的差别，计算过程完全按照运算符出现的先后次序进行，整个计算过程只需扫描表达式一次就可完成。 例：（12-4）/5 中缀表达式 12 4 5 / 后缀表达式,中缀表达式转换成后缀表达式的规则： 按照运算符的优先级，对中缀表达式作以下处理： 将运算符移到运算对象后面，相邻与其最后一个运算对 象，删除掉所有的括号。 后缀算术表达式的运算： 3/5+6 - 3 5 / 6 + 16-9*(4+3) - 16 9 4 3 + * - 2*(x+y)/(1-x) - 2 x y + * 1 x - / (25+x)*(a*(a+b)+b)25 x + a a b + * b + * 特点：运算对象的相对次序不变,4.5.2 后缀表达式求值的算法 设置一个栈，扫描后缀表达式中的各个字符， 如果扫描到的是运算对象（操作数），将其压栈，若是运算符，则从栈中弹出两个数据进行运算，然后将运算结果压栈，依此类推，直到扫描完所有的字符为止，此时，栈中只剩一个数据，即是算术表达式运算后的最后结果。,4.7 队列 ( Queue ),4.7.1 队列的定义运算受限的线性表 队列是只允许在一端删除，在另一端插入的线性表 允许删除的一端叫做队头(front)，允许插入的一端叫做队尾(rear) 插入称进队(入队), 删除称离队(出队) 先进先出(FIFO, First In First Out),4.4.2 队列的抽象数据类型 ADT QUEUE is Data: 一个队列Q，QueueType为存储类型 Operation(基本操作): void InitQueue(QueueType end QUEUE,假定有一个队列q，其元素类型为整型int，下面给出调 用上述操作的一些例子。 (1) InitQueue(q); /把队列q置为一个空队列 (2) EnQueue(q,35); /元素35进队，队列为（35） (3) int x=12; EnQueue(q,2*x+3); /元素2*x+3的值27进队，此时队列为（35,27） (4) EnQueue(q,-16); /元素-16进队，此时队列为(35,27,-16) (5) coutPeekQueue(q)endl; /输出队首元素35,原队列保持不变 (6) OutQueue(q); OutQueue(q); /依次删除队列元素35和27，此时队列为(-16) (7)while(!EmptyQueue(q) coutOutQueue(q)“ “; /依次输出队列q中的所有元素,练习：利用栈实现队列的运算 void EnQueue(s1,x) stack s1; int x; if(s1-top=n) cout“队列已满！”endl; else push(s1,x); ,void OutQueue(s1,s2,x) stack s1,s2; int x; s2.top=-1; while(!EmptyStack(s1) push(s2,pop(s1); x=pop(s2); while(!EmptyStack(s2) push(s1,pop(s2); ,bool EmptyQueue(s1) stack s1; if(EmptyStack(s1) return ture; else return false; ,4.7.3 队列的顺序存储结构和操作实现 使用数组和两个整型变量分别存储队首和 队尾元素的下标位置 struct Queue ElemType queueMaxSize; int front, rear; ;,队列的进队和出队,front = rear =0 时,初始化； 进队时队尾指针先进1 rear = rear + 1，再写入， rear 指向尾元素 出队时队头指针先进1 front = front + 1，再删除， front 指向队列头元素 当frontrear时，队列是什么状态呢？ 规定：让front指向队首元素的前一单元的位置。 当frontrear时，队列为空 注意：数组长度为N，队列只能使用其中的N-1个。,假设数组长度为N，则 （1）当front0，rearN1时， 队满，入队则溢出（真溢出） （2）当front！0，rearN1时， 入队也会溢出（假溢出） 解决方案： （1）队首固定：每次出队后，剩余元素向前移动，队首元素永远在数组第一个位置上。 缺点：造成大量数据的移动，浪费时间 （2）循环队列：利用模运算,存储队列的数组被当作首尾相接的表处理。 队头、队尾指针加1时从maxSize -1直接进到0，可用语言的取模(余数)运算实现。 队头指针进1: front = (front + 1) % MaxSize; 队尾指针进1: rear = (rear + 1) % MaxSize; 队列初始化：front = rear = 0; 队空条件：front = rear; 队满条件：(rear + 1) % MaxSize = front 队列元素个数：(rear-front+Maxsize)%Maxsize 插入和删除的时间复杂度为O（1）；,一般情况,练习： 栈和队列的共同点是_ A. 都实先进后出 B. 都是先进先出 C. 只允许在端点处插入和删除元素 D. 没有共同点,C,2. 已知一个栈的进栈序列是1，2，3，n，其输出序列是p1,p2,pn,若p1=n,则pi= _ A. i B. n-i C. n-i+1 D.不确定,C,3.将递归算法转换成对应的非递归算法时，通常需要使用_保存中间结果 A. 队列 B. 栈 C. 链表 D.树,B,4. 元素A、B、C、D依次进顺序栈后，栈顶元素是_，栈底元素是_ A. A B.B C.C D.D,D,A,5. 元素A、B、C、D顺序连续进入队列qu后，队头元素是_，队尾元素是_ A. A B.B C.C D.D,A,D,6. 若用一个大小为6的数组来实现循环队列，且当rear和front的值分别为0和3.当从队列中删除一个元素，再加入两个元素后，rear和front的值分别为多少？ A. 1和5 B.2和4 C.4和2 D.5和1,B,7. 设栈S和队列Q的初始状态为空，元素e1、e2、e3、e4、e5和e6依次通过栈S，一个元素出栈后即进入队列Q，若6个元素出队的序列是e2、e4、e3、e6、e5、e1，则栈S的容量至少应该是_。 A.6 B.4 C.3 D.2 8.若tail=32指向队尾元素，head=15指向队头元素的前一个空位置，队列空间m=60，则循环队列中元素数目是_。 A. 42 B. 16 C.17 D.41,C,C,判断题 1.栈和队列都是限制存取点的线性结构。 2.有n个数顺序（依次）进栈，出栈序列有Cn种，即： 3.即使对不含相同元素的同一输入序列进行两组不同的、合法的入栈和出栈组合操作，所得的输出序列也一定相同。 4.消除递归不一定需要使用栈。 5.栈的输入序列为123n，输出序列为a1a2an，若ai=n（1iai+1an.,4.7.3 队列的顺序存储结构和操作实现 使用数组和两个整型变量分别存储队首和队尾元素的下标位置 struct Queue ElemType queueMaxSize; int front, rear; ; ElemType *queue=new ElemTypen; /动态分配数组空间,队列运算在顺序存储结构上的实现 （1） 初始化队列 void InitQueue(Queue ,Q.rear,（3） 检查一个队列是否为空 bool EmptyQueue (Queue ,（5） 插入一个元素 void EnQueue (Queue ,（6） 删除一个元素 ElemType OutQueue (Queue ,（7） 检查一个队列是否为满 bool QueueFull(Queue ,4.7.4. 队列的链接存储结构和操作实现 由独立结点构成的单链表,队头在链头，队尾在链尾。队首指针指向真正的队首结点 链式队列在进队时无队满问题，但有队空问题。 队空条件为 front = NULL 或rear =NULL,struct LinkQueue LNode * front; LNode * rear; ; struct LNode ElemType data; LNode *next; ;,front,rear,front,x,rear,x,rear,y,x,rear,y,front,front,p,p,p,队列运算在链接存储结构上的实现 （1） 初始化链队 void InitQueue(LinkQueue ,（2） 向链队中插入一个元素 void EnQueue (LinkQueue ,（3） 从队列中删除一个元素 ElemType OutQueue(LinkQueue ,（4） 读取队首元素 ElemType PeekQueue (LinkQueue ,（5） 检查链队是否为空 bool EmptyQueue(LinkQueue /HQ.rear=NULL,（6） 清除链队中的所有元素，使之变为空队 void ClearQueue(LinkQueue ,练习： 1. InitQueue(Q); int a5=6,12,5,15,8; for(int I=0;I5;I+) QInsert(Q,aI); QInsert(Q,QDelete(Q); QInsert(Q,20); QInsert(Q,QDelete(Q)+16); While(!QEmpty(Q) CoutQDelete(Q)” “;,QInsert() 入队 QDelete() 出队 QEmpty() 判认空 InitQueue() 队列初始化,结果：5 15 8 6 20 28,2. InitStack(S); Push(S,30); Push(S,40); Push(S,50); int x=Pop(S)+2*Pop(S); Push(S,x); int I,a4=5,8,12,15; for (I=0;I3;I+) Push(S,ai); While(!StackEmpty(S) CoutPop(S)” “;,结果:12 8 5 130 30,3. 设栈的输入序列为123n,输出序列为a1,a2,a3an,若存在1=k=n使得ak=n,则当k=i=n时，ai为_ A n-i+1 B n-(i-k) C 不确定 4.后缀表达式转化为中缀表达式 a b c + * d a