A deeper than average look into Stacks [Math Mondays]

Making modifications to stacks to match various use cases.

Hey, it’s your favorite cult leader here 🐱‍👤

Mondays are dedicated to theoretical concepts. We’ll cover ideas in Computer Science💻💻, math, software engineering, and much more. Use these days to strengthen your grip on the fundamentals and 10x your skills 🚀🚀.

To get access to all the articles and support my crippling chocolate milk addiction, consider subscribing if you haven’t already!

p.s. you can learn more about the paid plan here.

---

Stacks are one of the most useful data structures in software engineering. However, not too many people understand how to develop them beyond just the vanilla stacks. This is a pity, because the strength of Stacks is in their flexibility. A good programmer can tweak the baseline stack to significantly improve operations. If you’re here, you probably already know the very basics of stacks (how they are Last In, First Out etc). I won’t waste your time writing yet another surface-level introduction to them. Instead, we will go over some more advanced variants. Later posts will go over the individual extensions in more detail, and talk about how they are implemented into systems.

Implementing Stacks

Vanilla Stacks

For completeness’s sake, I am including the implementation of vanilla stacks, since we will be making modifications to them. Also note that we build the stack on an array list in Python, which has dynamic resizing built in.

class Stack:
    def __init__(self):
        self.items = []

    def push(self, item):
        """Add an item to the top of the stack."""
        self.items.append(item)

    def pop(self):
        """Remove and return the top item of the stack."""
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        return self.items.pop()

    def peek(self):
        """Return the top item without removing it."""
        if self.is_empty():
            raise IndexError("Peek from empty stack")
        return self.items[-1]

    def is_empty(self):
        """Check if the stack is empty."""
        return len(self.items) == 0

Let’s start looking into how to change this up to accomplish various goals.

Using a Singly Linked List

In my computer science undergrad, they made us implement Stacks based on LinkedLists in C (ew). God knows why Universities pride themselves on making the lives of their students harder than they need to be. In theory, Linked lists can be easily resized as the number of elements in the stack grows or shrinks, without the need to allocate a new, larger block of memory and copy the elements to it. This makes them useful for use cases with a lot of dynamic resizing.

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

class LinkedListStack:
    def __init__(self):
        self.top = None
        self.size = 0

    def push(self, value):
        new_node = Node(value)
        new_node.next = self.top
        self.top = new_node
        self.size += 1

    def pop(self):
        if self.is_empty():
            raise IndexError("Pop from empty stack")
        value = self.top.value
        self.top = self.top.next
        self.size -= 1
        return value

    def peek(self):
        if self.is_empty():
            raise IndexError("Peek from empty stack")
        return self.top.value

    def is_empty(self):
        return self.size == 0

However, even from a memory standpoint, LLs are kinda trash because of the added cost per allocation. The general consensus is to build on top of ArrayLists. To quote an excellent post on arrays vs LLs for stacks/queues, “all of the structures support pushing and popping n elements in O(n) time. The linked list versions have better worst-case behavior, but may have a worse overall runtime because of the number of allocations performed. The array versions are slower in the worst-case, but have better overall performance if the time per operation isn't too important.” You can also check the memory utilization graph below-

Image Source

As you can see, in most cases, you will probably not use LLs over Arrays/Lists.

Persistent Stack

In computing, a persistent data structure or not ephemeral data structure is a data structure that always preserves the previous version of itself when it is modified. Such data structures are effectively immutable, as their operations do not (visibly) update the structure in-place, but instead always yield a new updated structure.

Persistence can be good for version control and security (one of the reasons that Functional Programming is regarded as Thread Safe is the immutability of variables. Persistent Data structures share that). This is a great implementation of persistent data structures in Python. Persistent Stacks can be implemented like so-

class PersistentStack:
    def __init__(self):
        self.versions = [[]]
        self.current_version = 0

    def push(self, item):
        new_version = self.versions[self.current_version].copy()
        new_version.append(item)
        self.versions.append(new_version)
        self.current_version += 1

    def pop(self):
        if self.current_version == 0:
            raise IndexError("Pop from an empty stack")

        new_version = self.versions[self.current_version].copy()
        new_version.pop()
        self.versions.append(new_version)
        self.current_version += 1implement

