Brendan Enrick

Daily Software Development

Understanding the Queue Data Structure Using a Simple C# Implementation

Introduction

Queue

The Queue is a very important and common Data Structure in Computer Science. As the name queue suggests, this data structure can be described with an analogy of waiting in a line. There is no cutting allowed in the line, so the first person in the line is the first person out of the line. With the data structure it is the same way First In First Out (FIFO).

The best way of managing the data in a queue in my opinion is by storing the data in a "circle" by this I mean that when we reach the end of the contiguous data if we have room at the beginning we can start filling in there. This data is stored kind of like a snake going through a circular pathway. The snake will grow and shrink as it travels along this path.

Methods of a Queue

There are only two functions which are required with a queue. One will insert data into the queue and one will remove data from the queue. (One to grow the snake and one to shrink the snake) We call these two functions Enqueue and Dequeue.

  • Enqueue is our method for adding new items to the queue. It will add the new items to the back of the queue.
  • Dequeue is our method for removing items from the queue. It will remove items from the front of the queue.

Since I like my collections to not be limited in size, we will also have a private function for increasing the size of the queue if we run out of space and need to add another element.

Common Implementations

Generally a queue will be an array and it will have a pointer to the front of the queue and a pointer to the end of the queue. As new items are added and removed the pointers will adjust themselves. The pointer to the end of the queue is the pointer to the location where the next element will be placed into the queue, and the pointer to the front of the queue is the location of the next element which will come out of the queue.

In my example I have simplified this a little bit by not using pointers. I'll just be using a FrontIndex and a BackIndex which are just integers telling me which index to use for my array.

Simple Sample C# Implementation

As I like doing, this queue will be a Generic queue, so this is how it will be defined.

public class Queue<T>
{
}

With the class defined, I'll start by adding the following properties.

#region Properties
 
/// <summary>
/// The capacity of the Elements Collection
/// </summary>
private int _capacity;
public int Capacity
{
    get { return _capacity; }
    set { _capacity = value; }
}
 
/// <summary>
/// The number of elements currently in the queue.
/// </summary>
private int _length;
public int Length
{
    get { return _length; }
    set { _length = value; }
}
 
/// <summary>
/// The actual data elements stored in the queue.
/// </summary>
private T[] _elements;
protected T[] Elements
{
    get { return _elements; }
    set { _elements = value; }
}
 
/// <summary>
/// This is the index where we will dequeue.
/// </summary>
private int _frontIndex;
public int FrontIndex
{
    get { return _frontIndex; }
    set { _frontIndex = value; }
}
 
/// <summary>
/// This is the index where we will next enqueue a value. 
/// It is calculated based on the Front Index, Length, and Capacity
/// </summary>
public int BackIndex
{
    get { return (FrontIndex + Length) % Capacity; }
}
 
#endregion

Once I have these properties in place I'll add my basic constructors; one which takes no parameters and one which takes a capacity.

#region Constructors
 
public Queue()
{
    Elements = new T[Capacity];
}
 
public Queue(int capacity)
{
    Capacity = capacity;
    Elements = new T[Capacity];
}
 
#endregion

Now that I am able to create the queue, it is time to start adding the functionality. As I've mentioned, we need to have enqueue, dequeue, and the private method IncreaseCapacity.

With Enqueue I'll have it take in an element and then check to see if we have space. If we don't I'll increase the capacity, and if we do I'll add the element at the back index and increment the length. Since we are calculating BackIndex based on the FrontIndex and the length we don't have to manually adjust it.

Dequeue will make sure we are not empty and if we are it will throw an error. We then want to pull the next element out of the front of the queue and adjust our length accordingly. We also want to increment our FrontIndex. Notice that we increment it by 1 and mod it by the Capacity. This gives us the remainder of FrontIndex + 1 / Capacity. This gives us our circular storage. It makes it so when we read the end of the array we start back at the beginning.

#region public methods
 
public void Enqueue(T element)
{
    if (this.Length == Capacity)
    {
        IncreaseCapacity();
    }
    Elements[BackIndex] = element;
    Length++;
}
 
public T Dequeue()
{
    if (this.Length < 1)
    {
        throw new InvalidOperationException("Queue is empty");
    }
    T element = Elements[FrontIndex];
    Elements[FrontIndex] = default(T);
    Length--;
    FrontIndex = (FrontIndex + 1) % Capacity;
    return element;
}
 
#endregion

Increasing the capacity is not very difficult. In this example I am going to add 1 and double the capacity when it needs to be increased. I like the idea of hitting a reset button on the queue every time we increase size, so I'll create a new queue and enqueue into it every element from the current queue using the dequeue method to empty the current one. I'll then assign all of the properties of the new queue to the current one and I am done.

