3.3双端队列抽象数据类型及Python实现+回文词判定-（Python进阶-数据结构与算法）课件

双端队列抽象数据类型及Python实现 数据结构与算法（Python版） ❖ 双端队列Deque是一种有次序的数据集， 跟队列相似，其两端可以称作“首 ”“尾 ”端， 但deque中数据项既可以从队首加入，也可以从 队尾加入；数据项也可以从两端移除。 某种意义上说，双端队列集成了栈和队列的能力 双端队列Deque：什么是Deque？ 数据结构与算法（Python版） 00 ❖ 但 双端 队 列并 不 具有 内 在的LI FO 或 者 FIFO特性 如果用双端队列来模拟栈或队列 需要由使用者自行维护操作的一致性 双端队列Deque：什么是Deque？ 数据结构与算法（Python版） 00 ❖ deque定义的操作如下： Deque()：创建一个空双端队列 addFront(item)：将item加入队首 addRear(item)：将item加入队尾 removeFront()：从队首移除数据项，返回值为 移除的数据项 removeRear()：从队尾移除数据项，返回值为 移除的数据项 isEmpty()：返回deque是否为空 size()：返回deque中包含数据项的个数 数据结构与算法（Python版） 抽象数据类型Deque 00 双端队列操作 双端队列内容 返回值 d=Deque() [] Deque object d.isEmpty() [] True d.addRear(4) [4] d.addRear('dog') ['dog',4,] d.addFront('cat') ['dog',4,'cat'] d.addFront(True) ['dog',4,'cat',True] d.size() ['dog',4,'cat',True] 4 d.isEmpty() ['dog',4,'cat',True] False d.addRear(8.4) [8.4,'dog',4,'cat',Tr ue] d.removeRear() ['dog',4,'cat',True] 8.4 d.removeFront() ['dog',4,'cat'] True 数据结构与算法（Python版） 抽象数据类型Deque 00 ❖ 采用List实现 List下标0作为 deque的尾端 List下标-1作为 deque的首端 ❖ 操作复杂度addFront/removeFront O(1) addRear/removeRear O(n) 数据结构与算法（Python版） Python实现ADT Deque 00 ❖ “回文词”指正读和反读都一样的词 如radar、madam、toot 中文“上海自来水来自海上 ” “山东落花生花落东山” 数据结构与算法（Python版） “回文词”判定 00 ❖ 用双端队列很容易解决“回文词”问题 先将需要判定的词从队尾加入deque 再从两端同时移除字符判定是否相同，直到 deque中剩下0个或1个字符 数据结构与算法（Python版） “回文词”判定 00 数据结构与算法（Python版） “回文词”判定：代码 00 ❖ 线性数据结构Linear DS将数据项以某种 线性的次序组织起来 ❖ 栈Stack维持了数据项后进先出LIFO的次 序 stack的基本操作包括push, pop, isEmpty ❖ 队列Queue维持了数据项先进先出FIFO 的次序 queue的基本操作包括enqueue, dequeue, isEmpty 数据结构与算法（Python版） 线性结构小结 00 ❖ 书写表达式的方法有前缀prefix、 中缀 infix和后缀postfix三种 由于栈结构具有次序反转的特性，所以栈结构适 合用于开发表达式求值和转换的算法 ❖ “模拟系统 ”可以通过一个对现实世界问 题进行抽象建模 ， 并加入随机数动态运行 , 为复杂问题的决策提供各种情况的参考 队列queue可以用来进行模拟系统的开发 数据结构与算法（Python版） 线性结构小结 00 ❖ 双端队列Deque可以同时具备栈和队列的 功能 deque的主要操作包括addFront, addRear, removeFront, removeRear, isEmpty ❖ 列表List是数据项能够维持相对位置的数 据集 ❖ 链表的实现 ， 可以保持列表维持相对位置 的特点 ， 而不需要连续的存储空间 ❖ 链表实现时 ， 其各种方法 ， 对链表头部 head需要特别的处理 数据结构与算法（Python版） 线性结构小结 00 ❖ 有序表是一种数据项依照其某可比性质( 如整数大小、 字母表先后） 来决定在列表 中的位置 ❖ 越“小 ”的数据项越靠近列表