数据结构(C语言版)严蔚敏 吴伟民主编课件第三章

第三章栈和队列栈和队列是两种特殊的线性表，是操作受限的线性表，称限定性DS§3.1栈（stack）栈的定义和特点定义：限定仅在表尾进行插入或删除操作的线性表，表尾—栈顶，表头—栈底，不含元素的空表称空栈特点：先进后出（FILO）或后进先出（LIFO）ana1a2……...栈底栈顶...出栈进栈栈s=(a1,a2,……,an)栈的存储结构顺序栈实现：一维数组s[M]top=0123450栈空栈顶指针top,指向实际栈顶后的空位置，初值为0top123450进栈Atop出栈栈满BCDEF设数组维数为Mtop=0,栈空，此时出栈，则下溢（underflow)top=M,栈满，此时入栈，则上溢（overflow)toptoptoptoptop123450ABCDEFtoptoptoptoptoptop栈空入栈算法0M-1栈1底栈1顶栈2底栈2顶出栈算法在一个程序中同时使用两个栈链栈栈顶^…...topdatalink栈底结点定义入栈算法出栈算法typedefstructnode{intdata;structnode*link;}JD;^…...栈底toptopxptop^…...栈底topq回文游戏：顺读与逆读字符串一样（不含空格）dadtop1.读入字符串2.去掉空格（原串）3.压入栈4.原串字符与出栈字符依次比较若不等，非回文若直到栈空都相等，回文多进制输出：字符串：“madamimadam”例把十进制数159转换成八进制数(159)10=(237)81598198280237余7余3余2toptop7top73top732表达式求值中缀表达式后缀表达式（RPN)a*b+cab*c+a+b*cabc*+a+(b*c+d)/eabc*d+e/+中缀表达式：操作数栈和运算符栈例计算2+4-3*6操作数运算符24+操作数运算符6-操作数运算符6-36*操作数运算符6-18操作数运算符-12后缀表达式求值步骤：1、读入表达式一个字符2、若是操作数，压入栈，转43、若是运算符，从栈中弹出2个数，将运算结果再压入栈4、若表达式输入完毕，栈顶即表达式值；若表达式未输入完，转1top4top43top735top例计算4+3*5后缀表达式：435*+top415top19§3.4队列队列的定义及特点定义：队列是限定只能在表的一端进行插入，在表的另一端进行删除的线性表队尾(rear)——允许插入的一端队头(front)——允许删除的一端队列特点：先进先出(FIFO)a1a2a3…………………….an入队出队frontrear队列Q=(a1,a2,……,an)队列的顺序存储结构实现：用一维数组实现sq[M]front=0rear=0123450队空123450FrontJ1,J1,J3入队J1J2J3rearrear123450J4,J5,J6入队J4J5J6front设两个指针front,rear,约定：rear指示队尾元素上一位置front指示队头元素初值front=rear=0出队列：x=sq[front++];空队列条件：front==rear队满：rear==Mrearrearfrontrear123450J1,J2,J3出队J1J2J3frontfrontfrontrear入队列：sq[rear++]=x;存在问题设数组长度为M，则：当front=0,rear=M时，再有元素入队发生溢出——真溢出当front0,rear=M时，再有元素入队发生溢出——假溢出解决方案队首固定，每次出队剩余元素向下移动——浪费时间循环队列基本思想：把队列设想成环形，让sq[0]接在sq[M-1]之后，若rear+1==M,则令rear=0;0M-11frontrear实现：利用“模”运算入队：sq[rear%M]=x;rear=(rear+1)%M出队：x=sq[front%M];front=(front+1)%M队满、队空判定条件队空：front==rear队满：front==rear解决方案：1.另外设一个标志以区别队空、队满2.少用一个元素空间(如：0号空间不用)：队空：front==rear队满：(rear+1)%M==frontJ4J5J6012345rearfront初始状态012345rearfrontJ4J5J6012345rearfrontJ9J8J7入队算法：出队算法：链队列结点定义typedefstructnode{intdata;structnode*link;}JD;头结点^…...front队头队尾rear设队首、队尾指针front和rear,front指向头结点，rear指向队尾frontrearx入队^xfrontreary入队x^yfrontrearx出队x^yfrontrear空队^frontreary出队^入队算法出队算法