Can anyone give me an example of situation where a Deque data structure is needed?
Please don't explain what a deque is...
Can anyone give me an example of situation where a Deque data structure is needed?
Please don't explain what a deque is...
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.
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.
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.
A "queue" can be implemented using one of two data structures
Typically, a deque is useful for priority queuing, scanning the queue is significantly faster with a deque than linked list.
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.