30 Days of Algorithms: From Zero to Intermediate (11/30) — Stack

The stack data structure is at the core of depth-first search, but its applications go beyond that.

• Whenever a function is called, it is placed on the stack
• Everytime there is an error in your code you see an error via call stack
• We can use stacks for undo/redo. By storing actions on a stack, the program can reverse or redo them as needed
• Recursive calls rely on stacks to keep track of the different levels of the recursion

Stack example

Stack works on the principle of last in, first out (LIFO).

Callstack visualization

Node

A stack is similar to a queue and is also node-based.

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

    def __repr__(self):
        return f"{self.value}"

Adding an item

When we add a new item to a stack, we need to link the new node with the top element of the current stack. Then, we point the head to the newly created node.