Queue Collection - C#

Problem

Remember the last 100 items accessed and store them in a data structure. The furthest back item must be evicted to make space for the newest. You want good performance and small memory footprint.

Solution: C#

We need the Queue object for our solution. First, let's look at some methods this class has. I am going to show the Enqueue and Dequeue methods in the following example of the built-in Queue. Make sure you include System.Collections.Generic at the top of your file.

//
// 1.
//
Queue<string> queue = new Queue<string>();
//
// 2.
//
queue.Enqueue("box"); // contains the string "box"
queue.Enqueue("cat"); // "cat" and then "box"
//
// 3.
//
string removedString = queue.Dequeue(); // now contains "cat" only

1. New Queue
   In the start of the method above, we create a new Queue generic object. It stores the type of string, which is in the brackets.
2. Enqueue is called
   This adds the specified argument string to the contents of the Queue. Enqueue is next called again.
3. Dequeue does the opposite
   Dequeue removes the first queued item and then returns the object removed.

How can I combine Queue and Dictionary?

Here we combine the Queue with a Dictionary to achieve a cache that both has constant O(1) access time, and also the FIFO behavior of Queue. This is important because it can yield the optimizations of both data structures. It may be overly complex for many scenarios, however.

class QueueCache<T, V> : CollectionBase
{
    Queue<T> _qInner = new Queue<T>();
    Dictionary<T, V> _dInner = new Dictionary<T, V>();

    int _sizeLimit;

    public QueueCache()
        : this(25)
    {
    }

    public QueueCache(int sizeLimitIn)
    {
        //
        // Use Debug.Assert for testing.
        //
        Debug.Assert(sizeLimitIn > 0);
        _sizeLimit = sizeLimitIn;
    }

    public bool TryGetValue(T keyIn, out V outParam)
    {
        return _dInner.TryGetValue(keyIn, out outParam);
    }

    public V AddToCache(T keyCache, V valToCache)
    {
        //
        // Add to our Dictionary and Queue. If we grow too large,
        // remove from both the Queue and the Dictionary.
        //
        _qInner.Enqueue(keyCache);
        _dInner.Add(keyCache, valToCache);

        if (_qInner.Count > _sizeLimit)
        {
            T rem = _qInner.Dequeue();
            _dInner.Remove(rem);
        }
        return valToCache;
    }
}

• T and V types
  These have nothing to do with television, but they are simply a notation for any data type. They allow you to use data types as objects.
• Adds to both structures
  The AddToCache method adds an object of any type to both the internal Queue and the Dictionary. These two structures must be kept in sync.
• Uses Count property to check length
  FIFO queues must expire old entries, so the queue removes the items that are more than 100 objects back. So when you add the 101st object, the first one will be removed.
• Removes from both
  The class removes objects from both its inner Queue and Dictionary when you specify to remove an item.
• Performance characteristics
  We get O(1) lookup times for the queue, but don't have to deal with a dictionary that grows endlessly, clogging up our computer with useless caches.

How can I use the above class?

At the start of this page, I showed how to use a C# Queue straight from the built-in types, and in this section I show you how to use the custom QueueCache generic. The following example method does some actions with the QueueCache and uses the TryGetValue method.

class TestClass
{
    //
    // Custom field.
    // Note the syntax at the end with the brackets and parenthesis.
    //
    QueueCache<string, string> _neighborCache = new QueueCache<string, string>(10);

    private string TestMethod(string word)
    {
        //
        // Does the cache contain a value for the key "word"?
        //
        string cache;
        if (_neighborCache.TryGetValue(word, out cache))
        {
            return cache;
        }

        //
        // Add the value "cache" to the queue cache.
        // The queue will never grow larger than 25 elements.
        //
        cache = "Value";
        return _neighborCache.AddToCache(word, cache);
    }
}

Discussion

One use for Queue is a history menu in a Windows Forms application that displays the last 15 unique items visited. As I show, you can combine Queue with Dictionary to achieve some of the benefits of both. FIFO caches can be very useful.