Implementing a Double-Ended Queue (or Deque) in C#

In this article I will be demonstrating an implementation of a Double-Ended Queue (or Deque) in C#.

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 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>.