Introduction
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!
Comments