编写算法实现双端队列,

　　本文给大家带来一些关于python的知识，包括deque的相关问题，包括deque的基本概念，deque的实现，以及deque的应用。希望对你有帮助。

0. 学习目标

1. 双端队列的基本概念

；dequee(dequee)也是线性表，插入和删除操作都限制在序列的两端，但不同于栈和队列，dequee的限制很少。对于队列，队列的最前面和最后面。新元素可以被添加到队列的头部和尾部。类似地，可以从任意一端移除现有元素。从某种意义上说，deque可以被认为是堆栈和队列的组合。

　　虽然deque具有栈和队列的许多特性，但它不需要按照这两种数据结构定义的LIFO原理和FIFO原理来操作元素。

　　00-1010除了添加和删除元素，队列还有初始化、判断队列间隙、求队列长度等辅助操作。具体来说，deque的抽象数据类型定义如下：

　　基本操作：

　　1.__itit__():初始化deque

　　创建一个空队列。

　　2.Size () 3360查找并返回包含在队列中的n个元素。

　　如果队列为空，则返回整数0。

　　3.ISEMPTY () 3360确定它是否为空队列。

　　确定元素是否存储在队列中。

　　4.addfront(data):德克团队负责人添加元素

　　将元素数据插入队列头。

　　5.Addear (data) 3360在队列组的末尾添加元素

　　在队列末尾插入元素数据

　　6.删除deque团队领导元素。

　　删除并返回队列头元素。

　　7 7.removerear():删除德雀队的tail元素。

　　删除并返回尾部元素。

　　00-1010和普通队列一样，deque也有两种存储表示：顺序存储和链式存储。

　　00-1010类似于顺序队列。dequee的顺序存储结构使用一组地址连续的存储单元，依次存储从dequee头到dequee尾的元素。同时，需要前后两个指针分别指示队列头元素和队列尾元素的位置。初始化空队列时，front=rear=0。当一个元素入队时，rear增加1，而当一个元素出队时，front增加1。同时，为了重用空闲空间，我们假设最后一个空间和第一个空间被顺序deque(具体原因参考顺序队列)视为连续空间：

　　类似地，顺序deque可以是固定长度和动态长度。当队列已满时，固定长度顺序队列将抛出队列已满异常，而动态顺序队列将动态申请空闲空间。

　　00-1010序列dequee的初始化需要四条信息：deque list用于存储数据元素，max_size用于存储队列列表的最大长度，front和rear分别用于记录队列头元素和队列尾元素的索引：

　　Deque:级

　　def __init__(self，max_size=6):

　　self.max_size=max_size

　　self . deque=[None]* self . max _ size

　　self.front=0

　　Self.rear=0

1.1 双端队列的基本概念

因为front和rear分别用于记录head和tail元素的索引，因为

　　此我们可以方便的计算出双端队列的长度；同时我们需要考虑双端队列为循环队列，front 可能大于 rear，不能直接通过 rear-front，我们需要利用公式计算解决此问题：

　　Python 实现如下：

 def size(self):
　　 return (self.rear-self.front+self.max_size) % self.max_size

2.1.3 判双端队列空

根据 front 和 rear 的值可以方便的判断双端队列是否为空：

 def isempty(self):
　　 return self.rear==self.front

2.1.4 判双端队列满

根据 front 和 rear 的值可以方便的判断双端队列是否还有空余空间：

 def isfull(self):
　　 return ((self.rear+1) % self.max_size == self.front)

2.1.5 双端队列队头和队尾添加元素

添加元素时，需要首先判断双端队列中是否还有空闲空间，然后根据双端队列为定长顺序双端队列或动态顺序双端队列，添加元素操作稍有不同：
[定长顺序双端队列的添加元素操作] 如果队满，则引发异常：

 # 注意队头和队尾修改索引的添加元素的不同顺序
　　 def addrear(self, data):
　　 if not self.isfull():
　　 self.deque[self.rear] = data
　　 self.rear = (self.rear+1) % self.max_size else:
　　 raise IndexError("Full Deque Exception")
　　 def addfront(self, data):
　　 if self.isfull():
　　 self.resize()
　　 if self.isempty():
　　 # 当双端队列
　　 self.deque[self.rear] = data
　　 self.rear = (self.rear+1) % self.max_size else:
　　 self.front = (self.front - 1 + self.max_size) % self.max_size
　　 self.deque[self.front] = data

