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

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

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

Solution 1:

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.

Solution 2:

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

Solution 3:

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.

Solution 4:

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.