Python实现双端队列
关于双端队列的介绍，请参考：栈和队列简介
双端队列的数据存储结构可以是顺序表，也可以是链表，本篇文章使用 Python 来分别实现顺序双端队列和链双端队列。
一、实现顺序双端队列
顺序双端队列是使用顺序表存储数据的双端队列，Python 中的列表元组都属于顺序表，下面使用列表来存储数据，实现顺序双端队列。
# coding=utf-8
class SequenceDoubleQueue(object):
def __init__(self):
self.__members = list()
def is_empty(self):
return not len(self.__members)
def show(self):
if self.is_empty():
print('双端队列为空')
return
for member in self.__members:
if self.__members.index(member) != len(self.__members)-1:
print(member, end='|')
else:
print(member)
def head_enter(self, data):
self.__members.insert(0, data)
def end_enter(self, data):
self.__members.append(data)
def head_outer(self):
if self.is_empty():
return
return self.__members.pop(0)
def end_outer(self):
if self.is_empty():
return
return self.__members.pop()
def length(self):
return len(self.__members)
def check(self, index):
if index < 0 or index > len(self.__members)-1:
raise IndexError
return self.__members[index]定义一个 SequenceDoubleQueue() 类，实例化的时候会创建一个空列表，生成一个空的顺序双端队列。Python 中的列表有很多自带的方法，所以将存储数据的列表设置成私有属性，避免用户在类外面链式调用列表的其他方法。如果用户直接在类外面操作列表，则双端队列只能从两端存取数据的规则可能会被破坏。
下面是顺序双端队列的各个方法实现：
is_empty(): 判断顺序双端队列是否为空。如果存储数据的列表长度为零(对应布尔值False)，则顺序双端队列为空(is_empty为True)，反之。
show(): 展示顺序双端队列中的数据，也就是将双端队列中所有的数据依次打印输出，对存储数据的列表遍历输出即可。
head_enter(data): 前端入队，也就是从队列的前端添加数据到队列中。在本文中，统一将列表的开头当成双端队列的前端，列表的结尾当成双端队列的后端。前端入队调用列表的 insert(0, data) 方法即可。
end_enter(data): 后端入队，也就是从队列的后端添加数据到队列中。后端入队调用列表的 append(data) 方法即可。
head_outer(): 前端出队，也就是从队列中取出前端的数据，并将取出的数据返回。前端出队调用列表的 pop(0) 方法即可。
end_outer(): 后端出队，也就是从队列中取出后端的数据，并将取出的数据返回。后端出队调用列表的 pop() 方法即可。
length(): 返回顺序双端队列的长度。顺序双端队列的长度就是存储数据的列表长度。
check(index): 返回顺序双端队列中指定位置的数据。根据指定的 index 值，将存储数据的列表中对应索引的数据返回即可。
if __name__ == '__main__':
sdq = SequenceDoubleQueue()
print("is_empty: ", sdq.is_empty())
sdq.show()
sdq.head_enter('x')
sdq.head_enter('y')
sdq.head_enter('z')
sdq.end_enter(10)
sdq.end_enter(20)
sdq.end_enter(30)
sdq.show()
print(sdq.head_outer())
print(sdq.end_outer())
sdq.show()
print("sequence double queue length: ", sdq.length())
print("index member is: ", sdq.check(2))运行结果：
is_empty: True
双端队列为空
z|y|x|10|20|30
z
30
y|x|10|20
sequence double queue length: 4
index member is: 10二、实现链双端队列
链双端队列是使用链表存储数据的双端队列，链表是逻辑有序的，由一个一个的节点构成，所以先声明一个创建节点的类。
class Node(object):
def __init__(self, data):
self.data = data
self.next = None下面按照单向链表的方式来实现链双端队列。
class LinkDoubleQueue(object):
def __init__(self):
self.__head = None
def is_empty(self):
return not self.__head
def show(self):
if self.is_empty():
print('双端队列为空')
return
cur = self.__head
while cur is not None:
if cur.next is not None:
print(cur.data, end='|')
else:
print(cur.data)
cur = cur.next
def head_enter(self, data):
node = Node(data)
node.next = self.__head
self.__head = node
def end_enter(self, data):
if self.is_empty():
self.head_enter(data)
return
node = Node(data)
cur = self.__head
while cur.next is not None:
cur = cur.next
cur.next = node
def head_outer(self):
if self.is_empty():
return
cur = self.__head
self.__head = self.__head.next
return cur.data
def end_outer(self):
if self.is_empty():
return
cur = self.__head
prev = None
while cur.next is not None:
prev = cur
cur = cur.next
if cur == self.__head:
self.__head = self.__head.next
return
prev.next = cur.next
return cur.data
def length(self):
length = 0
cur = self.__head
while cur is not None:
length += 1
cur = cur.next
return length
def check(self, index):
if index < 0 or index >= self.length():
raise IndexError
cur = self.__head
for _ in range(index):
cur = cur.next
return cur.data定义一个 LinkDoubleQueue() 类，实例化的时候会创建一个空链表，生成一个空的链双端队列。
下面是链双端队列的各个方法实现：
is_empty(): 判断链双端队列是否为空。如果存储数据的链表头指向空(对应布尔值False)，则链双端队列为空(is_empty为True)，反之。
show(): 展示链双端队列中的数据，也就是将双端队列中所有的数据依次打印输出，对存储数据的链表遍历输出即可。
head_enter(data): 前端入队，也就是从队列的前端添加数据到队列中。在本文中，统一将链表的头当成双端队列的前端，链表的尾当成双端队列的后端。前端入队就是从链表头部添加节点。
end_enter(data): 后端入队，也就是从队列的后端添加数据到队列中。后端入队就是从链表尾部添加节点。
head_outer(): 前端出队，也就是从队列中取出前端的数据，并将取出的数据返回。前端出队就是删除并返回链表头节点的数据。
end_outer(): 后端出队，也就是从队列中取出后端的数据，并将取出的数据返回。后端出队就是删除并返回链表尾节点的数据。
length(): 返回链双端队列的长度。链双端队列的长度就是存储数据的链表长度。
check(index): 返回链双端队列中指定位置的数据。根据指定的 index 值，找到并返回链表中对应位置的节点数据。
ldq = LinkDoubleQueue()
print("is_empty: ", ldq.is_empty())
ldq.show()
ldq.head_enter('X')
ldq.head_enter('Y')
ldq.head_enter('Z')
ldq.end_enter(100)
ldq.end_enter(200)
ldq.end_enter(300)
ldq.show()
print(ldq.head_outer())
print(ldq.end_outer())
ldq.show()
print("link queue length: ", ldq.length())
print("index member is: ", ldq.check(2))运行结果：
is_empty: True
双端队列为空
Z|Y|X|100|200|300
Z
300
Y|X|100|200
link queue length: 4
index member is: 100以上就是用 Python 实现的顺序双端队列及链双端队列。
腾讯云开发者
