有人能给我举一个需要使用双端队列数据结构的情况的例子吗?
注意 - 请不要解释什么是deque
。
有人能给我举一个需要使用双端队列数据结构的情况的例子吗?
注意 - 请不要解释什么是deque
。
Deque是双端队列,允许从两端插入和删除。
在实际场景中,我们可以将其附加到购票队列上,它的表现类似于一个队列,但有时候会发生这样的情况:有人已经购买了票,突然回来询问队列前面的事情。在这种情况下,因为他们已经购买了票,所以他们有权利来询问任何进一步的问题。因此,在这种情况下,我们需要一种数据结构,根据要求从前面添加数据。同样,在相同的场景中,用户也可以从后面离开队列。
因此,它完全遵循Deque的数据结构。
当建模任何类型的现实等待线时:实体(比特、人、汽车、单词、粒子等)以一定频率到达队列末尾,并在队列开头以不同频率进行服务。在等待期间,某些实体可能决定离开队列......等等。重要的是,您需要“快速访问”来在队列两端进行插入/删除,因此需要一个双向队列。
一个deque可以使用的例子是A-Steal作业调度算法。该算法实现了多处理器的任务调度。为每个处理器维护一个单独的线程双端队列。要执行下一个线程,处理器从队列中获取第一个元素(使用“删除第一个元素”的deque操作)。如果当前线程分叉,则将其放回队列的前面(“在前面插入元素”),并且执行新线程。当其中一个处理器完成其自己的线程的执行时(即其deque为空),它可以从另一个处理器“窃取”一个线程:它获取另一个处理器的deque的最后一个元素(“删除最后一个元素”)并执行它。
在最近的CLR via C#书籍中,Richter描述了在.Net 4.0中对ThreadPool进行的改进。值得一读,尤其是关于工作窃取的部分。Richter描述的算法看起来与维基百科的例子非常相似,因此我怀疑Dequeue也在那里被使用。
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);
}
}
}