59

谁能给我一个需要Deque数据结构的情况的例子吗？

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

4

8 回答 8

50

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

在实际场景中，我们可以将它附加到购票线上，它的表现就像一个队列，但有时会发生一些人已经购买了票，然后他们突然回来在队列前面询问一些事情。在这种情况下，因为他们已经购买了机票，所以他们有权前来询问任何进一步的问题。所以在这种情况下，我们需要一个数据结构，根据需要从前面添加数据。并且在同样的场景中，用户也可以从后面离开队列。

所以它完全遵循 Deque 的数据结构。

于 2013-02-23T07:28:21.390 回答
27
  1. deque 的一个很好的应用是存储 Web 浏览器的历史记录。最近访问的 URL 被添加到双端队列的前面，并且在双端队列后面的 URL 在前面插入了一些指定数量后被删除。
  2. 双端队列的另一个常见应用是存储软件应用程序的撤消操作列表。
  3. 可以使用双端队列的一个示例是 A-Steal 作业调度算法。 [5] 该算法实现了多个处理器的任务调度。为每个处理器维护一个带有要执行的线程的单独双端队列。为了执行下一个线程，处理器从双端队列中获取第一个元素（使用“删除第一个元素”双端队列操作）。如果当前线程分叉，则将其放回双端队列的前面（“在前面插入元素”）并执行一个新线程。当一个处理器完成其自己线程的执行（即它的双端队列为空）时，它可以从另一个处理器“窃取”一个线程：它从另一个处理器的双端队列中获取最后一个元素（“删除最后一个元素”）并执行它。- 礼貌维基百科
于 2014-10-31T18:47:26.833 回答
24

在对任何类型的现实世界等待线进行建模时：实体（比特、人、汽车、文字、粒子等）以一定的频率到达排队的末端​​，并在排队的开头以不同的频率提供服务。在等待某些实体可能决定离开线路时......等等。关键是您需要“快速访问”来在线路的两端插入/删除，因此是双端队列。

于 2010-10-07T10:07:31.290 回答
8

维基百科中的示例

可以使用双端队列的一个示例是 A-Steal 作业调度算法。该算法实现了多个处理器的任务调度。为每个处理器维护一个带有要执行的线程的单独双端队列。为了执行下一个线程，处理器从双端队列中获取第一个元素（使用“删除第一个元素”双端队列操作）。如果当前线程分叉，则将其放回双端队列的前面（“在前面插入元素”）并执行一个新线程。当一个处理器完成其自己线程的执行（即它的双端队列为空）时，它可以从另一个处理器“窃取”一个线程：它从另一个处理器的双端队列中获取最后一个元素（“删除最后一个元素”）并执行它。

在最近通过 C# 编写的 CLR 中， Richter 描述了 .Net 4.0 中对 ThreadPool 的改进。绝对值得一读，尤其是关于偷工减料的。Richter 描述的算法看起来与 Wikipedia 中的示例非常相似，所以我怀疑那里也使用了 Deque。

于 2010-10-07T09:46:48.610 回答
2

http://en.wikipedia.org/wiki/Deque说有使用双端队列的作业调度算法。德国维基百科页面 (http://de.wikipedia.org/wiki/Deque) 提到了模式匹配算法和非确定性有限状态机的实现作为双端队列的用例。

于 2010-10-07T09:40:09.370 回答
0

可以使用两种数据结构之一来实现“队列”

  1. 链表 - 如果您只在末端工作，并且不关心内存分配开销（或受限于如何分配内存），这是有道理的。
  2. deque - 如果你在末端工作，还需要位置访问（或者能够快速遍历队列中的项目）并且内存分配开销很重要（但不受限制），那么 deque 提供了两者的最佳选择（类似向量的分配具有类似功能的链表 - 好吧，无论如何，在中间插入更昂贵）

通常，双端队列对优先级队列很有用，使用双端队列扫描队列比链表快得多。

于 2010-10-07T10:05:18.347 回答
0

双端队列可以模拟火车站，汽车可以在线路的左侧或右侧进出，但只有末端的汽车可以进出。这是因为里面的车不能撞到外面的车离开，所以只能等待。

于 2015-03-05T19:02:02.713 回答
0

链接迭代器时有一个实际使用示例。我用它来实现一个可扩展的迭代器：

import java.util.Deque;
import java.util.Iterator;
import java.util.concurrent.ConcurrentLinkedDeque;

public class ExtendableIterator<T> implements Iterator<T> {

    public Deque<Iterator<T>> its = new ConcurrentLinkedDeque<Iterator<T>>();

    public ExtendableIterator() {

    }

    public ExtendableIterator(Iterator<T> it) {
        this();
        this.extend(it);
    }

    @Override
    public boolean hasNext() {
        // this is true since we never hold empty iterators
        return !its.isEmpty() && its.peekLast().hasNext();
    }

    @Override
    public T next() {
        T next = its.peekFirst().next();
        if (!its.peekFirst().hasNext()) {
            its.removeFirst();
        }
        return next;
    }

    public void extend(Iterator<T> it) {
        if (it.hasNext()) {
            its.addLast(it);
        }
    }
}
于 2015-11-25T16:42:46.130 回答