- 双端队列基础定义
一种有次序的数据集合，与队列相似，但具有两端，称为首端和尾端，但deque数据既可以从队首加入，也可以从队尾加入，数据项也可以从两端移除。（它集成了栈和队列的能力）
- 双端队列抽象数据类型
| Deque() | 创建一个双端队列 |
| addFront(item) | 将item加入队首 |
| addRear(item) | 将item加入队尾 |
| removeFront() | 从队首移除数据项，返回值为所移除的项 |
| removeRear() | 从队尾移除数据项，返回值为所移除的项 |
| isEmpty() | 返回是否为空 |
| size() | 返回deque中包含的数据项的个数 |
python自己建立的Deque：
1 class Deque: 2 def __init__(self): 3 self.items = [] 4 def isEmpty(self): 5 return self.items == [] 6 def addFront(self,item): 7 self.items.append(item) 8 def addRear(self,item): 9 self.items.insert(0,item) 10 def removeFront(self): 11 return self.items.pop() #时间复杂度O(1) 12 def removeRear(self): 13 return self.items.pop(0) #时间复杂度O(n) 14 def size(self): 15 return len(self.items)
- 双端队列的应用
- 回文词判断
回文词：如‘abcdedcba’这样左右对称的字符串。
思路：首先将所需判断的词加入deque，再分别从两端同时移除字符判定是否相同，直到deque中剩下0个或者1个字符。
代码：
1 from deque import Deque 2 3 def palchecker(aString): 4 ''' 5 :param aString: 待判断的字符 6 :return: bool类型 7 ''' 8 chardeque = Deque() 9 10 for ch in aString: 11 chardeque.addRear(ch) 12 stillEqual = True 13 14 while chardeque.size() > 1 and stillEqual: 15 first = chardeque.removeFront() 16 last = chardeque.removeRear() 17 if first != last: 18 stillEqual = False 19 return stillEqual 20 print(palchecker('abcdedcba')) 21 print(palchecker('anshsoba'))
[out]
True
False
Process finished with exit code 0