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!

Using a Numbers Table to Iterate Over Dates

I recently wrote some SQL which would do some work for a single day, but I wanted my code to be able to run once for each day in a date range. Luckily for me, I read Gregg Stark's SQL Blog. He recently posted about how to Iterate Over a List of Dates using a Numbers table in SQL. The SQL he gives is pretty much a cookie cutter solution to the problem.

The basic idea of this trick is to have a cursor which is going to allow you to fetch each of the dates into a variable for use in your code.

You first need to have a Numbers table in your database. This is basically just a table which contains a single number for each row. Use the following short snippet to create your Numbers table.

 
CREATE TABLE dbo.Numbers
(
    Number int IDENTITY(1, 1) PRIMARY KEY
)
GO
 
declare @MaxNumber int
set @MaxNumber = 65535
WHILE 1 = 1
BEGIN
    INSERT INTO dbo.Numbers DEFAULT VALUES
    
    IF scope_identity() = @MaxNumber 
    BEGIN
        BREAK
    END
END
GO

Once you have this numbers table you can follow this cookie cutter solution Gregg created which is actually a very nicely written solution to the problem.

Declare @StartDate datetime
Declare @EndDate datetime
 
-- Note: This StartDate is Exclusive and this EndDate is Inclusive
set @StartDate = '10/1/2007'
set @EndDate = '10/9/2007'
 
declare @CurrentDate datetime
 
-- Create the cursor with the dates using the numbers table
declare datecursor cursor forward_only 
    for Select dateadd(d,Number,@StartDate) from Numbers
          where Number <= datediff(d, @StartDate, @EndDate)
          order by Number
open datecursor
 
-- Loop which will exit when we are out of dates to check
while (1=1)
begin
    fetch next from datecursor into @CurrentDate 
    if @@fetch_status <> 0
        break;
    
    -- This is the code which will run for each date
    select * from some_table where DateRecorded = @CurrentDate
 
end
 
-- Cursor Cleanup
close datecursor
deallocate datecursor

Happy SQL writing!

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.

Understanding the Stack Data Structure

I found myself recently explaining a few times how the data structure commonly called a stack works. The technical term for a stack would be a Last in First out Data Structure (LIFO). To practically repeat myself, this means that the last object to go into the structure is the first one which will come out of the structure.

I've heard plenty of interesting analogies for this behavior. All too often I hear this being described as a stack of plates. Plates can be added easily onto the top of the stack, and can be removed from the top of the stack easily. Working with any plates not on the top is difficult because there are other plates on top of them. This is basically how a stack works.

While explaining the push() and pop() methods of stacks, I came up with an analogy which I think is far more interesting. To my students I described the stack as a Pez dispenser. You load the dispenser from the top and unload it from the top.

PezAnalogy

When you get a candy from the dispenser it comes out of the top and you now have possession of it. With a stack you get the value from the top and you now have possession of it. When adding candy to the dispenser you will add it on top of any existing candy. With a stack you will add new values on top of the existing values.

One extra method available to a Stack is the ability to "peek" at the top value without removing it. This is often necessary when using a stack, and also in a Pez dispenser. When you lift the head of the dispenser a little bit you can peek in to check what color is on top. If it is not one you like, you can still close the dispenser without having removed the candy. The same can be done with a stack.

Basic Implementation

Stacks may be implemented easily with an array or a linked-list as the underlying data structures. When drawing a stack it is far more common to draw the array version. There is one pointer of importance with a stack. This pointer is usually called the "top" pointer. It is a pointer which updates every time a "push" or a "pop" occurs, because this pointer will always point to the top of the stack. This is the pointer used to get to the stack and work with it.

The Push and Pop Operations work as the following image shows.

StackOperations

 

Enjoy, and look forward to more blog posts explaining interesting Computer Science topics.

.NET 3.5 is Open Source

Some very surprising news has come from Scott Guthrie in a recent blog post he has made. Visual Studio 2008 and .NET 3.5 will be shipping with the source for the base class libraries. As with a lot of the recent technology coming from Microsoft, the source code is open and not hidden away.

In the past, tools like Reflector have allowed developers to see what is going on within those libraries. These tools will no longer be as necessary. This source code is being released under the Microsoft Reference License (MS-RL). It seems Microsoft has started a new trend for itself in releasing its source code.

Debugging will now become much much easier with this code being open source. In the past developers have not been able to step into any of the base class libraries. Now that the source is open for everyone to see, people are able to go in and step through this code. This should make debugging much easier and better.

I think this is great that Microsoft is releasing more source code to the general public.

Happy coding.

Numbering the Rows Returned from a SQL Query

Outside of SQL it would be quite easy to number the rows returned from query, but to do so inside of the SQL is a bit more difficult. I recently wanted to be able to number the rows returned from a query in a stored procedure. I am using SQL Server 2000, so I cannot use row_number().

I was going to ask my go to SQL guy, Gregg Stark, how to do this, but while in the process of asking him for a good method of doing this, I came up with the solution. My cool trick for numbering the rows returned from a query is useful because I don't actually want to return these rows to other code. I want to store them back into my database ordered differently than the numbering, and using a table variable will allow me to do exactly what I am trying to do.

First we need to create a table variable. We will define that table as having an identity column plus any other columns we happen to need. We then insert into that table all of the values returned from our query.

declare @t table (Rank int identity(1,1), UserName nvarchar(256), Points int)
insert into @t
select UserName, sum(PointsEarned) as Points
from UserRecognition
group by UserName

