About Stacks

A stack data struture is a fundamental structure. It is the same as a List or array. Single dimension. Stacks are used to implement the undo feature. It is used in more complex code such as building compilers (e.g. synthax checking) and evaluating expressions.

The best way to think of stacks to visualize its structure, is stacks are like a stack of books. You can only remove the top book. To get to the bottom you have to remove all books. This is also called the Last in first out (LIFO) principle. This is why we can use stacks to implement undo features.

Internally we use an array or linkedlist to store the items in a stack, so \a stack is just a wrapper around an array or a linked list that gives us a different way of manipulating and accessing the data.

For demonstration. Stacks are implemented with a few core features as below. It's important to notice that stacks do not implement lookups. That is not what stacks are used for.

C#
public class Stack<T>{
	
	private T[] _stackData; 
	public void push(T t){
    	// insert an item to the top of the stack. 
	}
	
	public T pop(){
		// remove the top item and return it
	}
    
    public T peek() {
        // returns the top item in the stack without removing it.
    }
	
	public bool isEmpty(){
	}
	
	public bool isFull(){
	}
}

Included in .NET
Stacks are already included in .Net framework so we dont have to implement ourselves. Although it is important to learn how one is implemented. {: .prompt-tip}

Specs

All operations in a stack are constant time O(1). This is because adding and removing an item at an edge of a stack or array is always a O(1) operation. So is peeking and isEmpty checks.

Implementing a stack with Linked list

The same basic internal structure

Notice how stacks store their data internally as array as well. In this implementation, we will use a half-implemented linked list instead:

C#
public class Stack<T> {
    public Node head;
    
    public void push(T data) {
        var newNode = new Node<T>(data, head);
        head = newNode;
    }
    
    public T pop() {
        if (head == null)
            throw new Exception("Stack is empty");
        var currentNode = head;
        head = currentNode.next;
        currentNode.next = null;
        return currentNode.data;
    }

    public T peek() {
        if (head == null)
            throw new Exception("Stack is empty")
        return head.data;
    }
    
    
}
// The data class
public class Node<T> {
    public T data;
    public Node? nextNode;
    
    public Node<T>(T data, Node? nextNode) {
        this.data = data;
        this.nextNode = nextNode;
    } 
}

Linked lists
Ideally in real world application, we would not implement a linked list structure inside a stack, instead we would use readily made available linked list from .NET to store data. However, for demonstration purposes, these raw implementations will be shown. {: .prompt-tip}

Usecase 1: Reverse a string

var mystring = "Hello Jonh";

This is a naive method: Although we could implement it just fine, however since strings are immutable, everytime we concatonate a string it will create a new object in memory. This leads to large overhead.

C#
var stack = new Stacks<String>();
var reversed = "";

foreach (var i in mystring) {
    stack.push(i);
}
foreach (var i in mystring) {
    reversed += stack.pop()
}

StringBuilder / string buffer method: To solve the memory overhead, we need to use a mutable version of a string. A string builder.

C#
var stack = new Stacks<String>();
var sb = new StringBuilder();

foreach (var i in mystring) {
    stack.push(i);
}
foreach (var i in mystring) {
    sb.Append(i);
}
Console.WriteLine(sb);

Usecase 2: Balanced string

How can we design a synthax checking implementation using stacks. The problem goes something like this:

Given a string, find the order of open or closed brackets in the string to ensure each open bracket have its closing counter part. Return true if it is balanced, and false if its not balanced.

The algorithm goes like this:

Plain Text

stack = new Stack()
foreach character in string {
    if character is open bracket
        stack.add(character)
    if character is closing bracket
        stack.removeTop()
}
return (stack is empty)

Implementation

We can simply implement a basic version that checks only for some standard brackets ( ) <> [] {}

C#
public bool isBalanced(String input) {
    Stack<Char> stack = new Stack<Char>();
    
    foreach (var letter in input) {
        if (letter == '(' || letter == '<' || letter == '[' || letter == '{')
            stack.push(letter);
            
        if (letter == ')' || letter == '>' || letter == ']' || letter == '}') {
            if (stack.isEmpty()) return false;
            stack.pop();
        }
        
    }
    return stack.isEmpty();
}

Adding checks for incorrect end cases will result in such spaghetti code:

C#
public bool isBalanced(String input) {
    Stack<Char> stack = new Stack<Char>();
    
    foreach (var letter in input) {
        if (letter == '(' || letter == '<' || letter == '[' || letter == '{')
            stack.push(letter);
            
        if (letter == ')' || letter == '>' || letter == ']' || letter == '}') {
            if (stack.isEmpty()) return false;
            var top = stack.pop();
            if (
                (letter == ')' && top != '(') ||
                (letter == '>' && top != '<') ||
                (letter == ']' && top != '[') ||
                (letter == '}' && top != '{') 
            ) return false;
        }
    }
    return stack.isEmpty();
}

Refactoring

We can extract the boolean logics to make the code more readable:

C#
public bool isBalanced(String input) {
    Stack<Char> stack = new Stack<Char>();
    
    foreach (var letter in input) {
        if (isOpenBracket(letter.ToString()))
            stack.Push(letter);
            
        if (isCloseBracket(letter.ToString())) {
            if (stack.Count == 0) return false;
            
            var top = stack.Pop();
            if (!isBracketMatch(letter.ToString(), top.ToString())) 
                return false;
        }
    }
    return (stack.Count == 0);
}

The rest of the logics can be written in a more concise and extensible matter, store the open brackets and close brackets as a list.

C#
private List<String> openBrackets = new List<String>() { 
    "<", "(", "{", "["
};
private List<String> closeBrackets = new List<String>() {
    ">", ")", "}", "]"
};

private bool isOpenBracket(String letter) {
    return openBrackets.Contains(letter);
}

private bool isCloseBracket(String letter) {
    return closeBrackets.Contains(letter);
}

private bool isBracketMatch(String leftBracket, String rightBracket) {
    return (openBrackets.IndexOf(leftBracket) == closeBrackets.IndexOf(rightBracket));
}

Implementing a stack with Arrays

In our previous example a stack was implemented using an internal datastructure of a linked list. Here we will demonstate the same attempt using an array instead.

When it comes to array type implementation, it is easier to implement a fixed sized stack.

C#
public class Stack<T> {
    private T[] storage;
    public int lastItemIndex = 0;
    
    public Stacks2(int stackSize) {
        storage = new T[stackSize];
    }
    
    public void push(T item) {
        if (isFull())
            throw new StackOverflowException();
            
        storage[lastItemIndex] = item;
        lastItemIndex++;
    }
    
    public T pop() {
        if (isEmpty())
            throw new InvalidOperationException();
        
        var item = storage[lastItemIndex-1];
        storage[lastItemIndex-1] = default;
        lastItemIndex--;
        
        return item;
    }
    
    public bool isEmpty() {
        return lastItemIndex < 1;
    }
    
    public bool isFull() {
        return storage.Length <= lastItemIndex; 
    }
}