Stacks
This post will be a first in many going over data structures examples implemented in C#.
These posts are not meant to recommend new ways of approaching old problems. More that I wanted to brush up on some of the more detailed aspects of data structures that I use every day. So many are now built into whatever framework you are using, you don't need to give any thought as to how they work.
I thought a good one to start with is stacks. I will give some general info about them, then get into the actual code.
If you don't care about any of the explanation, and are only looking for code snippets, that's cool too. You can find the full implementation in my Github repository.
General Info About Stacks
Stacks are a collection that adheres to the last in, first out concept. Meaning that the most recent item added to the collection, will be the first removed. No matter how many items it contains.
You can visualize this in the real world with a "stack" of books or a "stack" of plates. When you add a book to the "stack", you set it on the top. If you wanted to remove a book, you would take it from the top, or risk knocking them all over.
Why Would You Use a Stack?
You might at first think that you wouldn't have much use for stacks. In fact, people use stacks all the time.
The back button in your browser is a good example. As you visit a web page it will add it to the stack that is your browser history. When you hit the back button, it "pops" the most recent item off the stack and redirects the user there.
Another example would be tracking matching elements. For example, open and close paranthesis, open and close html tags, etc.
Functionality
Stacks have a couple properties and a few functions that are pretty standard.
The properties consist of variable that tracks the size of the stack. Another that tracks the top element.
There are three main functions associated with a stack. Those are Push, Pop, and IsEmpty.
Push
Push is the insert functionality of the stack collection. It's called "Push" to symbolize pushing the item to the top of the stack. I like to think of it like those spring activated stacks of plates you see at buffets.
Its return type is void and it takes as an argument the item you are adding to the stack.
public void Push(T element){
if(top > size)
throw new Exception("Stack Overflow");
stack[top] = element;
top++;
}
Push runs in O(1) time.
Pop
Pop is the delete functionality of the stack collection. It removes the top item from the stack and returns it. It does not take any arguments.
public T Pop(){
if(IsEmpty())
throw new Exception("Stack Underflow");
else
{
top--;
return stack[top];
}
}
Pop runs in O(1) time.
IsEmpty
As the name implies, the IsEmpty function checks to see if there are any items in our stack. If there are none, it returns true. Otherwise, it returns false.
This function is useful for verifying the stack has content before calling Pop.
public bool IsEmpty(){
if(top == 0)
return true;
else
return false;
}
IsEmpty runs in O(1) time.
Implementation
In my code examples, I have two implementations of stacks. Stack.cs and NodeStack.cs. Both are stacks in the sense they function the way I describe stacks above. The difference is that Stack.cs uses an array to hold the elements, while NodeStack.cs uses a linked list.
Both implementations are efficient and achieve the same goal. The difference being that Array based need to have the size of the array defined ahead of time. This can be a problem if the number of items that you push onto your stack exceeds its size.
//Array Stack
public class Stack <T> : IStack<T>
{
private int top = 0;
private int size;
private T[] stack;
public Stack(int size = 10){
this.size = size;
stack = new T[size];
}
public bool IsEmpty(){
if(top == 0)
return true;
else
return false;
}
public void Push(T element){
if(top > size)
throw new Exception("Stack Overflow");
stack[top] = element;
top++;
}
public T Pop(){
if(IsEmpty())
throw new Exception("Stack Underflow");
else
{
top--;
return stack[top];
}
}
}
Side Note: There is a way to create an array based stack that doesn't run into this issue. You would need to check on push that the stack has space. If it does not, you can create a new array of larger size (usually double) and copy the elements over. This isn't the most efficient, and will have an effect on Big O complexity. But it gets the job done.
//Linked List Stack
public class NodeStack<T> : IStack<T>
{
private Node top;
private int size = 0;
public int Size => size;
public bool IsEmpty(){
return top == null;
}
public void Push(T element){
Node node = new Node(element, top);
top = node;
size++;
}
public T Pop(){
if(IsEmpty())
throw new Exception("Stack Underflow");
else
{
var temp = top.Element;
top = top.Next;
size--;
return temp;
}
}
private class Node
{
public Node(T element, Node next){
this.Element = element;
this.Next = next;
}
public T Element { get;set; }
public Node Next { get;set; }
}
}
The linked list version of the stack also has a separate class within it Node to represent each node of the linked list.
Both implementations use generics so you can store any data type in the stack. I created an IStack interface that implements the Push, Pop, and IsEmpty functions.
public interface IStack<T>
{
bool IsEmpty();
T Pop();
void Push(T element);
}
Running a quick test with both versions using strings as the types, I was get the same output shown below after pushing then popping 3 items into each.
-------------------------------------------------------------------
Test Stack (Push "Item 1", "Item 2", "Item 3")
Item 3
Item 2
Item 1
Test Node Stack (Push "Item 1", "Item 2", "Item 3")
Item 3
Item 2
Item 1
The full implementation can is on Github. As I go through these tutorials, I will add more to this project.
Final Thoughts
As I mentioned above, this isn't anything new. And if whatever framework you are working with provides its own implementation of a stack, use it.
But if you were looking for a straightforward example of how stacks work, I hope this was helpful.as helpful.
Top comments (0)