#region protected methods
 
protected void IncreaseCapacity()
{
    this.Capacity++;
    this.Capacity *= 2;
    Queue<T> tempQueue = new Queue<T>(this.Capacity);
    while (this.Length > 0)
    {
        tempQueue.Enqueue(this.Dequeue());
    }
    this.Elements = tempQueue.Elements;
    this.Length = tempQueue.Length;
    this.FrontIndex = tempQueue.FrontIndex;
}
 
#endregion

With this function we should now have a working Queue structure. To test it we can run it through some quick little for loops.

Queue<int> myQueue = new Queue<int>();
for (int i = 0; i < 50; i++)
{
    Console.WriteLine("Enqueue: " + i);
    myQueue.Enqueue(i);
    Console.WriteLine("New Length is: " + myQueue.Length);
}
 
for (int i = 0; i < 50; i++)
{
    Console.WriteLine("Dequeue: " + myQueue.Dequeue());
    Console.WriteLine("New Length is: " + myQueue.Length);
}
 
for (int i = 0; i < 50; i++)
{
    Console.WriteLine("Enqueue: " + i);
    myQueue.Enqueue(i);
    Console.WriteLine("New Length is: " + myQueue.Length);
}
 
for (int i = 0; i < 50; i++)
{
    Console.WriteLine("Dequeue: " + myQueue.Dequeue());
    Console.WriteLine("New Length is: " + myQueue.Length);
}
 
try
{
    myQueue.Dequeue();
}
catch (InvalidOperationException ex)
{
    Console.WriteLine("As expected I received this error: " + ex.Message);
}

Once we run that and see that it works we know that we probably have a Queue that works pretty well.

Once again here is the entire Queue Class.

public class Queue<T>
{
    #region Properties
 
    /// <summary>
    /// The capacity of the Elements Collection
    /// </summary>
    private int _capacity;
    public int Capacity
    {
        get { return _capacity; }
        set { _capacity = value; }
    }
 
    /// <summary>
    /// The number of elements currently in the queue.
    /// </summary>
    private int _length;
    public int Length
    {
        get { return _length; }
        set { _length = value; }
    }
 
    /// <summary>
    /// The actual data elements stored in the queue.
    /// </summary>
    private T[] _elements;
    protected T[] Elements
    {
        get { return _elements; }
        set { _elements = value; }
    }
 
    /// <summary>
    /// This is the index where we will dequeue.
    /// </summary>
    private int _frontIndex;
    public int FrontIndex
    {
        get { return _frontIndex; }
        set { _frontIndex = value; }
    }
 
    /// <summary>
    /// This is the index where we will next enqueue a value. 
    /// It is calculated based on the Front Index, Length, and Capacity
    /// </summary>
    public int BackIndex
    {
        get { return (FrontIndex + Length) % Capacity; }
    }
 
    #endregion
 
    #region Constructors
 
    public Queue()
    {
        Elements = new T[Capacity];
    }
 
    public Queue(int capacity)
    {
        Capacity = capacity;
        Elements = new T[Capacity];
    }
 
    #endregion
 
    #region public methods
 
    public void Enqueue(T element)
    {
        if (this.Length == Capacity)
        {
            IncreaseCapacity();
        }
        Elements[BackIndex] = element;
        Length++;
    }
 
    public T Dequeue()
    {
        if (this.Length < 1)
        {
            throw new InvalidOperationException("Queue is empty");
        }
        T element = Elements[FrontIndex];
        Elements[FrontIndex] = default(T);
        Length--;
        FrontIndex = (FrontIndex + 1) % Capacity;
        return element;
    }
 
    #endregion
 
    #region protected methods
 
    protected void IncreaseCapacity()
    {
        this.Capacity++;
        this.Capacity *= 2;
        Queue<T> tempQueue = new Queue<T>(this.Capacity);
        while (this.Length > 0)
        {
            tempQueue.Enqueue(this.Dequeue());
        }
        this.Elements = tempQueue.Elements;
        this.Length = tempQueue.Length;
        this.FrontIndex = tempQueue.FrontIndex;
    }
 
    #endregion
}

Happy Data Structure Building!

Simple C# Stack Implementation

I've just written a quick little stack implementation for use in explaining the stack data structure. It is written in C# and is not exactly a robust solution, but it works well enough. It is stubbed out with the basics of what is required to have a working stack. If you don't know how a Stack works, I also recommend reading my Simple Explanation of the Stack Data Structure.

