As you probably know, a Queue is a data structure that behaves much like a queue of people waiting at the bank: items are added to one end, and removed from the other. A Double Ended Queue, or Deque for short, is an extension of a Queue that allows items to be added to either end, and removed from either end.

 

Thus, the important operations on the Deque class are AddToFront, RemoveFromFront, GetAtFront, AddToBack, RemoveFromBack, GetAtBack. These operations add or remove an item from the front or back of the Deque, or examine that item without removing it. All of these operations on the Deque class are very efficient, and operate in O(1) time.

 

In addition to these traditional Deque operations, the Deque class allows all the flexibility of a List: you can access any item in the Deque by index (the front is always index zero), and you can also insert and remove items anywhere in the Deque. However, just like a List, inserting or removing items in the middle of the Deque may not be very efficient.

 

The Deque class actually has a quite simple implementation. The items in the Deque are stored in a single array, called buffer, which is grown as necessary. There are two integer member variables, called start and end, which hold the indexes in the array of the first and last items in the Deque. Thus, the first items in the Deque (index zero), is always stored at buffer[start].

 

The Deque may “wrap around” the end of buffer, such if the buffer has 10 items, for example, start might be 8, and end might be 2, so that the first item in the Deque is at buffer[8], the next at buffer[9], and the next at buffer[0].

 

With this framework, adding items at the front or back is equally easy and efficient: to add at the front, decrement start (with wrap-around) and store the item. To add at the back, increment end (with wrap-around) and store the item. If the buffer becomes full, it is doubled in size.

 

Accessing items by index is also simple and quite efficient; ignoring bounds checks, the item at index i is simply accessed by buffer[(start + i) % buffer.Length].

 

Inserting an item in the middle of the Deque is a bit more interesting. To be as efficient as it can, the Deque class checks to see if the point of insertion is closer to the front or the back. If it is closer to the front, it decrements start and moves all the items before the insertion point back in the buffer. If it is closer to the back, it increments end and moves all of the items after the insertion point forward in the buffer. Thus, the performance is proportional to the distance to the nearest end. Somewhat surprisingly, this algorithm was fairly tricky to implement efficiently: I wanted to use Array.Copy to move large chunks of items as fast as possible. Combined with the possibility wrap-around, the code has a lot of sub-cases and subtle boundary conditions.

 

The performance characteristics of Deque are fairly similar to that of List. The amount of memory used is just about the same, and most operations, like indexing or adding to the end, are slightly slower than their corresponding List operations, because of the overhead of dealing with the wrap-around. Deque is much faster than list, however, when adding and removing items at the front, or very close to the front. Thus, if you find yourself often adding/removing items at the front of a list as well as the back, then using Deque may be a much better option than List.

 

You can browse the documentation for Deque here.