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?

  • 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, 2012 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, 2012 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, 2012 at 14:51
  • I find this answer more practical by shiv.mymail - stackoverflow.com/questions/3880254/… Aug 16, 2017 at 6:32

2 Answers 2


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.

  • I don’t think deques are used / needed here. A simple (maybe size-limited) stack is enough. May 8, 2012 at 14:36
  • 2
    @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, 2012 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. May 8, 2012 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, 2012 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, 2012 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.