It's a common story: you're working on a project and have need for a very simple class, one that you assume is part of the library you're using. You search the library and discover that the class is not there. You're then faced with a choice, you can "roll your own" class or use a third party implementation (if you can find one). It's not surprising that in most cases we choose the former. Creating your own bread and butter class that you know will come in handy in the future can be satisfying.
The class in question is a
Deque (pronounced "deck") class. The deque is a data structure that allows you to add and remove elements at both ends of a queue. I was working on my state machine toolkit and needed a
Deque collection class. I checked the
System.Collections namespace to see if it had one. Unfortunately, it didn't. I did a cursory search for a
Deque class here at CodeProject and found this article for a "Dequeue" class. I have not looked at the code, but decided anyway that it wasn't exactly what I was looking for, and admittedly, I had already made up my mind to write my own
The Deque Data Structure
The queue data structure represents functionality for adding elements to the end (or back) of the queue and removing elements from the beginning (or front) of the queue. Think of a line of people waiting to buy a ticket at a movie theater. The first person in line is the first person to buy a ticket. This approach is called "first in, first out" (FIFO).
Sometimes you need the ability to add and remove elements at both the beginning and end of the queue. The deque data structure fits the bill. It is a "double-ended-queue" in which you can add and remove elements at the front and back of the queue.
First and foremost, I wanted my
Deque class to look like a class in the
System.Collections namespace. Had I found the
Deque class when I was searching the
System.Collections namespace, this is what it would look like. I took a close look at the
Queue class and modeled my class after it. To this end, the
Deque class implements the same interfaces,
In addition to the methods and properties in those interfaces, the
Deque class also has several methods found in the
Clear - Clears the collection of all of its elements.
Contains - Determines whether or not an object is in the collection.
ToArray - Copies all of the elements in the collection to an array.
Synchronized - Provides a synchronized wrapper for the collection.
Queue class also provide a
Peek method. This method lets you peek at the element at the front of the
Queue without removing it. Following its lead, the
Deque class provides
PeekBack methods for peeking at the elements at the front and back of the
PushBack methods allow you to add elements to the front and back of the
Deque respectively, and their counterparts, the
PopBack methods, allow you to remove elements from the front and back of the
Deque class uses a doubly-linked list to implement its collection of elements. The links in the list are represented by a private
Node class. Since elements can be added to the front and back of the
Deque, it was necessary to have front and back nodes to keep track of the front and back of the
There is a custom
DequeEnumerator private class for implementing the
IEnumerator interface returned by the
GetEnumerator method for enumerating over the
Deque from front to back. I've written custom enumerators before, and it really isn't hard, it's just that you have to make sure that your implementation conforms to the
Because I needed the
Deque to be thread safe, I implemented a static
Synchronized method (following the lead of the collections in the
System.Collections namespace). It returns a thread safe wrapper around a
Deque object. To implement this, I first made each of the methods and properties in the
virtual. I then derived a private class from the
Deque class called
SynchronizedDeque in which each of the
Deque's methods and properties are overridden.
SynchronizedDeque is created, it is given a
Deque object. It achieves thread safety by locking access to its
Deque object in each of its overridden methods and properties and delegating calls to the
Deque object. The
Synchronized method creates a
SynchronizedDeque object and returns a
Deque reference to it, so it looks and acts just like a regular
I decided it was time to create a new version of the
Deque class that supports generics. Converting the original
Deque class to a generic version was fairly straightforward. I copied the code from the original and changed all references to the items in the
Deque from type
object to type
T. I made
Deque<T> class implement the
IEnumerator<T> interface. What is interesting here is that
IDisposable, so I had to modify my private enumerator class to provide
IDisposable functionality. All of this was rather easy to do.
Deque is still there, unaltered, if you need it.
The Source Code
Deque class resides in the
Sanford.Collections namespace (this used to be the
LSCollections namespace; I felt it needed renaming). And the
Deque<T> class resides in the
Sanford.Collections.Generics namespace. The zipped source code contains several files: the original Deque.cs file, the files implementing the new
Deque<T> class, and the Tester.cs and GenericTester.cs files. The Tester.cs file represents a console application class that tests the functionality of both the
Well, this article has been a change of pace. My last contribution here at CodeProject was a series of articles presenting a toolkit I had spent months working on and researching. In contrast, the
Deque class along with this article was for the most part simple to write. But sometimes the simplest things can be the most useful. At least that's what I'm hoping I've accomplished here. Thanks for your time, and as always comments and suggestions are welcomed.
- September 25, 2005 - first version complete.
- October 15, 2006 - Article revised, and the
Deque<T> class added.