[动态顺序双端队列的添加元素操作] 如果双端队列满，则首先申请新空间，然后再执行添加操作：

 def resize(self):
　　 new_size = 2 * self.max_size
　　 new_deque = [None] * new_size
　　 d = new_size - self.max_size for i in range(self.max_size):
　　 new_deque[(self.front+i+d) % new_size] = self.deque[(self.front+i) % self.max_size]
　　 self.deque = new_deque
　　 self.front = (self.front+d) % new_size
　　 self.max_size = new_size 
　　 # 注意队头和队尾修改索引的添加元素的不同顺序
　　 def addrear(self, data):
　　 if self.isfull():
　　 self.resize()
　　 self.deque[self.rear] = data
　　 self.rear = (self.rear+1) % self.max_size def addfront(self, data):
　　 if self.isfull():
　　 self.resize()
　　 self.front = (self.front - 1 + self.max_size) % self.max_size
　　 self.deque[self.front] = data

与动态顺序队列类似，我们同样需要考虑复制之后的索引，否则可能出现存在不能用的空闲空间：

　　添加元素的时间复杂度为 $O (1)$ 。虽然当动态顺序双端队列满时，原双端队列中的元素需要首先复制到新双端队列中，然后添加新元素，但参考《顺序表及其操作实现》中顺序表追加操作的介绍，由于 n 次添加元素操作的总时间 $T (n)$ 与 $O (n)$ 成正比，因此其摊销时间复杂度可以认为 $O (1)$ 。

2.1.6 删除队头或队尾的元素

若双端队列不空，则删除并返回指定端元素：

 # 注意队头和队尾修改索引的删除元素的不同顺序
　　 def removefront(self):
　　 if not self.isempty():
　　 result = self.deque[self.front]
　　 self.front = (self.front+1) % self.max_size return result else:
　　 raise IndexError("Empty Deque Exception")
　　 def removerear(self):
　　 if not self.isempty():
　　 self.rear = (self.rear - 1 + self.max_size) % self.max_size
　　 result = self.deque[self.rear]
　　 return result else:
　　 raise IndexError("Empty Deque Exception")

2.2 链双端队列的实现

双端队列的另一种存储表示方式是使用链式存储结构，因此也常称为链双端队列，其中 addfront 操作和 addrear 操作分别是通过在链表头部和尾部插入元素来实现的，而 removefront 操作和 removerear 操作分别是通过从头部和尾部删除结点来实现的。为了降低在尾部删除结点的时间复杂度，接下来基于双向链表实现双端队列。

2.2.1 双端队列结点

双端队列的结点实现与双向链表并无差别：

class Node:
　　 def __init__(self, data=None):
　　 self.data = data
　　 self.next = None
　　 def __str__(self):
　　 return str(self.data)

2.2.2 双端队列的初始化

双端队列的初始化函数中，使其队头指针 front 和队尾指针 rear 均指向 None，并初始化双端队列长度：

class Deque:
　　 def __init__(self):
　　 self.front = None
　　 self.rear = None
　　 self.num = 0

2.2.3 求双端队列长度

返回 num 的值用于求取双端队列的长度，如果没有 num 属性，则需要遍历整个链表才能得到双端队列长度：

 def size(self):
　　 return self.num

2.2.4 判双端队列空

根据双端队列的长度可以很容易的判断其是否为空双端队列：

 def isempty(self):
　　 return self.num <= 0

2.2.5 添加元素

双端队列添加元素时，可以在队尾或队头插入新元素，因此需要修改 rear 和 front 指针，并且同时也要修改结点的 next 和 previous 指针；如果添加元素前双端队列为空，还需要进行相应处理：

 def addrear(self, data):
　　 node = Node(data)
　　 # 如果添加元素前双端队列为空，则添加结点时，需要将front指针也指向该结点
　　 if self.front is None:
　　 self.rear = node
　　 self.front = node else:
　　 node.previous = self.rear
　　 self.rear.next = node
　　 self.rear = node
　　 self.num += 1
　　 def addfront(self, data):
　　 node = Node(data)
　　 # 如果添加元素前双端队列为空，则添加结点时，需要将rear指针也指向该结点
　　 if self.rear is None:
　　 self.front = node
　　 self.rear = node else:
　　 node.next = self.front
　　 self.front.previous = node
　　 self.front = node
　　 self.num += 1

2.2.6 删除元素

