用python实现Deque双端队列，解决回文词的判定

    双端队列Deque是一种有次序的数据集，跟队列相似，其两端可以称作“首”“尾”端。但deque中数据项既可以从队首加入，也可以从队尾加入；数据项也可以从两端移除。

    从某种意义上说，双端队列集成了栈和队列的能力。    但是双端队列并不具有LIFO和FIFO的特性。

双端队列

    双端队列Deque定义的操作如下：

Deque()：创建一个空的双端队列，无参数，返回值是空队列。

addFront(item)：在队首添加入一个元素，参数是数据项，无返回值。

addRear(item)：在队尾添加入一个元素，参数是数据项，无返回值。

removeFront()：删除队首的元素，不需要参数，返回值是被删除的元素，队列本身有变化。

removeRear()：删除队尾的元素，不需要参数，返回值是被删除的元素，队列本身有变化。

isEmpty()：检测队列是否为空。无参数，返回布尔值。

size()：返回队列元素的个数。无参数，返回一个整数。

用List实现Deque，List下标0作为deque的尾端，List下标-1作为deque的首端：

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)

    其中addFront和removeFront的操作复杂度为O(1)，而addRear和removeRear的操作复杂度为O(n)。

---

    “回文词”判定

  “回文词”指正读和反渎都一样的词，如radar、madam、toot，而用双端队列很容易能解决“回文词”问题。

    首先将需要判定的词从队尾加入deque，再从两端同时移除字符判定是否相同，知道deque中剩下0个或1个字符。

回文词判断

回文词判定的算法如下：

代码

    但是其实python还有更简单的方法判定回文词，如下：

s = input()

a = reversed(list(s))

if list(a) == list(s):

    print('是回文')

else:

    print('不是回文')