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
Stack can be implemented as an array (or a Python list). Let's create a class representing our Stack together with our
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
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!
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!