Back

Data Structures with Python: Stacks

author-image

By Amir

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.

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