Introduction
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 Deque class.
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.
The Deque Class
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, ICollection, IEnumerable, and ICloneable.
In addition to the methods and properties in those interfaces, the Deque class also has several methods found in the Queue class.
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.
The 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 PeekFront and PeekBack methods for peeking at the elements at the front and back of the Deque respectively.
The PushFront and PushBack methods allow you to add elements to the front and back of the Deque respectively, and their counterparts, the PopFront and PopBack methods, allow you to remove elements from the front and back of the Deque respectively.
Implementation
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 Deque.
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 IEnumerator specification.
Synchronization
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 Deque class 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.
When a 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 Deque object.
The Deque<T> Class
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 IEnumerator<T> implements IDisposable, so I had to modify my private enumerator class to provide IDisposable functionality. All of this was rather easy to do.
The original Deque is still there, unaltered, if you need it.
The Source Code
The 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 Deque and Deque<T> classes.
Conclusion
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.
History
- September 25, 2005 - first version complete.
- October 15, 2006 - Article revised, and the
Deque<T> class added.