Limiting Stack Size:

In certain use cases, you want to limit the size of your stack. The easiest way to do this is to have a limit that you refuse to go beyond.

def __init__(self, limit=10):
    self.items = []
    self.limit = limit

def push(self, item):
    if len(self.items) >= self.limit:
        raise OverflowError("Stack limit reached.")
    self.items.append(item)

Another possibility is to have a stack that automatically forgets old entries to account for new events. Think about how you would implement that and where that might be more useful. There is also a security aspect to developing this- do you want your user to know the stack limit? The answer depends on what you want to use.

Ensuring Type Safety

Maybe it’s because I’m old, but I’m not a huge fan of dynamic typing. Although I abuse it as much as the next Python bro, I think typed systems are generally more readable, secure, and efficient. Languages like Python allow you to develop mixed-type collections, which are not needed in most cases. Forcing typing is a useful way to boost security/control the chaos. This can be implemented by doing the following

def __init__(self, desired_type):
        self.items = []
        self.desired_type= desired_type

def push(self, item):
    if not isinstance(item, self.desired_type):
        raise TypeError("Item type not allowed...")
    self.items.append(item)

Thread Safety

Thread Safety is another big one that you want to master, especially with how hot concurrency and parallel systems are these days-

import threading

class ThreadSafeStack(Stack):
    def __init__(self):
        super().__init__()
        self.lock = threading.Lock()

    def push(self, item):
        with self.lock:
            super().push(item)

    def pop(self):
        with self.lock:
            return super().pop()

Tracking Min/Max with Stacks

You can effectively track the mins/maxes inserted w/o a heap. It’s a pretty neat trick-

def push(self, item):
    super().push(item)
    if not self.min_stack or item <= self.min_stack[-1]:
        self.min_stack.append(item)

def pop(self):
    item = super().pop()
    if item == self.min_stack[-1]:
        self.min_stack.pop()
    return item

Undo Operations in Stacks

Web browsers, MS Word etc all need a good undo button. You can implement them (this combines well with the limiting size).

def push(self, item):
    self.history_stack.push(self.items.copy())
    super().push(item)

def undo(self):
    self.items = self.history_stack.pop()

Stacks are like Whipped Cream- only vanilla if you don’t know how to use it properly. By tailoring the stack to specific application needs, you can add a lot more flavor to the project. For an example of how a tweak to Stacks can Leetcode problems, check out the Microsoft Interview problem below-

That is it for this piece. I appreciate your time. As always, if you’re interested in working with me or checking out my other work, my links will be at the end of this email/post. If you found value in this write-up, I would appreciate you sharing it with more people. It is word-of-mouth referrals like yours that help me grow.

Save the time, energy, and money you would burn by going through all those videos, courses, products, and ‘coaches’ and easily find all your needs met in one place at ‘Tech Made Simple’! Stay ahead of the curve in AI, software engineering, and the tech industry with expert insights, tips, and resources. 20% off for new subscribers by clicking this link. Subscribe now and simplify your tech journey!

Using this discount will drop the prices-

800 INR (10 USD) → 640 INR (8 USD) per Month

8000 INR (100 USD) → 6400INR (80 USD) per year (533 INR /month)

Reach out to me

Use the links below to check out my other content, learn more about tutoring, reach out to me about projects, or just to say hi.

Small Snippets about Tech, AI and Machine Learning over here

AI Newsletter- https://artificialintelligencemadesimple.substack.com/

My grandma’s favorite Tech Newsletter- https://codinginterviewsmadesimple.substack.com/

Check out my other articles on Medium. : https://rb.gy/zn1aiu

My YouTube: https://rb.gy/88iwdd

Reach out to me on LinkedIn. Let’s connect: https://rb.gy/m5ok2y

My Instagram: https://rb.gy/gmvuy9

My Twitter: https://twitter.com/Machine01776819