注：本文如涉及到代碼，均經(jīng)過(guò)Python 3.7實(shí)際運(yùn)行檢驗(yàn)，保證其嚴(yán)謹(jǐn)性。
本文閱讀時(shí)間約為5分鐘。
雙端隊(duì)列Deque
雙端隊(duì)列(Deque)是一種有次序的數(shù)據(jù)集，跟隊(duì)列相似，其兩端可以稱作“首”、“尾”端，但deque中數(shù)據(jù)項(xiàng)既可以從隊(duì)首加入，也可以從隊(duì)尾加入，同時(shí)數(shù)據(jù)項(xiàng)也可以從兩端移除。
某種意義上說(shuō)，雙端隊(duì)列集成了棧和隊(duì)列的能力。但是，雙端隊(duì)列并不具有內(nèi)在的后進(jìn)先出(LIFO)或先進(jìn)先出(FIFO)的特性。如果要用雙端隊(duì)列來(lái)模擬棧或隊(duì)列，那么需要使用者自行維護(hù)操作的一致性。
雙端隊(duì)列的Python實(shí)現(xiàn)及操作
跟棧、隊(duì)列一樣，我們選擇使用Python的列表來(lái)實(shí)現(xiàn)雙端隊(duì)列。
代碼如下：
# 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)
注意，上述代碼對(duì)雙端隊(duì)列的實(shí)現(xiàn)是：列表的隊(duì)首是雙端隊(duì)列的隊(duì)尾，列表的隊(duì)尾是雙端隊(duì)列的隊(duì)首，即list[0]是雙端隊(duì)列的隊(duì)尾，list[-1]是雙端隊(duì)列的隊(duì)首。
上述操作的時(shí)間復(fù)雜度：
addFront/removeFront——O(1)。
addRear/removeRear——O(n)。
雙端隊(duì)列(deque)的操作如下：
- Deque()——?jiǎng)?chuàng)建一個(gè)空雙端隊(duì)列。
- .addFront(item)——將item加入隊(duì)首。
- .addRear(item)——將item加入隊(duì)尾。
- .removeFront()——從隊(duì)首移除數(shù)據(jù)項(xiàng)，返回值為移除的數(shù)據(jù)項(xiàng)。
- .removeRear()——從隊(duì)尾移除數(shù)據(jù)項(xiàng)，返回值為移除的數(shù)據(jù)項(xiàng)。
- .isEmpty()——返回deque是否為空的布爾值。
- .size()——返回deque中包含數(shù)據(jù)項(xiàng)的個(gè)數(shù)。
- .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 #查看雙端隊(duì)列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']
雙端隊(duì)列的應(yīng)用：句子回文結(jié)構(gòu)的判定
對(duì)句子回文結(jié)構(gòu)的判定是雙端隊(duì)列的一個(gè)典型應(yīng)用。
這里回文結(jié)構(gòu)指的是一個(gè)字符串是對(duì)稱的，該字符串從左到右讀和從右到左讀是完全一樣的。有一句很出名的回文結(jié)構(gòu)的句子，'able was i ere i saw elba'，傳言是拿破侖說(shuō)的，翻譯成中文意思是"看到Elba島之前我無(wú)所不能"，Elba島是拿破侖最后一次戰(zhàn)敗后被流放的一個(gè)小島，而且最后他死在了Elba島。
回文結(jié)構(gòu)的句子例子還有很多，比如'radar'、'madam'、'toot'、'山東落花生花落東山'、'上海自來(lái)水來(lái)自海上'、北京輸油管油輸京北'等。
回文結(jié)構(gòu)的特殊性使得雙端隊(duì)列很容易對(duì)其進(jìn)行處理。分兩步解決回文結(jié)構(gòu)的判定：
第一步，將需要判定的回文結(jié)構(gòu)的字符串按順序提取出來(lái)加入到雙端隊(duì)列中。
第二步，同時(shí)從兩端移除單個(gè)字符，看其是否相同，直到雙端隊(duì)列中剩下的字符串的長(zhǎng)度為0或1。字符串的長(zhǎng)度為奇數(shù)還是偶數(shù)，不影響對(duì)其回文結(jié)構(gòu)的判定。
具體判定的代碼如下：
# 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() # 新建一個(gè)雙端隊(duì)列。
# 將需要判定的回文結(jié)構(gòu)的字符串按順序提取出來(lái)加入到雙端隊(duì)列中
for ch in aString:
chardeque.addRear(ch)
stillEqual = True
# 同時(shí)從兩端移除單個(gè)字符，看其是否相同，直到雙端隊(duì)列中剩下的字符串的長(zhǎng)度為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.