若双端队列不空，可以从删除队头或队尾元素并返回，删除操作需要更新队头指针 front 以及尾指针 rear，同时也要修改结点的 next 和 previous 指针，若出队元素尾队中最后一个结点，还需要进行相应处理：

 def removefront(self):
　　 if self.isempty():
　　 raise IndexError("Empty Queue Exception")
　　 result = self.front.data
　　 self.front = self.front.next
　　 self.num -= 1
　　 if self.isempty():
　　 self.rear = self.front else:
　　 # 若删除操作完成后，双端队列不为空，将 front 指针的前驱指针指向 None
　　 self.front.previous = None
　　 return result 
　　 def removerear(self):
　　 if self.isempty():
　　 raise IndexError("Empty Queue Exception")
　　 result = self.rear.data
　　 self.rear = self.rear.previous
　　 self.num -= 1
　　 if self.isempty():
　　 self.front = self.rear else:
　　 # 若删除操作完成后，双端队列不为空，将 rear 指针的后继指针指向 None
　　 self.rear.next = None
　　 return result

2.3 双端队列的不同实现对比

双端队列的不同实现对比与栈的不同实现类似，可以参考《栈及其操作实现》。

3. 双端队列应用

接下来，我们首先测试上述实现的双端队列，以验证操作的有效性，然后利用实现的基本操作来解决实际算法问题。

3.1 顺序双端队列的应用

首先初始化一个顺序双端队列 deque，然后测试相关操作：

# 初始化一个最大长度为5的双端队列dq = Deque(5)print('双端队列空?', dq.isempty())for i in range(3):
　　 print('队头添加元素：', 2*i)
　　 dq.addfront(2*i)
　　 print('队尾添加元素：', 2*i+1)
　　 dq.addrear(2*i+1)print('双端队列长度为：', dq.size())for i in range(3):
　　 print('队尾删除元素：', dq.removerear())
　　 print('队头删除元素：', dq.removefront())print('双端队列长度为：', dq.size())

测试程序输出结果如下：

双端队列空? True队头添加元素： 0队尾添加元素： 1队头添加元素： 2队尾添加元素： 3队头添加元素： 4队尾添加元素： 5双端队列长度为： 6队尾删除元素： 5队头删除元素： 4队尾删除元素： 3队头删除元素： 2队尾删除元素： 1队头删除元素： 0双端队列长度为： 0

3.2 链双端队列的应用

首先初始化一个链双端队列 queue，然后测试相关操作：

# 初始化新队列dq = Deque()print('双端队列空?', dq.isempty())for i in range(3):
　　 print('队头添加元素：', i)
　　 dq.addfront(2*i)
　　 print('队尾添加元素：', i+3)
　　 dq.addrear(2*i+1)print('双端队列长度为：', dq.size())for i in range(3):
　　 print('队尾删除元素：', dq.removerear())
　　 print('队头删除元素：', dq.removefront())print('双端队列长度为：', dq.size())

测试程序输出结果如下：

双端队列空? True队头添加元素： 0队尾添加元素： 3队头添加元素： 1队尾添加元素： 4队头添加元素： 2队尾添加元素： 5双端队列长度为： 6队尾删除元素： 5队头删除元素： 4队尾删除元素： 3队头删除元素： 2队尾删除元素： 1队头删除元素： 0双端队列长度为： 0

3.3 利用双端队列基本操作实现复杂算法

[1] 给定一字符串 string (如：abamaba)，检查其是否为回文。

　　使用双端队列可以快速检查一字符串是否为回文序列，只需要将字符串中字符依次入队，然后从双端队列两端依次弹出元素，对比它们是否相等：

def ispalindrome(string):
　　 deque = Deque()
　　 for ch in string:
　　 deque.addfront(ch)
　　 flag = True
　　 while deque.size() > 1 and flag:
　　 ch1 = deque.removefront()
　　 ch2 = deque.removerear()
　　 if ch1 != ch2:
　　 flag = False
　　 return flag

验证算法有效性：

print('abcba是否为回文序列：', ispalindrome('abcba'))print('charaahc是否为回文序列：', ispalindrome('charaahc'))

结果输出如下：

abcba是否为回文序列： True

　　charaahc是否为回文序列： False

推荐学习：python教程以上就是Python数据结构与算法学习之双端队列的详细内容，更多请关注盛行IT软件开发工作室其它相关文章！

郑重声明：本文由网友发布，不代表盛行IT的观点，版权归原作者所有，仅为传播更多信息之目的，如有侵权请联系，我们将第一时间修改或删除，多谢。