Data Structures: Stack
Tags: stack, python
Published: 2022-02-25 15:34:17

## 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.

```python
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()`.

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

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

```python
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).

```python
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.

```python
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.

```python
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