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

Question

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

Please don't explain what a deque is...

Answer 1

technically, a queue that you can only add or remove from 1 end is a stack. a queue that you can add to one end, and remove from the other is a queue.

That's confusing, but to say it simply: a deque fulfils the needs of both stack and queue structures in 1 easy-to-remember structure.

Answer 2

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.

Answer 3

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.

Answer 4

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.

Answer 5

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.