Introduction

• Stack is a linear data structure which follows principle of Last-In-First-Out(LIFO).

• Stack is also a dynamic data structure which do not have any fixed size.

• Stacks do not consume fixed amount of memory size.

When we insert or push new item inside stack, it is always inserted at the top of the stack. When we remove or pop item from the stack, most recently added item is removed, which is commonly called as top item.

The two main operations in stack are push and pop and other supportive operations are isEmpty, peek, size and getStack.

Implementation

First of all we need to create the class for Stack and initialize an list in constructor to store stack items.

class Stack:
    def __init__(self) :
        self.items = []

when instance of class is created, all items will be stored in items list.

For implementing push function, we just need to append new item at the end of items list. Hence, the top item in the stack will always be last element of the items list. We can do this by using append method of list.

 def push(self,item):
        self.items.append(item)

We can get size of stack using len method of list which returns length of list.

def size(self):
        return len(self.items)

isEmpty method is used to check whether stack has items in it or not. If it has items,then return False, Otherwise return True. We can simply implement this method using size method implemented above by checking if size of stack is 0 or not.

  def isEmpty(self):
        return self.size() == 0

For implementing pop function, we can use list pop method to remove last added item from the stack. We also need to check whether stack is empty or not before removing item from stack.

If stack is empty, then we can handle this condition by using exception. We can create custom Exception for this.

class EmptyStack(Exception):
     def __str__(self) :
        return "Stack is Empty"

if stack is not empty then we pop the item from stack . Otherwise, raise EmptyStack Excpetion.

def pop(self):
        if self.isEmpty():
             raise EmptyStack()
        return self.items.pop()

For implementation of peek , we want the top item in stack i.e. last item added inside the it, which we can get by using index of list as -1. We also need to check whether stack is empty or not similar to what we used in pop function.

    def peek(self):
        if self.isEmpty():
            raise EmptyStack()
        return self.items[-1]

We can get all items presents in the stack by using getStack function which simply returns the items list.

def getStack(self):
        return self.items

Whole code of stack implementation will be

class EmptyStack(Exception):
     def __str__(self) :
        return "Stack is Empty"

class Stack:
    def __init__(self) :
        self.items = []

    def push(self,item):
        self.items.append(item)

    def size(self):
        return len(self.items)

    def isEmpty(self):
        return self.size() == 0

    def pop(self):
        if self.isEmpty():
             raise EmptyStack()
        return self.items.pop()

    def peek(self):
        if self.isEmpty():
            raise EmptyStack()
        return self.items[-1]

   def getStack(self):
        return self.items

Time and Space Complexity

• The time complexity of all operations in stack is o(1) i.e. constant time.

• The space complexity of all operation is o(n) where n is number of items in stack

Final Words

We have covered all the functions used in implementation of stack.

I hope it was a great read for you. If you got any questions or doubts, feel free to ping me.

I'd love to connect with you at Twitter | Instagram | LinkedIn .

If you have any feedback please share it in the comment below. Also, if you find it helpful, please like and hit the follow button.