Stack in Python

In python, there are inbuilt data structures like list,tuple, set and dictionary but we may need some additional functionalities in python programs. For example, If we need a last in first out (LIFO) functionality in our program then none of the inbuilt data structures provide that functionality. We can use stack to implement last in first out functionality in python. In this article, we will study the concept behind stack data structure and implement it in python.

What is a stack?

A stack is a linear data structure in which we can only access or remove the element which was added last to it. In real life, we can take the example of a stack of plates where we can only take out the uppermost plate because it was added last. We can perform the following operations on a stack data structure in python.

Insert an element(Push an element)
Remove an element (Pop an element)
Check if the stack is empty
Check the topmost element in the stack
Check the size of the stack

In the following subsections, we will implement stack and all its and will implement them in python.

How to implement stack in python?

In this tutorial, we will define a class named Stack and will implement the Stack using python lists. In the Stack class, we will have a list for containing the data added to the Stack and a variable for storing the size of the Stack. All the operations like push, pop, checking the size of the stack, checking the topmost element of stack and checking the stack if it is empty will be executed in constant time and thus will have O(1) time complexity. The Stack class will be defined as follows.The stackList is initialized as an empty list and stackSize is initialized to 0.

class Stack:
    def __init__(self):
        self.stackList=[]
        self.stackSize=0

Push items to a stack in python

To insert an item into the stack i.e. to push an element into the stack, we will simply append the element in the list and then we will increment the stackSize variable by 1. To implement the operation, we define a method which takes the element as an argument and appends the element to the list in the stack. Then it increments the stackSize variable. Following is the implementation for the push() method.

def push(self,item):
        self.stackList.append(item)
        self.stackSize+=1

Pop items from a stack in python

To remove an item from the stack i.e. to pop an element from the stack, we have to remove the element from the stack which was added last to it. As we append the element to the list in stack while push operation, the last element in the list will be the most recent element and will be removed from the stack. So we simply delete the last element from the list.

To implement the pop operation, we will implement the pop() method which first checks if the number of elements in the stack is greater than 0. If yes, then it will remove the last element from the list and decrease the stackSize by 1. If the number of elements in stack is 0, it will show an error message saying that the list is empty. For this task, we will use exception handling using python try except to raise an exception when the size of stack is 0. The pop() method can be implemented as follows.

def pop(self):
        try:
            if self.stackSize==0:
                raise Exception("Stack is Empty, returning None")
            temp=self.stackList.pop()
            self.stackSize-=1
            return temp
        except Exception as e:
            print(str(e))

Check size of the stack

To check the size of the stack, we simply have to check the value of the stackSize variable. For this operation, we will implement the size() method which returns the value of stackSize variable as follows.

def size(self):
        return self.stackSize

Check if stack is empty

To check if the stack has no elements i.e it is empty, we will have to check if the stackSize variable is 0 or not. For this operation, we will implement the isEmpty() method which returns True if the stackSize variable is 0 and returns false otherwise. Following is the implementation for isEmpty() method.

def isEmpty(self):
        if self.stackSize==0:
            return True
        else:
            return False

Check topmost element of an stack

The topmost element of the stack will be the element most recently added to it. To check the topmost element of the stack, we just have to return the last element in the list in the stack. For this operation, we will implement the top() method which first checks if the stack is empty i.e. stackSize is 0 or not, if yes then it will print a message saying that the stack is empty. Otherwise it will return the last element of the list. This can be implemented as follows.

def top(self):
        try:
            if self.stackSize==0:
                raise Exception("Stack is Empty, returning None")
            return self.stackList[-1]
        except Exception as e:
            print(str(e))

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Fri Apr 23 19:38:55 2021

@author: aditya1117
"""

class Stack:
    def __init__(self):
        self.stackList=[]
        self.stackSize=0
    def push(self,item):
        self.stackList.append(item)
        self.stackSize+=1
    def pop(self):
        try:
            if self.stackSize==0:
                raise Exception("Stack is Empty, returning None")
            temp=self.stackList.pop()
            self.stackSize-=1
            return temp
        except Exception as e:
            print(str(e))
    def size(self):
        return self.stackSize
    def isEmpty(self):
        if self.stackSize==0:
            return True
        else:
            return False
    def top(self):
        try:
            if self.stackSize==0:
                raise Exception("Stack is Empty, returning None")
            return self.stackList[-1]
        except Exception as e:
            print(str(e))
            
#Execution
s=Stack()
#push element
s.push(1)
#push element
s.push(2)
#push element
s.push(3)
print("popped element is:")
print(s.pop())
#push an element
s.push(4)
print("topmost element is:")
print(s.top())

Output:

popped element is:
3
topmost element is:
4

Conclusion

In this article, we have studied and implemented stack data structure in python. We have seen the operation for the stack and you may find it very different from python dictionary, list, set e.t.c. Stacks are used extensively in real world applications like expression handling, backtracking, function calls and many other operations and you should have a working knowledge about it. Stay tuned for more informative articles.