注：本文如涉及到代码，均经过Python 3.7实际运行检验，保证其严谨性。
本文阅读时间约为5分钟。
双端队列Deque
双端队列(Deque)是一种有次序的数据集，跟队列相似，其两端可以称作“首”、“尾”端，但deque中数据项既可以从队首加入，也可以从队尾加入，同时数据项也可以从两端移除。
某种意义上说，双端队列集成了栈和队列的能力。但是，双端队列并不具有内在的后进先出(LIFO)或先进先出(FIFO)的特性。如果要用双端队列来模拟栈或队列，那么需要使用者自行维护操作的一致性。
双端队列的Python实现及操作
跟栈、队列一样，我们选择使用Python的列表来实现双端队列。
代码如下：
# deque.py
class Deque:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def addFront(self, item):
self.items.append(item)
def addRear(self, item):
self.items.insert(0,item)
def removeFront(self):
return self.items.pop()
def removeRear(self):
return self.items.pop(0)
def size(self):
return len(self.items)
注意，上述代码对双端队列的实现是：列表的队首是双端队列的队尾，列表的队尾是双端队列的队首，即list[0]是双端队列的队尾，list[-1]是双端队列的队首。
上述操作的时间复杂度：
addFront/removeFront——O(1)。
addRear/removeRear——O(n)。
双端队列(deque)的操作如下：
- Deque()——创建一个空双端队列。
- .addFront(item)——将item加入队首。
- .addRear(item)——将item加入队尾。
- .removeFront()——从队首移除数据项，返回值为移除的数据项。
- .removeRear()——从队尾移除数据项，返回值为移除的数据项。
- .isEmpty()——返回deque是否为空的布尔值。
- .size()——返回deque中包含数据项的个数。
- .items——以列表形式返回deque中所有元素。
操作的代码示例如下：
# deque.py
class Deque:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def addFront(self, item):
self.items.append(item)
def addRear(self, item):
self.items.insert(0,item)
def removeFront(self):
return self.items.pop()
def removeRear(self):
return self.items.pop(0)
def size(self):
return len(self.items)
d = Deque()
d.isEmpty()
Out[12]: True
d.addRear(4)
d.addRear('dog')
d.addFront('cat')
d.items #查看双端队列d中的所有元素。
Out[17]: ['dog', 4, 'cat']
d.addFront(True)
d.items
Out[19]: ['dog', 4, 'cat', True]
d.isEmpty()
Out[20]: False
d.size()
Out[21]: 4
d.addRear(8.4)
d.removeRear()
Out[23]: 8.4
d.removeFront()
Out[24]: True
d.items
Out[25]: ['dog', 4, 'cat']
双端队列的应用：句子回文结构的判定
对句子回文结构的判定是双端队列的一个典型应用。
这里回文结构指的是一个字符串是对称的，该字符串从左到右读和从右到左读是完全一样的。有一句很出名的回文结构的句子，'able was i ere i saw elba'，传言是拿破仑说的，翻译成中文意思是"看到Elba岛之前我无所不能"，Elba岛是拿破仑最后一次战败后被流放的一个小岛，而且最后他死在了Elba岛。
回文结构的句子例子还有很多，比如'radar'、'madam'、'toot'、'山东落花生花落东山'、'上海自来水来自海上'、北京输油管油输京北'等。
回文结构的特殊性使得双端队列很容易对其进行处理。分两步解决回文结构的判定：
第一步，将需要判定的回文结构的字符串按顺序提取出来加入到双端队列中。
第二步，同时从两端移除单个字符，看其是否相同，直到双端队列中剩下的字符串的长度为0或1。字符串的长度为奇数还是偶数，不影响对其回文结构的判定。
具体判定的代码如下：
# deque.py
class Deque:
def __init__(self):
self.items = []
def isEmpty(self):
return self.items == []
def addFront(self, item):
self.items.append(item)
def addRear(self, item):
self.items.insert(0,item)
def removeFront(self):
return self.items.pop()
def removeRear(self):
return self.items.pop(0)
def size(self):
return len(self.items)
def palchecker(aString):
chardeque = Deque() # 新建一个双端队列。
# 将需要判定的回文结构的字符串按顺序提取出来加入到双端队列中
for ch in aString:
chardeque.addRear(ch)
stillEqual = True
# 同时从两端移除单个字符，看其是否相同，直到双端队列中剩下的字符串的长度为0或1。
while chardeque.size() > 1 and stillEqual:
first = chardeque.removeFront()
last = chardeque.removeRear()
if first != last:
stillEqual = False
return stillEqual
print(palchecker('lsfdfa'))
print(palchecker('abbccbba'))
<<<
False
True
<<<
To be continued.
