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