Python数据结构—双端队列

2022-01-06

双端队列是与队列类似的有序集合，它有前后两端，元素在其中保持自己的位置，并且可在任一端添加和移除元素，是一种更灵活的数据结构。

# python实现双端队列
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)

# 双端队列应用：回文检测器
'''回文是指从左往右和从右往左读都一样的字符串，例如toot，radar。利用双端队列的特性，可以将字符串从队列后端压入，然后同时从前端、后端读取第i个字符，直到队列中所有字符被遍历（偶数个字符），或剩下最中间的一个字符。即实现了回文字符串的判定'''
def palchecker(String):
    chardeque = Deque()

    for ch in String:
        chardeque.addRear(ch)

    stillEqual = True

    while chardeque.size() > 1 and stillEqual:
        first = chardeque.removeFront()
        last = chardeque.removeRear()
        if first != last:
            stillEqual = False

    return stillEqual