Introduction
The .NET framework contains a large number of collection classes. However, there are a few omissions including the double-ended queue (or deque) which is present in the standard libraries of other languages such as C++ and Java and is particularly useful in job scheduling applications.
In the case of an ordinary queue, items can only be added at the back and retrieved from the front of the queue. However, a deque allows items to be added at and retrieved from either end of the queue.
I thought it would therefore be useful to implement a Deque<T> class in C# to supplement the Queue<T> class which is already present in the .NET Framework.
Implementation
Deques are often implemented using doubly linked lists to which they are closely related. In fact another name for a deque is a 'head-tail linked list'.
The main difference between the two is that you can insert elements into or remove elements from the middle of the linked list as well as at the end points.
However, because of the way that heap memory is allocated, doubly linked lists (namely LinkedList<T>) are not very efficient in .NET and I have therefore used two List<T>'s , placed back to back, instead.
![vulpes.gif]()
I would have preferred to use back to back queues instead but this wasn't feasible as the items in the queues would need to be accessed by index in the circumstances described later in this section.
One List<T> represents the front and the other represents the back of the deque. Provided that there is always at least one element in both lists, then this approach is about three times faster than using a doubly linked list.
The difficulty, of course, is what to do if you need to remove an element from one end of the deque and there are no elements left in the corresponding list.
What I decided to do is to return the first element of the other list and mark it for deletion but not actually delete it. Deletion is a relatively expensive operation because all the other elements of the list need to be moved down in memory. Also simply marking it for deletion is better than it sounds because the capacity of the list (i.e. the maximum number of elements it can accommodate) is never reduced automatically when deletions take place. So having deleted items still sitting in memory does no immediate harm.
However, it does do some longer-term harm because it reduces the time needed before the capacity of the list next needs to be increased (a very expensive operation) and, in the case of reference type elements, increases the time before they can be garbage collected if there are no other references to them.
Consequently, whenever a new item is added to the deque, if the deque would otherwise need resizing, any deleted items are then removed completely. This postpones the resizing operation and may even prevent it altogether. If there is more than one deleted item, it also means that the other items only need to be moved down in memory once rather than each time a deletion occurs.
Resizing doesn't occur very often. A generic list has a default capacity of 4 and this is doubled (to 8, 16, 32 etc.) as new items are added.
If no further items are likely to be added to the deque, then you can call the TrimExcess method so that the capacity then matches the number of items. This method also removes deleted items before trimming the remainder. Notice though that since this method calls the TrimExcess method of the underlying List<T>'s, trimming only takes place if the List<T> is less than 90 per cent of capacity. In other words at least 10 percent of capacity must be unused.
The Deque<T> class
The Deque<T> class contains the same members, and implements the same interfaces, as the Queue<T> class except that there are no Enqueue and Dequeue methods. I have also added some 'convenience' members which Queue<T> lacks.
I felt that EnqueueFirst, EnqueueLast, DequeueFirst and DequeueLast would be too long-winded for names of commonly used methods and so I have used AddFirst, AddLast, PopFirst and PopLast instead. There are also PeekFirst and PeekLast methods and 'Try' versions of the last four to avoid throwing an exception if the Deque is empty.
The other 'convenience' members are the Capacity and IsEmpty properties and the AddRangeFirst and AddRangeLast methods which add multiple items to the Deque from an enumerable collection.
There is also a Reversed property which enables you to iterate the Deque in reverse order and a Reverse method which permanently reverses the order of the items in the Deque.
This table lists Deque<T>'s main constructors with a brief description of what they do:
| Constructor Signature |
Description |
| Deque() |
creates a new empty Deque |
| Deque(capacity) |
creates a new Deque with the specified initial capacity |
| Deque(backCollection) |
creates a new Deque by adding items from backCollection at the back of the Deque |
| Deque(backCollection, frontCollection) |
creates a new Deque by adding items from backCollection at the back and items from frontCollection at the front of the Deque |
This table lists its properties:
| Property Name |
Description |
| Capacity |
gets the total capacity of the Deque |
| Count |
gets the total number of items in the Deque |
| IsEmpty |
indicates whether the Deque is empty or not |
| Reversed |
enables the Deque's items to be iterated in reverse order (from last to first) |
And, finally, this table lists its main methods:
| Method Name and Signature |
Description |
| AddFirst(item) |
adds this item at the front of the Deque |
| AddLast(item) |
adds this item at the back of the Deque |
| AddRangeFirst(range) |
adds this range of items at the front of the Deque |
| AddRangeLast(range) |
adds this range of items at the back of the Deque |
| Clear() |
clears the Deque of all items |
| Contains(item) |
indicates if this item is within the Deque |
| CopyTo(array, index) |
copies the items in the Deque to an existing array starting at the specified index |
| GetEnumerator() |
gets an emunerator to iterate through the Deque's items from first to last |
| PeekFirst() |
returns the first item in the Deque without removing it |
| PeekLast() |
returns the last item in the Deque without removing it |
| PopFirst() |
returns and removes the first item in the Deque |
| PopLast() |
returns and removes the last item in the Deque |
| Reverse() |
permanently reverses the items in the Deque |
| ToArray() |
converts the items in the Deque to a new array |
| TrimExcess() |
reduces the capacity to match the number of items in the Deque, provided the underlying Lists are at less than 90 per cent of capacity |
| TryPeekFirst(out item) |
tries to get the first item in the Deque without removing it |
| TryPeekLast(out item) |
tries to get the last item in the Deque without removing it |
| TryPopFirst(out item) |
tries to get and remove the first item in the Deque |
| TryPopLast(out item) |
tries to get and remove the last item in the Deque |
Example of usage
The code for the Deque class can be downloaded from the link accompanying this article as it is too long to include in the body of the article itself. This class can be used in .NET 2.0 or later.
The following console application shows how to use some of its principal members:
using System;
using System.Collections;
using System.Collections.Generic;
using System.Runtime.InteropServices;
class DequeTest
{
static void Main()
{
int[] arrFront = { 5, 4, 3, 2, 1 };
int[] arrBack = { 6, 7, 8, 9, 10 };
// create new Deque using these arrays
Deque<int> d = new Deque<int>(arrBack, arrFront);
// iterate from first to last
Console.Write("The Deque contains : ");
foreach (int i in d) Console.Write("{0} ", i); // 1 to 10
Console.WriteLine();
// iterate from last to first
Console.Write("Or in reverse order : ");
foreach (int i in d.Reversed) Console.Write("{0} ", i); // 10 to 1
Console.WriteLine();
// permanently reverse the order of the items
d.Reverse();
// iterate from first to last again
Console.Write("After permanent reversal : ");
foreach (int i in d) Console.Write("{0} ", i); // 10 to 1
Console.WriteLine();
// add items at front
Console.WriteLine("Added 11 and 12 at the front");
d.AddRangeFirst(new int[] { 11, 12 });
// add item at back
Console.WriteLine("Added 0 at the back");
d.AddLast(0);
Console.WriteLine("The first item is : {0}", d.PeekFirst()); // 12
int num;
if (d.TryPeekLast(out num))
{
Console.WriteLine("The last item is : {0}", num); // 0
}
// pop last item
Console.WriteLine("Popped last item");
num = d.PopLast();
// pop first item
Console.WriteLine("Popped first item");
d.TryPopFirst(out num);
if (d.Contains(11))
{
// iterate again
Console.Write("The Deque now contains : ");
foreach (int i in d) Console.Write("{0} ", i); // 11 to 1
Console.WriteLine();
}
// peek at last item
Console.WriteLine("The last item is : {0}", d.PeekLast()); // 1
// count items
Console.WriteLine("The number of items is : {0}", d.Count); // 11
// convert to an array
int[] ia = d.ToArray();
// reload to a new Deque adding all items at front so they'll now be reversed
d = new Deque<int>(null, ia);
Console.Write("The new Deque contains : ");
foreach (int i in d) Console.Write("{0} ", i); // 1 to 11
Console.WriteLine("\nThe capacity is : {0}", d.Capacity);
d.TrimExcess();
Console.WriteLine("After trimming the capacity is now : {0}", d.Capacity);
// copy to an existing array
ia = new int[d.Count];
d.CopyTo(ia, 0);
// clear the Deque (No pun intended!)
d.Clear();
Console.WriteLine("After clearing the Deque is now empty : {0}", d.IsEmpty);
Console.WriteLine("The third element used to be : {0}", ia[2]);
Console.ReadKey();
}
}
Example output
A screenshot of the output is shown below:
![vulpes-2.gif]()
Conclusion
I hope you will find the Deque<T> class to be a useful addition to the other collection classes in the .NET Framework.
It is not intended as a replacement for the Queue<T> class and should only be used in situations where additions and removals at both ends of the queue are required. The performance of the two classes should be much the same.
Although there is also a non-generic Queue class in the .NET Framework, I didn't feel it would be worthwhile producing a non-generic Deque as this would be essentially the same as a Deque<object>.