为什么从队列前面插入(deque)



人们有什么理由想在队列的前面插入一些东西吗?我正在写一份关于双端队列的报告,这让我很烦恼。

我假设,当需要时,可能会在前面插入更重要的东西,但优先级队列会更相关。

可以使用deque的一个例子是Steal作业调度算法。该算法实现了多个处理器的任务调度。每个处理器都有一个单独的deque,其中包含要执行的线程。为了执行下一个线程,处理器从deque中获取第一个元素(使用"remove-first element"deque操作)。如果当前线程分叉,则将其放回deque的前面("在前面插入元素"),并执行一个新线程。当其中一个处理器完成自己线程的执行(即其deque为空)时,它可以从另一个处理器"窃取"线程:它从另一处理器的deque中获取最后一个元素("删除最后一个元件")并执行它。窃取作业调度算法由英特尔的线程构建块(TBB)库用于并行编程。

请注意,优先级队列与deque本质上不同,PQ中的元素根据其优先级进行处理,而在deque中,您只能在队列的前面或后面移除和插入。我很快就能想到deque的一个可能应用程序是一个"撤消"功能,使您能够恢复到以前的状态。

最新更新