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
pop and other supportive operations are
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
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
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
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
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
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.
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.