您好,登錄后才能下訂單哦!
這篇文章給大家分享的是有關(guān)Python中如何實(shí)現(xiàn)雙端隊(duì)列Dequeue的內(nèi)容。小編覺得挺實(shí)用的,因此分享給大家做個(gè)參考,一起跟隨小編過來看看吧。
雙端隊(duì)列Dequeue
雙端隊(duì)列是一種有序的數(shù)據(jù)集,與隊(duì)列相似,但雙端隊(duì)列的兩端都可以作為隊(duì)首和隊(duì)尾(即數(shù)據(jù)在兩端都可以刪除和插入)
某種意義上來說,雙端隊(duì)列Dequeue集合了棧和隊(duì)列的功能,Dequeue既可以實(shí)現(xiàn)棧也可以實(shí)現(xiàn)隊(duì)列
雙端隊(duì)列的操作:
Dequeue() | 創(chuàng)建一個(gè)雙端隊(duì)列 |
addFront() | 隊(duì)首加入數(shù)據(jù) |
addFear() | 隊(duì)尾加入數(shù)據(jù) |
removeFront() | 隊(duì)首刪除數(shù)據(jù) |
removeFear() | 隊(duì)尾刪除數(shù)據(jù) |
size() | 雙端隊(duì)列元素個(gè)數(shù) |
isEmpty() | 是否為空 |
雙端隊(duì)列使用實(shí)例:
雙端隊(duì)列代碼:
雙端隊(duì)列應(yīng)用——“回文詞”判定
“回文詞”:正讀和反讀都一樣的詞
例:radar(雷達(dá)),madam,foot,“上海自來水來自海上”,“山東落花生花落”
算法:利用雙端隊(duì)列Dequeue,先將字符串加入雙端隊(duì)列,再?gòu)膬啥碎_始移除判斷是否相同,最后剩一個(gè)字符
代碼:
所有代碼:
class Dequeue():
"""雙端隊(duì)列"""
def __init__(self):
self.items = []
def addFront(self, item):
self.items.append(item)
def addFear(self, item):
self.items.insert(0, item)
def removeFront(self):
"""時(shí)間復(fù)雜O(1)"""
return self.items.pop()
def removeFear(self):
"""時(shí)間復(fù)雜度O(n)"""
return self.items.pop(0)
def size(self):
return len(self.items)
def isEmpty(self):
return self.items == []
def check_backwords(backwords):
"""回文詞判斷"""
check_dequeue = Dequeue()
mark = True
for word in backwords:
check_dequeue.addFront(word)
while check_dequeue.size() > 1 and mark:
# 從兩端取出數(shù)據(jù)進(jìn)行對(duì)比
check1 = check_dequeue.removeFear()
check2 = check_dequeue.removeFront()
if check1 != check2:
mark = False
return mark
感謝各位的閱讀!關(guān)于“Python中如何實(shí)現(xiàn)雙端隊(duì)列Dequeue”這篇文章就分享到這里了,希望以上內(nèi)容可以對(duì)大家有一定的幫助,讓大家可以學(xué)到更多知識(shí),如果覺得文章不錯(cuò),可以把它分享出去讓更多的人看到吧!
免責(zé)聲明:本站發(fā)布的內(nèi)容(圖片、視頻和文字)以原創(chuàng)、轉(zhuǎn)載和分享為主,文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng),如果涉及侵權(quán)請(qǐng)聯(lián)系站長(zhǎng)郵箱:is@yisu.com進(jìn)行舉報(bào),并提供相關(guān)證據(jù),一經(jīng)查實(shí),將立刻刪除涉嫌侵權(quán)內(nèi)容。