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 per cent 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 show 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>.