数据结构与算法(Python语言描述)课件栈和对列

第三章栈和队列2016Fall《数据结构》2020/3/291数学科学学院栈（Stack）2020/3/292数学科学学院什么是栈？top2020/3/293数学科学学院toptoptoptop只允许在一端插入和删除的线性表top：插入删除端，栈顶特点：后进先出(LIFO)push：入栈pop：出栈、退栈getTop：查看栈顶元素栈的基本操作2020/3/29数学科学学院4top=None空栈toptoptoptoptopa进栈b进栈aababcdee进栈abcdef进栈溢出abdee退栈c2020/3/295数学科学学院c退栈b退栈aba退栈空栈topabdd退栈ctopabctop2020/3/296数学科学学院top=Noneeadecdebcdeabcde此时，再pop则非法！__init__(self)创建空栈is_empty(self)判断栈是否为空，空返回truepush(self,elem)入栈，使elem成为新的栈顶pop(self)弹出栈顶，若栈为空，抛出异常top(self)查看栈顶，若栈为空，抛出异常ADTStack2020/3/29数学科学学院7top始终指向栈顶元素！顺序栈2020/3/298数学科学学院a1a2a3a6a0a4a5maxSizeelemstoptop始终指向栈顶元素！顺序栈2020/3/299数学科学学院a2a3a6a0a4a5maxSizeelemstop栈顶在链头！链式栈（带头结点）topa0a5a62020/3/2910数学科学学院栈顶在链头！链式栈（不带头结点）2020/3/2911数学科学学院topa0a5a6^队列（Queue）2020/3/2912数学科学学院在一端删除，在另一端插入的线性表删除端叫队头(head)，插入端叫队尾(tail)。特性：先进先出(FIFO,FirstInFirstOut)什么是队列？a0a1a2an-1headtail2020/3/2913数学科学学院enqueue：入队列，进队•在队尾插入元素。dequeue：出队列•删除队头元素peek：取队头元素•查看队列的基本操作2020/3/29数学科学学院14__init__(self)创建队列is_empty(self)判断队列是否为空，空返回trueenqueue(self,elem)入对列，使elem成为新的队尾dequeue(self)出对列，若对列为空，抛出异常peek(self)查看队头，若对列为空，抛出异常ADTQueue2020/3/29数学科学学院15a0∧an-1…Q.headQ.tailQ.headQ.tail∧空队列链队列（带头结点）2020/3/29数学科学学院16a0a1∧an-1…Q.headQ.tail^^Q.headQ.tail空队列链队列（不带头结点）2020/3/29数学科学学院17headtail空队列headtailB进队ABheadtailA进队AheadtailC,D进队ABCD顺序队列——进队2020/3/2918数学科学学院headtailA退队BCDheadtailE,F,G进队CDEFGheadtailB退队CDCDEFGheadtailH进队,假溢出！顺序队列——出队2020/3/2919数学科学学院head指向队头元素tail指向队尾元素的下一个位置maxSize最大空间长初始时：head=tail=0入队列：先填入元素，再tail+=1出队列：先记下元素，再head+=1进队、出队原则2020/3/2920数学科学学院队空《==》head==tail队满《==》tail==maxSize假溢出的解决：队列数组首尾相接，形成循环队列。空、满的判别2020/3/2921数学科学学院01234567head01234567head01234567headtailAABCtailtail空队列A进队B,C进队2020/3/2922数学科学学院0123456701234567A退队B退队01234567D,E,F,G,H进队headBCtailAheadBCtailheadCtailDEFGH2020/3/2923数学科学学院head指向队头元素tail指向队尾元素的下一个位置maxSize最大空间长初始化：head=tail=0入队列：head=(head+1)%maxSize出队列：tail=(tail+1)%maxSize循环队列2020/3/2924数学科学学院问题：head==tail？？？删除时，head+1后使得head==tail时，队列为空。插入时，tail+1后使得head==tail时，队列为满。空、满的判别2020/3/2925数学科学学院方法1：增设一个标志变量Tag，初值为0。入队列操作时置为1，出队列时置为0。方法2：少占用一个数据空间，即最大的使用空间是maxSize-1，禁止tail追上head。队满《==》(tail+1)%MAXSIZE==head队空《==》head==tail解决办法2020/3/2926数学科学学院对于顺序结构，空间满时，要考虑空间的追加！一般的顺序表顺序栈顺序队列基本认识！！！2020/3/29数学科学学院27