After running this part we have created a table variable which contains the information we want. We can then select data out of this as if it were a normal table. In this example I am able to obtain a ranking for my users based on their earned points. This lets me store that ranking without having them stored in ranking order.

It is obviously much easier to do this in SQL 2005, but this is a very cool trick for those of us using SQL Server 2000. Let me know what you think, and if you have any cool improvements.

Dangers of Using Floating Point Numbers

An interesting question came up from a few of my students while teaching my class. Some of them discovered a bug in their programs which they did not understand. They were writing a program which was doing some calculations on currency.

Computer Programmers commonly use floating point numbers, but I am sure that not all of them really understand what is going on underneath the hood. As I am sure everyone reading this knows, all data is stored in binary format on computers. In base 10 as with all numbering systems with a base, each digit is a round number in the base. The fractional amounts are what is interesting and specific to floating point numbers and not to integers.

When using floating point numbers they aren't stored in a way which is intuitive to base 10 users. As an example I will use the fractional amount 1/4. To make seeing the conversion easier I'll say that it is also 25/100 or really 2/10 + 5/100.

In a base 10 floating point number we may represent this number as the following.

0.25

If we were to write that same number in binary format we should note that it is 1/4 or really 0/2 + 1/4.

0.01

You'll want to notice here that those two numbers are not similar, and as you can probably guess, some examples would not come out quite so cleanly.

The problem which the students came across stemmed from subtracting 10 cents from some amount of money. I'll use $100.00 as my example. When the students did the calculation it worked in the following way:

100.00 - 0.1 = 99.900000000000006

FloatingPointError

That seems to not make sense, but it does make some sense. There are numbers which in base 10 will have decimal places which will extend on, and we have to round them at some point. A good example of this is 1/3 which can be written roughly as any of the following

0.3

0.33

0.33333333333

All of those are approximations of that fractional amount. In binary we have the same type of problem, because 0.1 cannot be represented correctly in binary. This causes a problem; it will round at a certain point, and because the number isn't represented correctly, the calculation is done incorrectly. In many other languages it hides away that inaccuracy, but Python allows you to see it.

It is important to know how your floating point numbers are working underneath. Be careful. The computer doesn't speak our language.

Teaching Introduction to Computer Programming

I recently started teaching a course for the Computer Science Department at Kent State University. I am teaching a course called Introduction to Computer Programming. It is a course teaching non-computer science majors the basics of programming.

In this course the students learn simple concepts and ideas behind programming, and along the way will learn to develop simple applications. The students who take this course come from many different areas: Technology, Education, Art History, Visual Communication Design, etc.

I am enjoying teaching the course, and it is beneficial not just to the students but to me as well. As I am teaching this course I am refreshing my memory on a lot of different areas of computer science which I believe are very important to software development.

Python is the programming language of choice for this class. It has been chosen for many reasons, but a few choice ones are: Python's being a very high level language, ease of use, quick development, works with Windows, Linux, and Mac OS. We have Mac, Linux, and Windows users in the class so it is nice to use a language which is easy to develop in and works well in each of the operating systems.

In an effort to start posting more to my blog perhaps I can post a few of the interesting concepts which are applicable to all programming not just Python.

Installing SQL Server Management Studio with SQL Server

Update (24 March 2008): Steve Smith found a more reliable solution to install the SQL Server Client Tools. Once in the tools folder open the setup folder and in there is a SqlRun_Tools.msi file. If you run that it should actually install SSMS.

When I recently installed SQL Server 2005 and SQL Server Management Studio on my computer it did not install SSMS or any of the other Client Tools. When running the installation of SQL Server 2005 I followed along with the instructions. I individually selected each component to install including the Client Tools for SQL Server. When the installation finished there was no SQL Server Management Studio.

Figuring this might be a difficult thing to Google for, I asked Steve Smith if he knew how to get the client tools. He told me that just about the only way to get SSMS to install was to sacrifice a chicken and hope for luck, because there is something weird which has to be done in order to get the program to install.

Upon scouring the folders on the disc, I discovered that the default setup file is coming from a servers folder. I tried using the setup file from the tools folder. This should have worked, but I had a slight problem. Since I had told SQL Sever to install the client tools from the wrong setup file it now believed I had them installed already and would not install them.

SQL Server 2005 Install Folders

Since the installation defaults to the Servers setup file, I never even saw the tools install. There was also no reason to even suspect one since the primary setup file claimed to be able to install the client tools.

I had to uninstall and reinstall SQL Server without the Client tools and then the setup file from the client tools would install SQL Server Management Studio. This was quite a pain, and I don't understand why the client tools are listed as options in a setup file which cannot install them. I think this is a bit crazy, but at least now when I install it I don't have this problem anymore.

How to Convert from hex to int

I recently needed to convert hexadecimal numbers into integer numbers. So for your benefit, and for mine when I forget how to do this, I will tell you a couple of ways to convert numbers of these types. Both methods are quite simple and easy to use.

string myHexNumber = "C4FFB716";
int myIntNumber = Int32.Parse(myHexNumber, System.Globalization.NumberStyles.HexNumber);

 

 This will convert a hexadecimal number in string format into an integer number. You could also do the following.

string myHexNumber = "C4FFB716";
int myIntNumber = Convert.ToInt32(myHexNumber, 16);

 

In this case you have easily converted from a hexadecimal string into an integer. If you want to convert from a base other than 16 into an integer you can pass either 2 or 8 instead of 16 to this method.

(Yes, I am aware that those are terrible variable names. This is merely an example.)

Enjoy!