In this article we will focus on a complete walk through of a Python stack data structure.
Table of Contents
- What is a stack
- How to create a stack in Python
- How to check if a stack is empty in Python
- How to add elements to a stack in Python
- How to remove elements from a stack in Python
- Conclusion
What is a stack
A stack is an array-like data structure that stores the items using the LIFO (Last In First Out) approach.
You can think of boxes in some storage, where each box is placed on top of another box like this:
As you can see, the boxes were added in the following order: 1 -> 2 -> 3, where box 3 was added last.
Now, if we would like to get to box 1, we will need to remove box 3 first, then box 2, and then get to box 1 making it a reverse order: 3 -> 2 -> 1.
The above examples show the methodology behind the LIFO principle: the last item added will be removed first.
How to create a stack in Python
There are multiple ways of creating stacks in Python:
- using list
- using linked list
- using collections.deque
- using queue.LifoQueue
In this tutorial we will use the simplest approach and create stacks in Python using the list data structure.
Creating an empty stack is identical to creating a list in Python using square brackets [].
Let’s start with creating a new class and initializing it as an empty stack:
class Stack():
def __init__(self):
self.elements = []
Then we will create an empty stack and print in out:
stack = Stack()
print(stack.elements)
You should get:
[]
How to check if a stack is empty in Python
When working with stacks, we often need to know whether they are empty as a requirement for some operations.
For example, when removing elements from a stack, we need to make sure that there are elements to remove (since we can’t remove elements from an empty stack).
Since our implementation of a stack data structure is based on Python list, we can simply check the length of the stack to determine whether it’s empty or not.
In this section we will implement a method check_empty() for checking whether there are elements in a stack for the Stack() class.
def check_empty(self):
if len(self.elements)==0:
return True
else:
return False
It will be added as a method of the Stack() class:
class Stack():
def __init__(self):
self.elements = []
def check_empty(self):
if len(self.elements)==0:
return True
else:
return False
We can test it with an empty stack:
stack = Stack()
stack.check_empty()
And you should get:
True
How to add elements to a stack in Python
Once we have a stack, we can start adding elements to it.
This stack operation is referred to as push to a stack.
Since our stack is created as a list, we can use the .append() method of Python list for adding elements.
In this section we will implement a method push() for adding elements to a stack for the Stack() class.
def push(self, data):
self.elements.append(data)
It will be added as a method of the Stack() class:
class Stack():
def __init__(self):
self.elements = []
def check_empty(self):
if len(self.elements)==0:
return True
else:
return False
def push(self, data):
self.elements.append(data)
Let’s create the same stack as in example section and print out the elements of the stack:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
print(stack.elements)
And you should get:
[1, 2, 3]
How to remove elements from a stack in Python
Once we have a stack with elements, we may want to remove some of them from the stack.
Recall that stacks use the LIFO (Last In First Out) approach, meaning that we can only remove elements that are at the top of the stack at every iteration.
This stack operation is referred to as pop from a stack.
Since our stack is created as a list, we can use the .pop() method of Python list for removing elements (and reference index -1 to reference the top of the stack)
In this section we will implement a method pop() for removing elements from a stack for the Stack() class.
def pop(self):
if self.check_empty():
raise IndexError('Index out of range, the stack is empty.')
else:
self.elements.pop()
It will be added as a method of the Stack() class:
class Stack():
def __init__(self):
self.elements = []
def check_empty(self):
if len(self.elements)==0:
return True
else:
return False
def push(self, data):
self.elements.append(data)
def pop(self):
if self.check_empty():
raise IndexError('Index out of range, the stack is empty.')
else:
self.elements.pop()
Let’s test create the same stack as in previous section, then pop one element and print out the elements of the stack:
stack = Stack()
stack.push(1)
stack.push(2)
stack.push(3)
stack.pop()
print(stack.elements)
And you should get:
[1, 2]
Conclusion
This article is an introductory walkthrough for stack data structure in Python and its functionality which is important to learn as they are used in many areas of programming and in machine learning.
Feel free to leave comments below if you have any questions or have suggestions for some edits and check out more of my Data Structures articles.
