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

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)

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();
    }
}