What will we cover in this tutorial?
We will learn what a Stack is and how to implement it in Python.
But why bother, when you can use a Python list as a Stack? Good question. If you understand how a Stack works, you will know when to use it to efficiently solve problems. The best way to learn something, is by trying to implement it.
Why use a Stack? Check out this tutorial on how to Solve a Maze or Find the Nearest Smallest Element Problem.
Step 1: Understand Stack
A Stack in computer science is like a stack of plates. You can add one on top at the time. Or you can remove the top plate one by one.
A stack can have any number of items on it. In the above illustration you see the following.
- (left) A stack with 4 elements (1, 2, 3, 4).
- (mid) A stack of 4 elements where a fifth element is added by a push operation.
- (right) A stack that had 5 elements, but where the last item (5) is removed by a pop operation.
That is a Stack has two vital operations push and pop. Also, these operations should be done in constant time, O(1). That is they should be done with a performance, which is independent of the size of the stack. Say, if the Stack has 2 elements, then a push (or a pop) takes the same time to execute if the Stack has 2,000,000 elements.
Notice the following with a Stack. The last item you add on the Stack is the first one to get removed. That is Last-in-first-out or LIFO.
Step 2: How to represent a Stack item (Node) in Python code
As always, keep things simple.
How can we represent the above efficiently, such that the operations are not becoming expensive.
We only need to keep track of two things.
- The item added before. Starting with the first item to be added to point at None.
- A pointer to the top of the Stack (not in diagram above).
If we have that we can create a Stack. We can make the operations as follows.
- push – Find the top item of the stack using pointer from 2. Then add the new item and let it point at top item. Let stack pointer point at new item.
- pop – Remove top item. Let stack pointer point at item pointed by top item.
Hence, we need a way to represent a item. Such an item is called a Node. This Node should have two things.
- The element it represents.
- A pointer to the next node.
This can be turned into Python code like this.
class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node
This class can take the element and next_node pointer as optional arguments as constructed.
Step 3: Creating the stack class to represent the operations push and pop
Let’s start by creating a new class Stack.
class Stack:
def __init__(self):
self.stack = None
This creates an empty Stack, where we have the pointer self.stack to point at None.
To add an element can be done by adding a new Node and let it point at the current self.stack.
class Stack:
def __init__(self):
self.stack = None
def push(self, element):
node = Node(element, self.stack)
self.stack = node
This works for the initial element push’ed on the Stack and for any element push’ed afterwards.
Now we need to pop the top element of the Stack.
class Stack:
def __init__(self):
self.stack = None
def push(self, element):
node = Node(element, self.stack)
self.stack = node
def pop(self):
element = self.stack.element
self.stack = self.stack.next_node
return element
We need to get the element. Update the self.stack pointer to point to the element below.
Notice, we do not handle the case where the stack is empty, this will cause the pop function to fail. This is handled by adding a a is_empty function, to check whether the Stack is empty.
class Stack:
def __init__(self):
self.stack = None
def push(self, element):
node = Node(element, self.stack)
self.stack = node
def pop(self):
element = self.stack.element
self.stack = self.stack.next_node
return element
def is_empty(self):
return self.stack == None
The full code with a print function
Here the full code is provided with a way to represent the Stack as a string. That way you can print it out.
class Node:
def __init__(self, element=None, next_node=None):
self.element = element
self.next_node = next_node
class Stack:
def __init__(self):
self.stack = None
def push(self, element):
node = Node(element, self.stack)
self.stack = node
def pop(self):
element = self.stack.element
self.stack = self.stack.next_node
return element
def is_empty(self):
return self.stack == None
def __str__(self):
if self.stack is None:
return None
node = self.stack
result = "["
while node is not None:
result += str(node.element) + " "
node = node.next_node
return result[:-1] + "]"
stack = Stack()
for i in range(10):
stack.push(i)
print(stack)
for _ in range(8):
stack.pop()
print(stack)
Where the example code in the end will give the following output.
[9 8 7 6 5 4 3 2 1 0]
[1 0]
Learn Python
Learn Python A BEGINNERS GUIDE TO PYTHON
- 70 pages to get you started on your journey to master Python.
- How to install your setup with Anaconda.
- Written description and introduction to all concepts.
- Jupyter Notebooks prepared for 17 projects.
Python 101: A CRASH COURSE
- How to get started with this 8 hours Python 101: A CRASH COURSE.
- Best practices for learning Python.
- How to download the material to follow along and create projects.
- A chapter for each lesson with a description, code snippets for easy reference, and links to a lesson video.
Expert Data Science Blueprint
Expert Data Science Blueprint
- Master the Data Science Workflow for actionable data insights.
- How to download the material to follow along and create projects.
- A chapter to each lesson with a Description, Learning Objective, and link to the lesson video.
Machine Learning
Machine Learning – The Simple Path to Mastery
- How to get started with Machine Learning.
- How to download the material to follow along and make the projects.
- One chapter for each lesson with a Description, Learning Objectives, and link to the lesson video.
