谁能给我一个需要Deque数据结构的情况的例子吗?
注意 -请不要解释 adeque
是什么?
Deque 是一个双端队列,允许从两端插入和删除。
在实际场景中,我们可以将它附加到购票线上,它的表现就像一个队列,但有时会发生一些人已经购买了票,然后他们突然回来在队列前面询问一些事情。在这种情况下,因为他们已经购买了机票,所以他们有权前来询问任何进一步的问题。所以在这种情况下,我们需要一个数据结构,根据需要从前面添加数据。并且在同样的场景中,用户也可以从后面离开队列。
所以它完全遵循 Deque 的数据结构。
在对任何类型的现实世界等待线进行建模时:实体(比特、人、汽车、文字、粒子等)以一定的频率到达排队的末端,并在排队的开头以不同的频率提供服务。在等待某些实体可能决定离开线路时......等等。关键是您需要“快速访问”来在线路的两端插入/删除,因此是双端队列。
可以使用双端队列的一个示例是 A-Steal 作业调度算法。该算法实现了多个处理器的任务调度。为每个处理器维护一个带有要执行的线程的单独双端队列。为了执行下一个线程,处理器从双端队列中获取第一个元素(使用“删除第一个元素”双端队列操作)。如果当前线程分叉,则将其放回双端队列的前面(“在前面插入元素”)并执行一个新线程。当一个处理器完成其自己线程的执行(即它的双端队列为空)时,它可以从另一个处理器“窃取”一个线程:它从另一个处理器的双端队列中获取最后一个元素(“删除最后一个元素”)并执行它。
在最近通过 C# 编写的 CLR 中, Richter 描述了 .Net 4.0 中对 ThreadPool 的改进。绝对值得一读,尤其是关于偷工减料的。Richter 描述的算法看起来与 Wikipedia 中的示例非常相似,所以我怀疑那里也使用了 Deque。
http://en.wikipedia.org/wiki/Deque说有使用双端队列的作业调度算法。德国维基百科页面 (http://de.wikipedia.org/wiki/Deque) 提到了模式匹配算法和非确定性有限状态机的实现作为双端队列的用例。
可以使用两种数据结构之一来实现“队列”
通常,双端队列对优先级队列很有用,使用双端队列扫描队列比链表快得多。
双端队列可以模拟火车站,汽车可以在线路的左侧或右侧进出,但只有末端的汽车可以进出。这是因为里面的车不能撞到外面的车离开,所以只能等待。
链接迭代器时有一个实际使用示例。我用它来实现一个可扩展的迭代器:
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);
}
}
}