概述

双端队列（deque，全名double-ended queue）是一种具有队列和栈性质的线性数据结构。双端队列也拥有两端：队首（front）、队尾（rear），但与队列不同的是，插入操作在两端（队首和队尾）都可以进行，删除操作也一样。

双端队列的数据存储结构可以是顺序表，也可以是链表，即顺序双端队列和链双端队列。

图片.png

双端队列ADT（抽象数据类型）一般提供以下接口：

Deque() 创建双端队列
insert(item) 向队首插入项
append(item) 向队尾插入项
popFront() 返回队首的项，并从双端队列中删除该项
pop() 返回队尾的项，并从双端队列中删除该项
isEmpty() 判断双端队列是否为空
size() 返回双端队列中项的个数
get(index) 返回对列中的对象
show() 对象遍历

操作示意图：

图片.png

顺序双端队列

顺序双端队列是使用顺序表存储数据的双端队列，Python 中的列表元组都属于顺序表，下面使用列表来存储数据，实现顺序双端队列。

class SeQueue(object):def __init__(self):self.__members = list()def isEmpty(self):return not len(self.__members)def show(self):if self.isEmpty():returnfor member in self.__members:if self.__members.index(member) != len(self.__members) - 1:print(member, end=',')else:print(member)def insert(self, data):self.__members.insert(0, data)def append(self, data):self.__members.append(data)def popFront(self):if self.isEmpty():returnreturn self.__members.pop(0)def pop(self):if self.isEmpty():returnreturn self.__members.pop()def size(self):return len(self.__members)def check(self, index):if index < 0 or index > len(self.__members) - 1:raise IndexErrorreturn self.__members[index]

使用
if  name == ' main':
sdq = SeQueue()
print("isEmpty: ", sdq.isEmpty())
sdq.show()
sdq.insert('x')
sdq.insert('z')
sdq.append(10)
sdq.append(20)
sdq.show()
print(sdq.popFront())
print(sdq.pop())
sdq.show()
print("sequence double queue length: ", sdq.size())
print("index member is: ", sdq.check(2))

链双端队列的实现

链双端队列是使用链表存储数据的双端队列，链表是逻辑有序的，由一个一个的节点构成，所以先声明一个创建节点的类。

# coding=utf-8
class Node(object):"""链双端，节点对象类"""def __init__(self, data):self.data = dataself.next = Noneclass LinkQueue(object):"""链表"""def __init__(self):self.__head = Nonedef isEmpty(self):return not self.__headdef show(self):if self.isEmpty():returncur = self.__headwhile cur is not None:if cur.next is not None:print(cur.data, end=',')else:print(cur.data)cur = cur.nextdef insert(self, data):node = Node(data)node.next = self.__headself.__head = nodedef append(self, data):if self.isEmpty():self.insert(data)returnnode = Node(data)cur = self.__headwhile cur.next is not None:cur = cur.nextcur.next = nodedef popFront(self):if self.isEmpty():returncur = self.__headself.__head = self.__head.nextreturn cur.datadef pop(self):if self.isEmpty():returncur = self.__headprev = Nonewhile cur.next is not None:prev = curcur = cur.nextif cur == self.__head:self.__head = self.__head.nextreturnprev.next = cur.nextreturn cur.datadef size(self):size = 0cur = self.__headwhile cur is not None:size += 1cur = cur.nextreturn sizedef get(self, index):if index < 0 or index >= self.size():raise IndexErrorcur = self.__headfor _ in range(index):cur = cur.nextreturn cur.data

用标准库collections.deque实现

from collections import dequeclass Deque:def __init__(self):self.items = deque()def insert(self, item):self.items.appendleft(item)def append(self, item):self.items.append(item)def show(self):if self.isEmpty():returnfor index, value in enumerate(self.items):if index != len(self.items) - 1:print(self.items.__getitem__(index), end=',')else:print(self.items.__getitem__(index))def popFront(self):return self.items.popleft()def pop(self):return self.items.pop()def isEmpty(self):return self.size() == 0def size(self):return len(self.items)def get(self, index):self.items.__getitem__(index)

举例

ldq = Deque()# print("isEmpty: ", ldq.isEmpty())# ldq.show()ldq.insert('X')ldq.insert('Y')ldq.insert('Z')ldq.append(100)ldq.append(200)ldq.append(300)ldq.show()# print(ldq.popFront())# print(ldq.pop())# ldq.show()print("link queue length: ", ldq.size())print("index member is: ", ldq.get(2))

输出

Z,Y,X,100,200,300
link queue length:  6
index member is:  None

应用 - 回文算法

算法：回文（palindrome）是正读反读都一样的单词或句子，是一种修辞方式和文字游戏。
举例：

madam
able was i ere i saw elba
# 中文
花非花
人人为我、我为人人

如果要实现一个 回文验证算法（验证一个给定的字符串是否为回文），使用Deque类将非常容易：将字符串存储到双端队列，同时取出首尾字符并比较是否相等，只要有一对字符不等，则该字符串不是回文；若全部相等，则该字符串为回文。具体代码如下：

#!/usr/bin/env python
# -*- coding: utf-8 -*-
def palchecker(aString):chardeque = Deque()for ch in aString:chardeque.insert(ch)while chardeque.size() > 1:first = chardeque.popFront()last = chardeque.pop()if first != last:return Falsereturn Trueif __name__ == '__main__':str1 = 'able was i ere i saw elba'print('"%s" is%s palindrome' % (str1, '' if palchecker(str1) else ' not'))str2 = u'人人为我、我为人人'print(u'"%s"%s是回文' % (str2, u'' if palchecker(str2) else u'不'))str3 = u"What's wrong 怎么啦"print(u'"%s"%s是回文' % (str3, u'' if palchecker(str3) else u'不'))