栈和队列PPT课件

第三章栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS§3.1栈（stack）栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)栈的存储结构栈顺序存储表示：#defineSTACK_INIT_SIZE100//存储空间初始分配量#defineSTACKINCREMENT10//存储空间分配增量typedefstruct{Selemtype*base;//在栈构造之前和销毁之后，base的值为NULLSelemtype*top;//栈顶指针intstacksize;//当前已分配的存储空间，以元素为单位}sqstack;栈的基本操作：P46base123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEFtop=0,栈空，此时出栈，则下溢top=stacksize,栈满，此时入栈，则上溢toptoptoptoptop123450ABCDEFtoptoptopbasetopbase栈的操作演示：top•构造一个空栈statusinitstack(sqstack&s){s.base=(Selemtype*)malloc(STACK_INIT_SIZE*sizeof(Selemtype));if(!s.base)exit(overflow);s.top=s.base;s.stacksize=STACK_INIT_SIZE;returnOK;}•销毁栈statusdestorystack(sqstack&s){if(!s.base)exit(error);free(s.base);s.base=s.top=NULL;returnOK;}•置栈为空栈statusclearstack(sqstack&s){if(!s.base)exit(error);s.top=s.base;returnOK;}•判空intstackempty(sqstacks){returns.base==s.top;}0M-1栈1底栈1顶栈2底栈2顶在一个程序中同时使用两个栈链栈栈顶^…...top栈底^…...栈底toptopxp入栈top^…...栈底topq出栈栈的应用数值转换例把十进制数159转换成八进制数(159)10=(237)81598198280237余7余3余2toptop7top73top732回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文括号匹配的检验：行编辑程序迷宫求解字符串：“madamimadam”表达式求值中缀表达式后缀表达式（RPN)a*b+cab*c+a+b*cabc*+a+(b*c+d)/eabc*d+e/+中缀表达式：操作数栈和运算符栈(1)对每种运算符赋予一个优先数(2)可以使用两个工作栈：数栈(NS)；运算符栈(OS)。(3)编译程序自左向右扫描至语句结束符，处理的原则是：凡遇到操作数，一律进数栈；当遇到运算符时，则将该运算符的优先数与运算符栈中的栈顶元素的优先数相比较。若该运算符的优先数大，则进栈；反之，则取出栈顶的运算符，并在数栈中连续取出两个栈顶元素作为运算对象进行运算，并将运算结果存入数栈，然后继续比较该运算符与栈顶元素的优先数。例计算2+4-3*6操作数运算符24+操作数运算符6-操作数运算符6-36*操作数运算符6-18操作数运算符12后缀表达式求值步骤：1、读入表达式一个字符2、若是操作数，压入栈，转43、若是运算符，从栈中弹出2个数，将运算结果再压入栈4、若表达式输入完毕，栈顶即表达式值；若表达式未输入完，转1top4top43top735top例计算4+3*5后缀表达式：435*+top415top19§3.2队列队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)——允许插入的一端队头(front)——允许删除的一端队列特点：先进先出(FIFO)a1a2a3…………………….an入队出队frontrear队列Q=(a1,a2,……,an)双端队列a1a2a3…………………….an端1端2入队出队入队出队链队列结点定义typedefstructQNode{Qelemtypedata;structQNode*next;}Qnode,*QueuePtr;头结点^…...front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾typedefstruct{QueuePtrfront;QueeuPtrrear;}LinkQueue;frontrearx入队^xfrontreary入队x^yfrontrearx出队x^yfrontrear空队^frontreary出队^构造空队列销毁队列QstatusInitQueue(LinkQueue&Q){Q.front=Q.rear=(QueuePtr)malloc(sizeof(Qnode));if(!Q.front)exit(overflow);Q.front-next=NULL;returnOK;}statusDestoryQueue(LinkQueue&Q){while(Q.front){Q.rear=Q.front-next;free(Q.front);Q.front=Q.rear;}returnOK;}入队算法出队算法statusEnQueue(LinkQueue&Q,QElemTypee){p=(QueuePtr)malloc(sizeof(QNode));if(!p)exit(overflow);p-data=e;p-next=NULL;Q.rear-next=p;Q.rear=p;returnOK;}statusDeQueue(LinkQueue&Q,QElemType&e){if(Q.front==Q.rear)return(error);p=Q.front-next;e=p-data;Q.front-next=p-next;if(Q.rear==p)Q.rear=Q.front;free(p);returnOK;}队列的顺序存储结构front=-1rear=-1123450队空123450frontJ1,J2,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素；front指示队头元素前一位置初值front=rear=-1空队列条件：front==rear入队列：sq[++rear]=x;出队列：x=sq[++front];rearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfront存在问题设顺序空间为M，则：当front=-1,rear=M-1时，再有元素入队发生溢出—真溢出当front-1,rear=M-1时，再有元素入队发生溢出—假溢出解决方案队首固定，每次出队剩余元素向下移动——浪费时间循环队列基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;0M-11frontrear实现：利用“模”运算入队：rear=(rear+1)%M;sq[rear]=x;出队：front=(front+1)%M;x=sq[front];队满、队空判定条件012345rearfrontJ4J5J6012345rearfrontJ9J8J7J4J5J6012345rearfront初始状态队空：front==rear队满：front==rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间：队空：front==rear队满：(rear+1)%M==front构造空队列队列长度statusinitqueue(sqQueue&Q){Q.base=(Qelemtype*)malloc(MAXQUEUESIZE*sizeof(Qelemtype));if(!Q.base)exit(OVERFLOW);Q.front=Q.rear=0;returnOK;}intqueuelength(sqQueueQ){return(Q.rear-Q.front+MAXQUEUESIZE)%MAXQUEUESIZE;}#defineMAXQUEUESIZE100typedefstruct{Qelemtype*base;intfront，rear;}sqQueue;入队算法出队算法statusEnQueue(SqQueue&Q,QelemTypee){if((Q.rear+1)%MAXQUEUESIZE==Q.front)exit(overflow);Q.rear=(Q.rear+1)%MAXQUEUESIZE;Q.base[Q.rear]=e;returnOK;}statusDeQueue(SqQueue&Q,QelemType&e){if(Q.front==Q.rear)exit(error);Q.front=(Q.front+1)%MAXQUEUESIZE;e=Q.base[Q.front];returnOK;}