Why do we need Deque data structures in the real world? [closed]

Closed开发者_StackOverflow社区. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 6 years ago.

Improve this question

Can anyone give me an example of situation where a Deque data structure is needed?

Note - Please don't explain what a deque is?

---

A Deque is a double ended queue, allowing inserting and removing from both ends.

In real scenario we can attached it to a Ticket purchasing line, It performs like a queue but some time It happens that some body has purchased the ticket and sudden they come back to ask some thing on front of queue. In this scenario because they have already purchased the ticket so they have privilege to come and ask for any further query. So in these kind of scenario we need a data structure where according to requirement we add data from front. And In same scenario user can also leave the queue from rear.

So it follows completely data structure of Deque.

---

1. A nice application of the deque is storing a web browser's history. Recently visited URLs are added to the front of the deque, and the URL at the back of the deque is removed after some specified number of insertions at the front.
2. Another common application of the deque is storing a software application's list of undo operations.
3. One example where a deque can be used is the A-Steal job scheduling algorithm.[5] This algorithm implements task scheduling for several processors. A separate deque with threads to be executed is maintained for each processor. To execute the next thread, the processor gets the first element from the deque (using the "remove first element" deque operation). If the current thread forks, it is put back to the front of the deque ("insert element at front") and a new thread is executed. When one of the processors finishes execution of its own threads (i.e. its deque is empty), it can "steal" a thread from another processor: it gets the last element from the deque of another processor ("remove last element") and executes it. - Courtesy Wikipedia

---

When modeling any kind of real-world waiting line: entities (bits, people, cars, words, particles, whatever) arrive with a certain frequency to the end of the line and are serviced at a different frequency at the beginning of the line. While waiting some entities may decide to leave the line.... etc. The point is that you need "fast access" to insert/deletes at both ends of the line, hence a deque.

---

Example in Wikipedia

One example where a deque can be used is the A-Steal job scheduling algorithm. This algorithm implements task scheduling for several processors. A separate deque with threads to be executed is maintained for each processor. To execute the next thread, the processor gets the first element from the deque (using the "remove first element" deque operation). If the current thread forks, it is put back to the front of the deque ("insert element at front") and a new thread is executed. When one of the processors finishes execution of its own threads (i.e. its deque is empty), it can "steal" a thread from another processor: it gets the last element from the deque of another processor ("remove last element") and executes it.

In the recent CLR via C# book Richter describes improvements made to ThreadPool in .Net 4.0. It is definitely worth reading, especially about work stealing. Algorithm described by Richter looks very similar to the example from Wikipedia so I suspect Deque is used there as well.

---

http://en.wikipedia.org/wiki/Deque says that there are job scheduling algorithms that use deques. The German wikipedia page (http://de.wikipedia.org/wiki/Deque) mentions pattern-matching algorithms and the implementation of non deterministic finite state machines as use cases for deques.

---

A "queue" can be implemented using one of two data structures

1. linked list - if you are exclusively working on the ends, and don't care about memory allocation overhead (or constrained as to how memory can be allocated), this makes sense.
2. deque - if you work on the ends, positional access is also required (or the ability to iterate through items in the queue quickly) and memory allocation overhead is important (but not constrained), then deque offers the best of both (vector like allocation with linked list like functionality - well, at the ends anyway, insert in the middle is more expensive)

Typically, a deque is useful for priority queuing, scanning the queue is significantly faster with a deque than linked list.

---

A deque can model a train station where cars can enter and leave on the left or right side of a line, but only the cars at the ends can move in and out. This is because the cars on the inside cannot hit the cars on the outside to leave, so they just have to wait.

---

There is a practical usage example when chaining iterators. I've used it to implement an extendable iterator:

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