双端队列
双端队列,简称deques,是一种广义形式的队列.队列与队列完全相似,只是元素可以添加到队列中或从队列中删除头或的尾巴.
在这张图片中,双端队列中目前有3件物品——两边的额外空间只是用来显示新物品可以放在哪里。在双端队列中,项目可以添加到两侧,也可以从两侧删除。所以,在4前面加一个4会导致4出现在6的左边。头部就会在4上。另一方面,加上7会使7出现在2的右边。那么尾巴就在7上。
双端队列可以被认为是在餐馆排队等候的人。就像在队列在美国,排在队伍前面的人可以得到帮助,他们可以在队伍后面加入队伍。然而,与队列不同的是,还会发生两件事。在这条队伍中,排在队伍末尾的人如果不耐烦了,可以提前离开,人们可以在点完菜后再回来要调味品。因此,在这条线的两端都可以增加和删除人员。
最低要求功能
双端队列的问题
双端队列的问题
想象一下在餐厅排队接受帮助的人们。的头在前面。的尾巴在队伍的后面。
什么样的双端队列操作可以描述某人由于不耐烦而离开队列的末端?什么操作描述了一个人回到前线拿调味品?
双端队列与常规队列有什么不同?
A1。的delete_last
函数。的预谋
函数。A2。使用双端队列,您可以从队列的前面和后面同时删除和添加项目。在队列中,只能向后面添加数据,并从前面删除数据。
使用列表的Python实现示例
数据结构列表
在Python中能够实现双端队列,尽管效率较低:
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 |
|
让我们看看实际的实现。
12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
|
时间复杂度
deques的时间复杂度取决于使用的数据结构类型和构建的特定实现。下面是对double的复杂度分析链表而且动态数组:
操作 | 双链表 | 动态数组 |
附加 | ||
预谋 | ||
delete_last | ||
delete_first | ||
examine_last | ||
examine_first |
为数组,你仍然可以把出队列看作是一条线。如果你把第一个人赶出去,那么你必须把所有人都往前推,所以运行时间是O(n)然而,如果你把排在队伍最后的人赶走了——也许他们只是离开了队伍——那么你就不需要调动其他人了。所以运行时间是O(1)同样的逻辑也适用于增加人数。
在链表执行,所有的都是常数时间。这是因为,对于任何操作,您所要做的就是修改指向有问题的元素及其邻居的指针。链表实现通常有指向尾巴deque的。这使得链表的实现非常快。