From Theory to Practice: Implementing Stacks in C#

A stack stores data in the same way arrays do. In fact, a stack data structure is actually just an array with limitations. The purposeful “limitations” that we place on stacks are:

• Insertion only at the end of the stack (push)
• Deletion only at the end of the stack (pop)
• Only the last element of the stack can be read. (peek)

Push, pop, and peek are operations given to the stack, because it closely resembles a stack of plates.

A stack functions very similar to a stack of plates; you can’t grab dishes from the middle (ok… maybe you can but it is NOT going to be fun). Similarly, you can only add dishes to the bottom and remove them from the top.

This analogy can be confusing since we are most often used to arrays being on their side.

As you can see, the first item in the array becomes the bottom of the stack and the last item becomes the top.

Pushing onto a stack

Let’s see how a stack works step-by-step by inserting a new value onto the stack (aka “push”). Just like adding a new dish to the top of the stack a push is very similar.

Nothing complicated has happened. All we’ve done is just insert 2 into the end of the array.

Now, let’s push a 6!

Now, let’s push a 9!

If you notice, we’re always adding data to the top (or the end from horizontal perspective) of the stack. We cannot insert from the bottom or middle of the stack, because the nature of the stack is like plates. Trying to insert a plate into the middle of the stack will be difficult.

Popping elements off the stack

Removing elements from the top of the stack is called popping from the stack. Because the stack’s restrictions, we can only pop data from the top.

The stack now only contains two elements.

Let’s pop the next element off the stack.

The acronym LIFO, which describes “Last In, First Out”, often is used to describes stacks. This means that the last item pushed onto a stack is always the first item popped off. Very similar to a canister of tennis balls, the first tennis balls that go in are always the first to be taken out.

Abstract Data Type

Most programming languages come with a stack as a built-in data structures and if you want to you can skip this entire part!

Stacks are built “on top” of regular data structures like arrays and list. This is why stacks are often referred to as “abstract data types”.

I’m guessing that many people reading this blog want to build one, so here is one way to implement a stack in C#:

using System;
using System.Collections.Generic;

public class Stack<T>
{
    private List<T> data;

    public Stack()
    {
        data = new List<T>();
    }

    public void Push(T element)
    {
        data.Add(element);
    }

    public T Pop()
    {
        if (data.Count == 0)
        {
            throw new InvalidOperationException("Stack is empty.");
        }

        object topElement = data[data.Count - 1];
        data.RemoveAt(data.Count - 1);
        return topElement;
    }

    public T Read()
    {
        if (data.Count == 0)
        {
            throw new InvalidOperationException("Stack is empty.");
        }

        return data[data.Count - 1];
    }
}

As you can see, our stack implementation stores the data in a List<t> called data. We could %100 use a regular array, but List<T> is easier due to builtin methods like Add, RemoveAt, and Count .

By building the stack class around a list, we have a built-in interface that forces the user to interact with data in limited ways. By adding extra code on top of the list, we can only read the last item and the same goes for inserting at the end. The stack is similar to a set of rules around how we can access an array.

Stacks in real-life

The one area where stacks really shine tends to be string questions. String questions that can use a stack will involve iterating over a string and putting strings onto the stack, while comparing the op of the stack with the current character at each iteration. Stacks are useful for strings because it saves the “history” of the previous characters.

Linter aka “Valid Parentheses”

One of the easiest ways to learn stacks and how they work is to make a very primitive linter. This is also a LeetCode question called “Valid Parentheses”.

This hypothetical linter is one that inspects the parentheses, square brackets, and curly braces and determines is they are valid.

(var x = 2); //valid
(var x = 2;  //not valid
(var x = [1, 2, 3)]; //not valid

Example #3 can be tricky. Notice that there is a matching set of parentheses and a matching pair of square brackets. But the closing parenthesis is in the wrong place, as it doesn’t match the immediate opening brace.

Implementation

1. We must prepare a Dictionary<> to store potential bracket values to compare against.
2. We must prepare an empty stack. We can just use the built in stack provided to us by C#.
3. Create a for loop that will read each character in the string from left to right
4. Check Dictionary, If we find any character that isn’t a type of brace (“(), “[]”, “{}”), ignore it.
5. If we find opening braces, we push it onto the stack.
6. if we find closing braces, we pop the top element in the stack and inspect it
   • If the item we popped does not match, this is a syntax error
   • if we couldn’t pop an element because the stack is empty, that means the current closing brace doesn’t have a corresponding opening brace beforehand.
   • if the item we popped is a corresponding match for the current closing brace, it means we’ve successfully close that opening brace.
7. If we make it to the end of the line and there’s still something left on the stack, that also means error.

public class Linter
{
    public string Lint(string text)
    {
        Dictionary<char, char> matches = new();
        matches.Add('(', ')');
        matches.Add('[', ']');
        matches.Add('{', '}');
        Stack<char> stack = new();
        //Iterate thru string
        foreach(char c in s)
        {
            //If char is in dictionary, push onto stack
            if(matches.ContainsKey(c))
            {
                stack.Push(c);
            }
            else
            {
                //If no matches found, return false
                if(stack.Count == 0)
                {
                    return false;
                }
                //check the top of stack
                char previousOpening = stack.Pop();
                //if it does not match anything, return false
                if(matches[previousOpening] != c)
                {
                    return false;
                }
            }
        }
        return stack.Count == 0;
    }
}