For the heck of it, since I love Generics, I decided to make this a Generic Stack. The first step is to create the Generic class definition. To make it Generic we will add <T> into the name of the class.

public class Stack<T>
{
}

Once we have this class we will want to give it some properties. The properties I am going to use for this implementation are; Capacity to hold the amount of space reserved for the Stack, Length to let us know how many elements are currently in our stack, Elements to actually contain our elements, and Index to keep track of which element is currently on the top of the stack.

#region Properties
 
private int _capacity;
public int Capacity
{
    get { return _capacity; }
    set { _capacity = value; }
}
 
public int Length
{
    get { return Index + 1; }
}
 
private T[] _elements;
protected T[] Elements
{
    get { return _elements; }
    set { _elements = value; }
}
 
private int _index = -1;
public int Index
{
    get { return _index; }
    set { _index = value; }
}
 
#endregion

We have initialized Index to -1 and Length is always Index + 1, so right now Length is 0. Notice that Elements is an array of T elements. When someone instantiates this stack class T will be defined as some type.

In our constructor we will want to initialize Elements to be an empty array for us to store out data. For this simple example I have two constructors. One of them takes 0 parameters and creates an empty array, and the other constructors takes an initial capacity for the array.

public Stack()
{
    Elements = new T[Capacity];
}
 
public Stack(int capacity)
{
    Capacity = capacity;
    Elements = new T[Capacity];
}

Next we need to create the basic functions to perform the operations we require with a stack. The first operation needed is a way to add data to the stack. We do this using the Push method. Push will take an element of type T, and it will push it onto our stack. If we are out of space on our stack, Push will need to create more space for us, so we will also create a method for  increasing out capacity. To get data out of the stack we will need a Pop method. This method will remove the top element from the stack and return it to us. It should throw an error if the stack is empty. Sometimes it is needed in a stack to be able to check the top element without removing it. I will call this method peek. This could have been achieved by calling myStack.Push(myStack.Pop()), but I think it is much cleaner to just create this simple method.

public void Push(T element)
{
    if (this.Length == Capacity)
    {
        IncreaseCapacity();
    }
    Index++;
    Elements[Index] = element;
}
 
public T Pop()
{
    if (this.Length < 1)
    {
        throw new InvalidOperationException("Stack is empty");
    }
 
    T element = Elements[Index];
    Elements[Index] = default(T);
    Index--;
    return element;
}
 
public T Peek()
{
    if (this.Length < 1)
    {
        throw new InvalidOperationException("Stack is empty");
    }
 
    return Elements[Index];
}
 
private void IncreaseCapacity()
{
    Capacity++;
    Capacity *= 2;
    T[] newElements = new T[Capacity];
    Array.Copy(Elements, newElements, Elements.Length);
    Elements = newElements;
}

At this point we now have a working stack. We can push, pop, and peek. So now we write a tiny little command line program to test out our stack. I'll use some for loops to throw some data into the stack and use for loops to peek at the data and pop it off. I'll then make sure I can get my stack empty errors.

class Program
{
    static void Main(string[] args)
    {
        Stack<int> myStack = new Stack<int>();
        for (int i = 0; i < 50; i++)
        {
            Console.WriteLine("Pushing: " + i);
            myStack.Push(i);
            Console.WriteLine("New Length is: " + myStack.Length);
        }
 
        for (int i = 0; i < 50; i++)
        {
            Console.WriteLine("Peeking First: " + myStack.Peek());
            Console.WriteLine("Popping: " + myStack.Pop());
            Console.WriteLine("New Length is: " + myStack.Length);
        }
 
        try
        {
            myStack.Peek();
        }
        catch (InvalidOperationException ex)
        {
            Console.WriteLine("As expected I received this error: " + ex.Message);
        }
 
        try
        {
            myStack.Pop();
        }
        catch (InvalidOperationException ex)
        {
            Console.WriteLine("As expected I received this error: " + ex.Message);
        }
 
        Console.WriteLine("Press the enter key to exit");
        Console.ReadLine();
    }
}

As I said, this is not the most robust and best written stack ever. It isn't designed to be, but it explains the basics of how a stack works. I hope you've enjoyed this. Happy Generic Stack writing.

Generic List AddRange, Remove, and Count Performance

The .NET System.Collections.Generic.List class is not a linked list as non-.NET users might expect. This list class is actually more like an array list than a linked list. Because of this it has some of the benefits of arrays. Simply because of the array data structure which exists within the generic list class, the class is able to achieve a constant time Count function. The basic array data structure is a collection of objects which are stored contiguously in memory, and because of this it makes counting them easy. It also makes it quite easy to index into a specific location, because you can just jump straight to the correct location in memory. With a linked list one has to traverse the list. The advantage of the linked list is that it is held together using pointers, so if you want to add nodes it is simply an update to pointers. This means that adding a collection of nodes can take constant time.

