为什么在现实世界中需要双端队列数据结构？

Question

有人能给我举一个需要使用双端队列数据结构的情况的例子吗？

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

- user366312

---

相关信息：双端队列 在维基百科上的介绍。 - Oded

加一票支持“请不要解释deque是什么”。这个人懂得使用stackoverflow。 - mackenir

在Programmers.SE上的[Where would I typically use a Deque in production software?]的副本。 - mins

Answer 1

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

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

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

- S.P Singh

---

不错，这是一个更实际的例子。 - roottraveller

非常好的解释。 - Jay

Answer 2

1. deque的一个很好的应用是存储web浏览器的历史记录。最近访问的URL被添加到deque的前面，在一些指定数量的插入操作之后，deque末尾的URL将被移除。
2. deque的另一个常见应用是存储软件应用程序的撤消操作列表。
3. deque可用于A-Steal作业调度算法[5]。该算法实现多处理器的任务调度。为每个处理器维护一个单独的线程deque。要执行下一个线程，处理器从deque中获取第一个元素（使用“删除第一个元素”deque操作）。如果当前线程分叉，它将被放回deque的前面（“在前面插入元素”），然后执行新的线程。当其中一个处理器完成自己的线程的执行（即其deque为空时），它可以从另一个处理器“窃取”一个线程：从另一个处理器的deque中获取最后一个元素（“删除最后一个元素”），然后执行它。 - 摘自维基百科

- improgrammer

---

为什么普通队列不能满足1和2的要求？ - Aadith Ramia

@Aadith，我认为你对于#1是正确的，但是#2更适合使用双端队列(deque)，因为你可以通过从deque的前面取出来来“撤销你的撤销”，而在队列中这样做是不合法的。此外，就C++而言，由于某种原因，deque允许进行迭代，而队列则不行。 - user755921

根据《Java并发实践》一书的描述：“工作窃取”比传统的生产者-消费者设计更具可扩展性，因为工作者不会争夺共享的工作队列；大多数时间它们只访问自己的双端队列，减少了争用。当一个工作者必须访问另一个工作者的队列时，它从尾部而不是头部进行，进一步减少了争用。” - BartoszMiller

Answer 3

当建模任何类型的现实等待线时：实体（比特、人、汽车、单词、粒子等）以一定频率到达队列末尾，并在队列开头以不同频率进行服务。在等待期间，某些实体可能决定离开队列......等等。重要的是，您需要“快速访问”来在队列两端进行插入/删除，因此需要一个双向队列。

- ric0liva

---

我不确定这是否现实可行。请考虑，除非在一个队伍中只有最后一个人可以离开，否则你不能使用deque来模拟现实世界中的队伍。此外，在这个假想的队伍中，如果倒数第三个人想离开，那么他身后的每个人都需要分享他的观点，因为他们也需要离开。 - nsfyn55

我正在处理这个问题：我有一个使用OpenGL以60Hz显示图像的程序。另一个程序决定在图像中绘制什么。不幸的是，这个另一个程序偶尔会因为垃圾回收而停止。我在显示程序中使用deque作为未来图像的缓存。这样，即使垃圾回收器偶尔停止生产者，我也可以确保始终有可用的图像。 - whoplisp

Answer 4

维基百科的例子

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

在最近的CLR via C#书籍中，Richter描述了在.Net 4.0中对ThreadPool进行的改进。值得一读，尤其是关于工作窃取的部分。Richter描述的算法看起来与维基百科的例子非常相似，因此我怀疑Dequeue也在那里被使用。

- Konstantin Spirin

Answer 5

http://en.wikipedia.org/wiki/Deque中提到有使用双端队列的作业调度算法。德语维基百科页面（http://de.wikipedia.org/wiki/Deque）提到，模式匹配算法和实现非确定有限状态机是双端队列的应用案例。

- jens

Answer 6

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

1. 链表 - 如果您仅在两端工作，并且不关心内存分配开销（或受到内存分配方式的限制），则这是有意义的。
2. 双端队列 - 如果您需要在两端工作，还需要位置访问（或快速迭代队列中的项目的能力）并且内存分配开销很重要（但不受限制），那么双端队列提供了最佳选择（向量式分配与链表式功能相结合 - 在两端上是这样的，插入到中间更昂贵）

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

- Nim

Answer 7

在迭代器链中有一个实际的使用例子。我用它来实现一个可扩展迭代器:

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);
        }
    }
}

- Reut Sharabani

Answer 8

一个双端队列可以模拟火车站，汽车可以从线路的左侧或右侧进出，但只有两端的汽车可以移动进出。这是因为内部的汽车不能碰到外部的汽车离开，所以它们只能等待。

- thegenie