Implement Stack in Python

Stack is a data structure which follows last in first out (LIFO) order for accessing the elements. In a stack, we can only access the most recently added element. Stacks have many uses in applications like expression handling, backtracking and function calls. In this article, we will try to implement stack data structure with linked lists in python.

Implement stack in Python using linked list

A linked list is a linear data structure in which each data object points to one another. To implement a stack with linked list, we will have to perform insertion and deletion and deletion of elements from a linked list such that it takes a constant amount of time. This is only possible when we insert as well as delete the elements at the start of the linked list.

To implement a stack with linked list in python, we will first define a node object which will have the current element, will point to the node which was inserted just before it using a reference next. The Node can be implemented as follows in python.

class Node:
    def __init__(self,data,size):
        self.data=data
        self.next=None

When we implement a stack with linked list, it will have an element named top which will refer to the most recent element inserted in the linked list. All other  elements can be accessed with the help of that.We can implement an empty stack in python with top initialized to None and stackSize initialized to 0 as follows .

class Stack:
    def __init__(self):
        self.top=None
        self.stackSize=0

Implement Push operation in stack in Python

When we insert an element into the stack, the operation is called push operation. To implement push operation in stack with the help of linked list, for every insertion we will add the element to be inserted at the start of the linked list . In this way, the most recent element will always be at the start of the linked list. Then we will point the top element of the stack to the start of the linked list and increment the stackSize by 1. The push operation can be implemented using linked lists in python as follows.

 def push(self,data):
        temp=Node(data)
        if self.top is None:
            self.top=temp
            self.stackSize= self.stackSize+1
        else:
            temp.next=self.top
            self.top=temp
            self.stackSize=self.stackSize+1

Implement Pop operation in stack in Python

When we take out an element from the stack, the operation is said to be a pop operation. The element to be taken out from stack is the most recently added element to the stack. As we know that during a push operation, we add the most recent element to the start of the linked list which is pointed by the top of stack hence we will remove the element pointed by top and will point top to the next recent element. Before performing pop operation, we will check if stack is empty. If the stack is empty i.e. top points to None, we will raise an exception using python try except with a message that stack is empty. We can implement the pop operation as follows.

 def pop(self):
        try:
            if self.top == None:
                raise Exception("Stack is Empty")
            else:
                temp=self.top
                self.top=self.top.next
                tempdata=temp.data
                self.stackSize= self.stackSize-1
                del temp
                return tempdata
        except Exception as e:
            print(str(e))

How to access topmost element of stack

As the topmost element of the stack is being referenced by top, we just have to return the data in the node pointed by top. It can be implemented as follows.

def top_element(self):
        try:
            if self.top == None:
                raise Exception("Stack is Empty")
            else:
                return self.top.data
        except Exception as e:
            print(str(e))

Get the size of the stack

As we keep the current size of stack in stackSize variable, we just have to return the value in the stackSize variable top. This can be done as follows.

def size(self):
        return self.stackSize

Check if the stack is empty

The element top refers to the most recent element in the stack. If there is no element in the stack, top will point to None. Thus, to check if the stack is empty, we just have to check if top points to None or stackSize variable has a value 0. We can implement isEmpty() method to check if the stack is empty as follows.

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

The full working code to implement stack using linked list in python is as follows.

#!/usr/bin/env python3
# -*- coding: utf-8 -*-
"""
Created on Sun Apr 25 00:28:19 2021

@author: aditya1117
"""

class Node:
    def __init__(self,data):
        self.data=data
        self.next=None
class Stack:
    def __init__(self):
        self.top=None
        self.stackSize=0
    def push(self,data):
        temp=Node(data)
        if self.top is None:
            self.top=temp
            self.stackSize= self.stackSize+1
        else:
            temp.next=self.top
            self.top=temp
            self.stackSize=self.stackSize+1
    def pop(self):
        try:
            if self.top == None:
                raise Exception("Stack is Empty")
            else:
                temp=self.top
                self.top=self.top.next
                tempdata=temp.data
                self.stackSize= self.stackSize-1
                del temp
                return tempdata
        except Exception as e:
            print(str(e))
    def isEmpty(self):
        if self.stackSize==0:
            return True
        else:
            return False
    def size(self):
        return self.stackSize
    def top_element(self):
        try:
            if self.top == None:
                raise Exception("Stack is Empty")
            else:
                return self.top.data
        except Exception as e:
            print(str(e))
s=Stack()
s.push(1)
print(s.size())

s.push(2)
print(s.size())

print(s.pop())
print(s.size())
print(s.pop())
print(s.stackSize)

print(s.top_element())
print(s.isEmpty())

Output:

1
2
2
1
1
0
Stack is Empty
None
True

Conclusion

In this article, we have implemented stack and all its operations using linked list in python. To gain more insight into it and understand how stack is different from inbuilt data structures like python dictionary, list and set , copy the full code given in the above example and experiment with the operations in it. Stay tuned for more informative articles.