Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question
seems there's some confusion in this thread. On the internet "deque" is a double-ended queue (wikipedia mentions linked list implementation). However in C++ STL, "std::deque" is an array-like structure implemented as array of data blocks. It offers random access, similar to std::vector, but its resize capability is closer to that of std::list because as data is added, it adds blocks and does not reallocate and move existing data. – DXM May 8 '12 at 14:28
@DXM: a STL deque is still a double-ended queue though and provides faster operations at the ends (depending on implementation). That it offers access to the middle as well doesn't make its primary operation less queue-like. – gbjbaanb May 8 '12 at 14:30
@gbjbaanb: All I'm saying is if you look at public interfaces of 3 classes: std::vector, std::list (or std::queue) and std::deque, you'll see that std::vector and std::deque have identical public interface and identical capability (std::deque is slightly more flexible at expense of larger memory footprint). std::list and std::queue on the other hand behave more like their CS counter-parts, linked-list and queue respectively. CS deque != std::deque – DXM May 8 '12 at 14:51
up vote 14 down vote accepted

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.

share|improve this answer
I don’t think deques are used / needed here. A simple (maybe size-limited) stack is enough. – Konrad Rudolph May 8 '12 at 14:36
@Konrad How do you age items in a simple stack? (i.e. how do you remove commands that are "too old"?) – Andres F. May 8 '12 at 14:39
@AndresF. Is age independent of the stack size? If so, then I’ve never heard of this data structure. Otherwise it’s simply a stack with fixed size which can be implemented in terms of a deque, or simply by postulating a simpler data structure called the fixed-sized stack. – Konrad Rudolph May 8 '12 at 14:46
So deques are useful after all ;) Never heard of a fixed-size stack (in the sense you mean, of removing the oldest item). It makes sense, but it's not what is usually meant by "stack", and whether it is actually simpler remains to be seen :) – Andres F. May 8 '12 at 14:51
This was posted in the comments of the original question: It's just a double ended queue. I have used it in practice in the way I have outlined above (which is why I posted it). In a true stack, the only operations you should have are push, pop, top and peek (we could argue others, but this is generally it). You should have no knowledge of what is on the bottom of the stack or even how to access the bottom. In a "fixed sized stack" you would just generate stack overflow instead of aging old items when you filled it. – jmq May 8 '12 at 16:00

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.

share|improve this answer
Do you have a source for this? Sounds interesting. – dsch May 8 '12 at 15:26
@Richard1987 The Wikipedia article cites the original paper. Several implementations exist, for instance in the GNU c++stdlib parallel extension work-stealing implementation (but the code is horrible to read) or a parallel implementation of generalised divide & conquer by yours truly (but the latter uses a very idiomatic programming style particular to the library and thus hard to read) – Konrad Rudolph May 8 '12 at 15:35

protected by gnat Aug 26 '15 at 5:43

Thank you for your interest in this question. Because it has attracted low-quality or spam answers that had to be removed, posting an answer now requires 10 reputation on this site.

Would you like to answer one of these unanswered questions instead?

Not the answer you're looking for? Browse other questions tagged or ask your own question.