Data Structures with Python: Stacks
Published on Feb 3, 2022
Stacks is one of the data structures that a programmer needs to understand. In this article, I will explain how to code a basic stacks data structure with Python.
Pre-requisite
In this article, you need to have a knowledge on nodes and linked list before proceeding.
Concept
Imagine gym plates (weights) in a stack. To take out a plate, we can only take out the weight from the top of the stack. And to add a plate, we can only put the plate at the top of the stack.
In this context, stacks data structure is a linked list in a stack. We can only remove the head node in the stack, add node on top of the stack (on top of head node), and also peek the head node in the stack without removing it.
- push - Push/Add new node on top of head node in the stacks
- pop - Pop/Remove node at the head node in the stacks (second node will become the new head node, if there’s any)
- peek - Peek the head node in the linked list
A less frequently used term for stacks is First In, Last Out, or FILO
1st Step: Node
First step we need to create node class:
class Node:
def __init__(self, value, next_node=None):
self.value = value
self.next_node = next_node
def set_next_node(self, next_node):
self.next_node = next_node
def get_next_node(self):
return self.next_node
def get_value(self):
return self.value
This is a basic node
class, so I will not be explaining about this code, and focus more on explaining how to write stacks.
2nd Step: Initialising Stack Class
class Stack:
def __init__(self, limit=None):
self.top_node = None
self.size = 0
self.limit = limit
Initiate a Stack class and define the constructor __init__
method. Set self.top_item
to None, self.size
to 0 and self.limit
to limit (default = None). The self.top_node
will keep track of the top node in the stack, self.size
is the current size of the stack, which will be 0 initially as when we initialized the Stack class, there will be no node yet in the stack. And self.limit
is the limit size of the stack (which will be None by default).
3rd Step: peek, has_space and is_empty
Then write these codes under the same Stack class:
def peek(self):
if not self.is_empty():
return self.top_item.get_value()
print("Nothing to see here!")
def has_space(self):
return self.limit > self.size
def is_empty(self):
return self.size == 0
peek is to see the first node value if the queue is not empty.
has_space is to check if there’s space left to be filled. If the limit is more that the current size, it will return True
, or else, False
.
is_empty is for checking if the queue is empty or not. if self_size
is equal to 0, it will return True
, and if it’s not, False
.
4th Step: Push
def push(self, value):
if self.has_space():
new_node = Node(value)
new_node.set_next_node(self.top_node)
self.top_node = new_node
self.size += 1
else:
print("fullstack!")
First we can write and if statement with self.has_space(). If there’s space available then we can push a node in the stack.
item = Node(value)
is to instantiate a Node with value passed as an argument (have to be in node) and assign it to new_node
variable. Then we can use .set_next_node()
to set the new_node
to point to the current top node in the stack, self.top_node
. And then, we can set the new top node to the new_node
as it will become the new head node. Don’t forget to increment the size by 1 as we have added a new node in the stack.
5th Step: Pop
def pop(self):
if not self.is_empty():
node_to_remove = self.top_node
self.top_node = node_to_remove.get_next_node()
self.size -= 1
return node_to_remove.get_value()
print("Stack empty!")
To pop or remove the head node in the stack, first we have to make sure that the stack is not empty. Write an if statement with not self.is_empty()
. If the stack is not empty, assign the top node in the stack to node_to_remove
variable. Next, set the top node, self.top_node
to become the second node in the stack, via .get_next_node()
. Make sure to decrease the self.size
by 1.
Done
- Congratulations, now you know how to write stacks data structure in Python.
- To get the full codes, click the link below:
- Github