为什么我们在现实世界中需要Deque数据结构？

Question

任何人都可以给我一个需要Deque数据结构的情况的例子吗？

注意 -请不要解释它deque是什么？

Answer 1

Deque是一个双端队列,允许从两端插入和删除.

在实际场景中,我们可以将它附加到票证购买行,它像队列一样执行但是有些时候发生了某些机构已经购买了机票并突然他们回来在队列前面询问一些事情.在这种情况下,因为他们已经购买了票证,所以他们有权来请求任何进一步的查询.所以在这种情况下我们需要一个数据结构,根据需要我们从前面添加数据.在同一场景中,用户也可以从后面离开队列.

因此它完全遵循Deque的数据结构.

Answer 2

在对任何类型的真实等待线进行建模时:实体(位,人,汽车,单词,粒子等)以一定频率到达线的末端,并在线的开头以不同的频率进行服务.在等待一些实体可能决定离开线路......等等.重点是你需要"快速访问"在线路的两端插入/删除,因此是一个双端队列.

Answer 3

1. deque的一个很好的应用是存储Web浏览器的历史记录.最近访问过的URL被添加到双端队列的前面,并且在前面的一些指定数量的插入之后删除了双端队列后面的URL.
2. deque的另一个常见应用是存储软件应用程序的撤消操作列表.
3. 可以使用双端队列的一个例子是A-Steal作业调度算法.[5] 该算法实现了多个处理器的任务调度.为每个处理器维护一个单独的deque,其中包含要执行的线程.为了执行下一个线程,处理器从deque中获取第一个元素(使用"remove first element"deque操作).如果当前线程分叉,则将其放回到双端队列的前面("在前面插入元素")并执行新线程.当其中一个处理器完成自己的线程执行(即它的deque为空)时,它可以从另一个处理器"窃取"一个线程:它从另一个处理器的deque中获取最后一个元素("删除最后一个元素")并执行它. - 礼貌维基百科

Answer 4

维基百科中的示例

可以使用双端队列的一个示例是A-Steal作业调度算法.该算法实现了多个处理器的任务调度.为每个处理器维护一个单独的deque,其中包含要执行的线程.为了执行下一个线程,处理器从deque中获取第一个元素(使用"remove first element"deque操作).如果当前线程分叉,则将其放回到双端队列的前面("在前面插入元素")并执行新线程.当其中一个处理器完成自己的线程执行(即它的deque为空)时,它可以从另一个处理器"窃取"一个线程:它从另一个处理器的deque中获取最后一个元素("删除最后一个元素")并执行它.

在最近通过C#的CLR中, Richter描述了.Net 4.0中对ThreadPool的改进.绝对值得一读,尤其是偷工作.Richter描述的算法看起来与维基百科的例子非常相似,所以我怀疑Deque也在那里使用.