Data Structures: Stack

What is a Stack

Stack is a simple, yet very handy data structure that can be used in solving all kinds of programming problems.

Imagine a pile of plates stacked on top of one another. You can either put a new plate on top of the pile or you can remove the top plate. In order to get to the plate located at the very bottom, first you have to remove all the plates above this plate. And that is exactly how Stack works.

In programming terms, we say that it follows the Last In First Out (LIFO) principle, meaning that the last element added to the Stack will be the first element to be removed.

So, Stack is defined by two main features, which are adding a value on top of the Stack and removing the top value from the Stack. In Stack terms however, adding a value to the Stack is called push and removing the top value from the Stack is called pop.

Implementation of Stack

Stack can be implemented as an array (or a Python list). Let's create a class representing our Stack together with our push and pop functionality and a little additional function is_empty to check if the Stack is empty.

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

    def push(self, value):
        self.data.append(value)

    def pop(self):
        return self.data.pop()

    def is_empty(self):
        return len(self.data) == 0

Now we can simply create an instance of our Stack, push some values into it, pop some values out of it and see how it interacts.

But firstly, let's create a small helper function that will nicely print our Stack to the console on calling print().

def __repr__(self):
    return " ".join([ str(value) for value in self.data ])

We're all set, let's see how our Stack performs.

stack = Stack()

stack.push(1)
stack.push(2)
stack.push(3)
print(stack) # 1 2 3

stack.pop()
print(stack) # 1 2

stack.pop()
print(stack) # 1

Values are pushed to the Stack one after another and are popped in the order following the LIFO principle. Great!

Usage of Stack

Stack is used in a variety of programming problems, one of them being Tree/Graph Traversal, more specifically the Depth First Search Algorithm. Let's see how our Stack can be of help!

Firstly, let’s create a simple Tree (and Node class).

class Node:
    def __init__(self, value, children = []):
        self.value = value
        self.children = children

class Tree:
    def __init__(self, root = None):
        self.root = root

Now, let’s implement the Depth First Search algorithm using our Stack.

def depth_first_search(self):
    if not self.root:
        return None

    stack = Stack()
    stack.push(self.root)

    while not stack.is_empty():
        node = stack.pop()
        print(node.value)

        for child in node.children:
            stack.push(child)

Firstly, we initialise our Stack and push the root node of our Tree into it as the first value (only if it exists). Then, we are popping nodes from the Stack one by one and printing them to the console until the Stack is completely empty. However, with every node being popped from the Stack, we add all its children to the Stack to be dealt with later.

Let's initialise and build our Tree and run the depth_first_search() algorithm on it.

tree = Tree(
    Node(1, [
        Node(2, [
            Node(4),
            Node(5)
        ]),
        Node(3, [
            Node(6),
            Node(7)
        ])
]))

tree.depth_first_search()
# 1 3 7 6 2 5 4

As we can clearly see, the output is exactly what we expected. Yay! We have successfully created a Stack from scratch and used it to solve Tree Traversal.

I hope you enjoyed this article and hopefully learned something new!

Best of luck on your coding journey!
Tomas