Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

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
2  
    
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
1  
@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
add comment

4 Answers

up vote 8 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: en.wikipedia.org/wiki/Double-ended_queue 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
add comment

deque is like an array, but better. It offers random access, good cache coherence, but none of the irritating resize crap, and superior complexity/iterator invalidation.

share|improve this answer
    
A deque offers random access? Only if you've already searched for your access point, which is a linear operation. Typically, a deque is O(N) for arbitrary indexing (away from the ends, which are special cases) whereas an array really is constant. –  Donal Fellows May 8 '12 at 14:18
2  
OP is talking about the abstract data structure, not the C++ implementation with irritatingly-close name but different interface. –  Konrad Rudolph May 8 '12 at 14:36
add comment

At least in the C++ Standard Template Library, deques provide random access iterators, so you get the flexibility of a vector with constant time insertions at both the beginning and end of it. Insertions in the middle take linear time, unfortunately.

share|improve this answer
add comment

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. –  ConsideredHarmful May 8 '12 at 15:26
1  
@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
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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