数据结构与算法十二双端队列 [复制链接]

1.双端队列抽象数据类型及Python

?双端队列Deque是一种有次序的数据集，跟队列相似，其两端可以称作“首”“尾”端，但deque中数据项既可以从队首加入，也可以从队尾加入；数据项也可以从两端移除。某种意义上说，双端队列集成了栈和队列的能力

?但双端队列并不具有内在的LIFO或者FIFO特性如果用双端队列来模拟栈或队列需要由使用者自行维护操作的一致性

?deque定义的操作如下：

Deque()：创建一个空双端队列

addFront(item)：将item加入队首

addRear(item)：将item加入队尾

removeFront()：从队首移除数据项，返回值为移除的数据项removeRear()：从队尾移除数据项，返回值为移除的数据项

isEmpty()：返回deque是否为空

size()：返回deque中包含数据项的个数

?采用List实现

List下标0作为deque的尾端

List下标-1作为deque的首端

?操作复杂度

addFront/removeFrontO(1)

addRear/removeRearO(n)

?“回文词”指正读和反读都一样的词

如radar、madam、toot中文

“上海自来水来自海上”

“山东落花生花落东山”

?用双端队列很容易解决“回文词”问题

先将需要判定的词从队尾加入deque再从两端同时移除字符判定是否相同，直到deque中剩下0个或1个字符

classDequeef__init__(self):self.items=[]defisEmpty(self):returnself.items==[]defaddFront(self,item):self.items.append(item)defaddRear(self,item):self.items.insert(0,item)defremoveFront(self):returnself.items.pop()defremoveRear(self):returnself.items.pop(0)defsize(self):returnlen(self.items)

frompythonds.basic.dequeimportDequedefpalchecker(aString):chardeque=Deque()forchinaString:chardeque.addRear(ch)stillEqual=Truewhilechardeque.size()1andstillEqualirst=chardeque.removeFront()last=chardeque.removeRear()iffirst!=last:stillEqual=FalsereturnstillEqualprint(palchecker("lsdkjfskf"))print(palchecker("radar"))

数据结构与算法（一）

数据结构与算法（二）数据结构与算法（三）

数据结构与算法（四）-栈的实现

数据结构与算法（五）-栈的应用

数据结构与算法（六）-栈的应用

数据结构与算法（七）

数据结构与算法（八）-栈的应用

数据结构与算法（九）队列抽象数据类型

数据结构与算法（十）

数据结构与算法（十一）队列的应用

扫描下方