I would highly recommend against the array list if you will be adding and removing objects from this collection often. Since there is an allocated amount of space in memory for the array this means that if you need to exceed this space then you will need to create a new list. Using Big O notation the AddRange function of list will take O(n) time to complete. The n in this case is the number of elements to add. This doesn't seem to bad, but when the allotted space is exceeded the array will need to move and recreate itself with more space. This is the big performance hit. For this operation it will have O(n+m) time, because you will have to do the regular n operations plus m operations for the original data in the array.

Removing an element from an array requires a little bit of work. One reason for this is that the array data structure should never contain an empty space. This means that first you will need to perform a linear search algorithm to find the element to remove. Stepping one by one through the list. Upon reaching the element to remove, it is removed, but then all the elements after that one must be moved forward in the array so no space exists. This causes the remove function to perform in linear time.

  • Capacity O(1)
  • Count O(1)
  • AddRange O(n) or O(n+m)
  • Remove O(n)

I am planning to write of series of little bits of stuff. If you catch any mistakes in any of this series please comment on the correction ASAP. I don't want to be passing along incorrect information.

Enjoy! 

Great C# to VB and VB to C# Converters

I was recently on Developer Fusion when I noticed some simple and easy to use C# to VB and VB to C# converters. It is not difficult to translate code from one language to the other, but sometimes I'll want to test out a code snippet from some site and it is in VB. I use C# and I don't want to have to sit there translating 20 lines of code, and I also don't want to go and get an expensive converter. These seem to do a reasonable job converting between the two languages. I've used them a fair amount so far, and I haven't run into a problem with them yet. I suggest you check them out and bookmark them. They've saved me plenty of time already.

Infinite Loop in a Property

Earlier today I was trying to debug a Stack Overflow Exception I was receiving. While debugging I was stepping into the function where the problem was occurring. I could not seem to find the problem. A line of code was calling a function and passing it a few properties as parameters and the value returned by the function was being stored in another property. Without really paying attention to which properties I was stepping into I just clicked through them and then it would throw the exception. I was quite confused and did not even think that it could be a problem with the properties, because I had stepped through them. Well, I as with many other people are annoyed when I am debugging and it steps into a property with no extra logic. Sometimes when I create a property I remember to add the DebuggerStepThrough property. If you don't know what that is I recommend you learn what it is and use it.

When a property has no extra logic in it I obviously don't care to step through its execution it is not the problem.... except when it is.

Someone added a property to a class recently and remembered to add the DebuggerStepThrough property to it. The problem is that this simple property created an infinite loop, which I did not even think to check because some of the properties I was stepping into. Only one did I not step into and it had the problem. It had the following problem.


private int _x;
[DebuggerStepThrough]
public int X
{
    get
    {
        return _x;
    }
    set
    {
        X = value;
    }
}

When I tried to set the value I jumped into a recursive loop which the debugger stepped through so it did not even let me see the problem when I was trying to debug. Gotta make sure that doesn't happen. Kind of bad when a property calls itself instead of setting the private member it is supposed to access.

Simple Lazy Loading

Lately, I’ve noticed a lot of people who are not careful about how they load objects. Managing objects is a fundamentally important part of software development.

Lets say for example I have an integer in the query string, and I need to use this number in a few places on my page. Well it is obviously inefficient and an ugly process to check the query string and parse the value into an integer every time I want to access that number. I could also at the beginning just grab the number, but this would become a problem if I rearranged things. There is also a chance the execution will not require even checking the query string, and then I will have loaded that value for no reason.

This is a very simple and easy way of retrieving an number from a query string.

private int _pageId = 0;
private int PageId
{
    get
    {
        if (_pageId == 0)
        {
            int myInt;
            int.TryParse(Request.QueryString[”pageId”], out myInt);
            _pageId = myInt;
        }
        return _pageId;
    }
}

With this I no longer have to parse the query string or have the ugly Request.QueryString all through my code. One nice thing is that once I have successfully loaded a valid pageId it will not reference the query string again. As you can probably see this is also helpful when making a database call or any other time consuming work to get some data.

This is very useful for more complex data structures. When the object being loaded is large we want to avoid loading it if we do not have to and also loading it more than once. This is what we can achieve here. In that case you would compare the value to null instead of 0. This will let you know if it has yet been loaded.