Deque（雙端隊(duì)列）：
- 特點(diǎn)：有序集合，有兩個(gè)端部, 首部和尾部，可以在前面或后面添加新項(xiàng)，也可以在任一端移除現(xiàn)有項(xiàng)。
-
Deque抽象數(shù)據(jù)類型
Deque()創(chuàng)建一個(gè)空的新deque。它不需要參數(shù)，返回空的deque。
addFront(item)將一個(gè)新項(xiàng)添加到deque的首部。它需要item參數(shù)并不返回任何內(nèi)容。
addRear(item) 將一個(gè)新項(xiàng)添加到 deque 的尾部。它需要 item 參數(shù)并不返回任何內(nèi)容。
removeFront() 從 deque 中刪除首項(xiàng)。它不需要參數(shù)并返回 item。deque 被修改。
removeRear() 從 deque 中刪除尾項(xiàng)。它不需要參數(shù)并返回 item。deque 被修改。
isEmpty() 測(cè)試 deque 是否為空。它不需要參數(shù)，并返回布爾值。
size() 返回 deque 中的項(xiàng)數(shù)。它不需要參數(shù)，并返回一個(gè)整數(shù)。
image.png
# -*- utf8 -*-
# Deque.py
'''
Deque（雙端隊(duì)列）：
特點(diǎn)：有序集合，有兩個(gè)端部, 首部和尾部，可以在前面或后面添加新項(xiàng)，也可以在任一端移除現(xiàn)有項(xiàng)。
Deque抽象數(shù)據(jù)類型
Deque()創(chuàng)建一個(gè)空的新deque。它不需要參數(shù)，返回空的deque。
addFront(item)將一個(gè)新項(xiàng)添加到deque的首部。它需要item參數(shù)并不返回任何內(nèi)容。
addRear(item) 將一個(gè)新項(xiàng)添加到 deque 的尾部。它需要 item 參數(shù)并不返回任何內(nèi)容。
removeFront() 從 deque 中刪除首項(xiàng)。它不需要參數(shù)并返回 item。deque 被修改。
removeRear() 從 deque 中刪除尾項(xiàng)。它不需要參數(shù)并返回 item。deque 被修改。
isEmpty() 測(cè)試 deque 是否為空。它不需要參數(shù)，并返回布爾值。
size() 返回 deque 中的項(xiàng)數(shù)。它不需要參數(shù)，并返回一個(gè)整數(shù)。
'''
'''
用Python實(shí)現(xiàn)一個(gè)Deque
底層同樣使用列表
假定deque的尾部在列表中的位置為0
在removeFront中，我們使用pop方法從列表中刪除最后一個(gè)元素。
但是，在removeRear中，pop(0)方法必須刪除列表的第一個(gè)元素。因?yàn)閐eque的末尾是列表的開頭，開頭是列表的結(jié)尾。
所以deque從前面添加(列表的末尾)是O(1)，在后面添加(列表的前面)是O(n)
'''
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)
image.png
'''
Deque的實(shí)際應(yīng)用：回文檢查
規(guī)則：對(duì)稱然后首尾相同的字符串就是回文例如 radar toot madam
大概思路：把字符串從左到右每個(gè)字符添加到deque的尾部，全部添加后，再利用deque的雙重功能，
把deque的前后兩邊的第一個(gè)字符移除并且判斷是否相同，如果相同就繼續(xù)取剩下的前后兩邊的字符繼續(xù)判斷，
直到不相同即不是回文，或者deque大小為1或者為0，即回文。
'''
def palchecker(aString):
chardeque = Deque()
for ch in aString:
chardeque.addRear(ch)
stillEqual = True
while chardeque.size() > 1 and stillEqual:
first = chardeque.removeFront()
last = chardeque.removeRear()
if first != last:
stillEqual = False
return stillEqual
print(palchecker("lsdkjfskf"))
print(palchecker("radar"))
# False
# True
