I'm fairly familiar with where to use Stacks, Queues, and Trees in software applications but I've never used a Deque (Double Ended Queue) before. Where would I typically encounter them in the wild? Would it be in the same places as a Queue but with extra gribbilies?
One way a deque is used is to "age" items. It is typically used as an undo or history feature. A new action is inserted into the deque. The oldest items are at the front. A limit on the size of the deque forces the items at the front to be removed at some point as new items are inserted (aging the oldest items). It then provides a fast way to access both ends of the structure because you instantly know the oldest and the newest items to either remove the front and commit the oldest action in O(1) or undo in O(1) time.
Excellent question. I can’t remember our CS 102 course mentioning a single application for the double-ended queue.
To this day, the only application I know is the work-stealing scheduler mentioned in the Wikipedia article.
It works essentially as follows:
In a normal, single-threaded procedural model, every function call pushes an activation record on a so-called call stack. An activation record contains the local variables and parameters of that call. Once the call to the method is completed (“returns”), the last activation record is popped from the call stack.
This is particularly important because that’s how recursion is implemented: the structure of the recursion is represented in the current state of the call stack.
When parallelising a recursive algorithm, we can exploit this property by replacing the call stack with a call queue. Every thread in the computation gets its own call queue and pushes and pops activation records like in a sequential execution.
But once a thread has finished its work (= its call queue is empty), it steals work from another thread by removing an activation record from that thread’s call queue by removing from the “wrong” end.
Basically, the call queue acts as two call stacks which now serve two threads.