双端队列

双端队列，简称deques，是队列的广义形式队列．的元素可以添加或删除，这一点与队列完全类似头或的尾巴．

在这张图中，双端队列中目前有3个项目——两边的额外空间只是为了显示新项目可以放在哪里。在双端队列中，可以向两边添加或删除项目。因此，在4前面加一个4会导致4出现在6的左边。头在4上。另一方面，增加7会使7出现在2的右边。那么尾巴就在7上。

有头有尾的双桅帆船

双端队列可以被认为是在餐厅等待的一排人。就像队列在美国，排在队伍前面的人可以得到帮助，他们可以在队伍后面加入队伍。然而，与队列不同的是，还可能发生两件事。在这个队伍中，排在队伍末尾的人如果不耐烦了，可以提前离开，点完菜后还可以再来点调味品。所以，增加和减少人员可能发生在这条线的两端。

最小所需功能

双端队列有六种基本操作。

函数名* 提供的功能

追加(我) 添加元素我排在队伍的尾部

预先考虑(我) 添加元素我排在队伍的最前面

delete_last () 删除位于队列尾部的元素

delete_first () 移除队列开头的元素

examine_last () 返回位于队列尾部的元素

examine_first () 返回位于队列头部的元素

*不需要确切的名字。事实上，某些功能可以由特定的语言直接通过特殊的语法提供。

通常，这些操作是用数据结构实现的链表．链表使得线性更新非常容易抽象数据类型．无论使用的数据结构是什么，对deque的头和尾的引用都必须保持，这样才能执行每个操作。

双端队列的问题

双端队列的问题

想象一下，在餐馆里有一排人正在接受帮助。的头这条线在前面。的尾巴队伍的最后面。

什么双端队列操作可以描述一个人因为不耐烦而离开队伍的末端?什么操作描述了某人回到前线取调味品?

双端队列与常规队列有什么不同?

A1。的delete_last函数。的预谋函数。

A2。使用双端队列，您可以同时从队列的前端和尾部删除和添加项。在队列中，您只能将数据添加到后面，并将其从前面删除。

使用列表的Python实现示例

数据结构列表可以实现双端队列，尽管效率不高:

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23

类双端队列：def__init__（自我):自我．队列＝［］def附加（自我，我):自我．队列．附加（我）def预谋（自我，我):自我．队列．插入（0，我）defdelete_last（自我):如果len（自我．qlist）= =0：返回"Deque是空的"自我．qlist．流行（-1）defdelete_first（自我):如果len（自我．qlist）= =0：返回"Deque是空的"自我．qlist．流行（0）defexamine_last（自我):如果len（自我．qlist）= =0：返回"Deque是空的"返回自我．qlist［-1］defexamine_first（自我):如果len（自我．qlist）= =0：返回"Deque是空的"返回自我．qlist［0］

让我们看看这个实现的实际情况。

12 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

>>>双＝双端队列（）>>>双．附加（3.）>>>双．队列［3.］>>>双．附加（2）>>>双．队列［3.，2］>>>双．预谋（1）>>>双．队列［1，3.，2］>>>双．delete_last（）>>>双．队列［1，3.］>>>双．delete_first（）>>>双．队列［3.］>>>双．examine_first（）3.

时间复杂度

deques的时间复杂度取决于使用的数据结构的类型和构建的具体实现。下面是对加倍的复杂度分析链表而且动态数组：

操作	双链表	动态数组
附加	$O (1)$	$O (1)$
预谋	$O (1)$	$O (n)$
delete_last	$O (1)$	$O (1)$
delete_first	$O (1)$	$O (n)$
examine_last	$O (1)$	$O (1)$
examine_first	$O (1)$	$O (1)$

为数组，你仍然可以把出队列想象成一条线。如果你去掉了排在第一个的人，那么你就必须把所有人都往前推，所以运行时间是O(n)然而，如果你把排在队伍最后的人赶走——也许他们只是离开了队伍——那么你就不需要挪动其他人了。所以运行时间是O(1)同样的逻辑也适用于将人添加到这条线上。

在链表实现时，一切都是常数时间。这是因为，对于任何操作，您所要做的就是修改指向有问题的元素和邻居的指针。链表实现通常有指向尾巴deque的。这使得链表实现非常快。

应用程序

deque在许多不同的场景中都很有用，因为它们展示了a和b的原则堆栈而且一个队列．分布式计算和调度就是一个例子。如果有许多计算机试图完成各种工作，那么每台计算机首先从自己列表中的第一个工作开始。如果该作业完成，它将被丢弃，但如果它被中断，它将被推回到列表的前面。然后，如果有一台计算机完成了他们的列表，他们就可以使用最后的元素从另一台计算机的列表中删除。

队列的另一个重要应用是在网络中。像队列，网络数据以先到先服务的方式在dequeue中处理。但是，如果某个数据包已经等待了太长时间，那么它可以选择离开并尝试其他地方。这样，从两端删除的deque功能非常有用。

有关……

内容

双端队列的问题