Зачем нам нужны структуры данных Deque в реальном мире?

Ответ 1

При моделировании любой линии ожидания реального мира: сущности (биты, люди, автомобили, слова, частицы и т.д.) поступают с определенной частотой до конца строки и обслуживаются с другой частотой в начале линия. Ожидая, что некоторые сущности могут решить покинуть линию.... и т.д. Дело в том, что вам нужен "быстрый доступ" для вставки/удаления на обоих концах строки, следовательно, для deque.

Ответ 2

A Deque - это двойная очередь, позволяющая вставлять и удалять с обоих концов.

В реальном сценарии мы можем привязать его к линии покупки билетов, он работает как очередь, но некоторое время. Иногда бывает, что кто-то купил билет и внезапно вернулся, чтобы спросить что-то впереди очереди. В этом случае, поскольку они уже приобрели билет, у них есть привилегия приходить и запрашивать дальнейший запрос. Таким образом, в таком сценарии нам нужна структура данных, в которой согласно требованию мы добавляем данные с фронта. И в том же сценарии пользователь также может оставить очередь сзади.

Таким образом, это полностью соответствует структуре данных Deque.

Ответ 3

• Хорошим приложением deque является сохранение истории веб-браузера. Недавно просмотренные URL-адреса добавляются в начало deque, а URL-адрес в конце deque удаляется после некоторого определенного количества вставок спереди.
• Другим распространенным приложением deque является сохранение списка операций отмены операций в программном приложении.
• Одним из примеров, где можно использовать deque, является алгоритм планирования заданий A-Steal [5]. Этот алгоритм реализует планирование задач для нескольких процессоров. Для каждого процессора поддерживается отдельный деб с потоками, которые должны выполняться. Чтобы выполнить следующий поток, процессор получает первый элемент из deque (используя операцию "удалить первый элемент" deque). Если текущие вилки резьбы, они возвращаются к передней части deque ( "элемент вставки спереди" ), и выполняется новый поток. Когда один из процессоров заканчивает выполнение собственных потоков (т.е. Его дека пуст), он может "украсть" поток из другого процессора: он получает последний элемент из deque другого процессора ( "удаляет последний элемент" ) и выполняет Это. - Courtesy Wikipedia

Ответ 4

Пример в Википедии

Одним из примеров, где можно использовать deque, является алгоритм планирования заданий A-Steal. Этот алгоритм реализует планирование задач для нескольких процессоров. Для каждого процессора поддерживается отдельный деб с потоками, которые должны выполняться. Чтобы выполнить следующий поток, процессор получает первый элемент из deque (используя операцию "удалить первый элемент" deque). Если текущие вилки резьбы, они возвращаются к передней части deque ( "элемент вставки спереди" ), и выполняется новый поток. Когда один из процессоров заканчивает выполнение собственных потоков (т.е. Его дека пуст), он может "украсть" поток из другого процессора: он получает последний элемент из deque другого процессора ( "удаляет последний элемент" ) и выполняет он.

В недавнем

Ответ 5

http://en.wikipedia.org/wiki/Deque говорит, что есть алгоритмы планирования заданий, которые используют deques. На немецкой странице wikipedia (http://de.wikipedia.org/wiki/Deque) упоминаются алгоритмы сопоставления образцов и реализация недетерминированных машин конечного состояния в качестве вариантов использования для deques.

Ответ 6

"Очередь" может быть реализована с использованием одной из двух структур данных

• связанный список - если вы работаете исключительно на концах и не заботитесь о распределении памяти (или ограничено, как распределяется память), это имеет смысл.
• deque - если вы работаете с концами, также необходим позиционный доступ (или возможность быстрого итерации элементов в очереди), и важны служебные данные распределения памяти (но не ограничены), тогда deque предлагает лучшее из них ( вектор, подобный распределению со связанным списком, как функциональность - ну, на концах, в любом случае, вставка в середине дороже).

Как правило, deque полезен для очередности очередности, сканирование очереди происходит значительно быстрее с помощью deque, чем связанного списка.

Ответ 7

Deque может моделировать железнодорожную станцию, где автомобили могут въезжать и уходить с левой или правой стороны линии, но только автомобили на концах могут двигаться и выходить. Это связано с тем, что автомобили внутри не могут попасть в автомобили снаружи, чтобы уйти, поэтому им просто нужно подождать.

Ответ 8

Существует пример практического использования при цепочке итераторов. Я использовал его для реализации расширяемого итератора:

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