Beginners Guide to Stacks in Python.

Stacks are one of the most basic data structures that allows us to store and retrieve data sequentially.

Features of Stacks:

It is a linear data structure

The data is organized linearly and only one data can be accessed at a time.

It is a abstract data type.

The abstract data type is a special kind of data type whose behaviour is defined by a set of value and set of operations.

Stacks follow LIFO (Last in first out)

Consider a stack of chairs placed one on top of another.We cant take out the middle one at once.We have to take out the topmost one and then sequentially come to the one chair that you wanna remove.Stacks work similarly and the last element inserted will be the first element thats going out.

Operations in stack:

You can only access stack from one end so both insertion and removal/deletion occurs from the same end.

• Insertion​: This is known as a ​push()​ operation.
• Deletion/Removal​: This is known as a ​pop​() operation.

Main stack operations:

• ​Push (int data): Insert data onto the stack.
• ​ int Pop(): Removes and returns the last inserted element from the stack. Auxiliary stack operations.

Other Stack Operations:

• int Top(): Returns the last inserted element without removing it.
• ​int Size(): Returns the number of elements stored in the stack. ​
• int IsEmptyStack(): Indicates whether any elements are stored in the stack or not. ​
• int IsFullStack(): Indicates whether the stack is full or not.

Exceptions:

In an empty array if you call pop() then it throws an exception called stack underflow.

Trying to push() an element on a full stack throws an exception called stack overflow.

Implementation Of Stacks.

— Using simple arrays

We use a simple array for stack implementation and also we use a top variable to keep track of the top element.

We add elements from the left to right.

#Constructor  
def __init__(self):  
   self.stack = list()  
   self.maxSize = 8     #Maximum size of the list  
   self.top = 0     #Top element 
 
#Adds element to the Stack  
def push(self,data):  
   if self.top>=self.maxSize: #Stack Overflow  
      return ("Stack Full!")  
   self.stack[top]= data    #Assign the new element at 'top'  
   self.top += 1     #Increment top  return True
  
#Removes element from the stack  
def pop(self):  
   if self.top<=0:
      return("Stack is empty")
   item = self.stack[top-1]
   self.top -= 1
   return item
#size of the stack 
def size(self):
   return self.top

Limitations of this approach:

In python the arrays are resizable but it is still expensive on the storage if we have to add more elements to the stack when its full.

In other programming language like Java and C++ the size of the array is fixed.

— Using linked list

We first create a node class which is used everytime a new element is created during push() operation.

#creating a node class
class Node :
def __init__(self, data) :
        self.data = data
        self.next = None
class Stack :
#Define data members and __init__()
    def __init__(self):
        self.__head=None
        self.__count=0
def getSize(self) :
        #Implement the getSize() function
        return self.__count
def isEmpty(self) :
        #Implement the isEmpty() function
        return self.getSize()==0
def push(self, data) :
        #Implement the push(element) function
        newNode=Node(data)
        newNode.next=self.__head
        self.__head=newNode
        self.__count+=1
def pop(self) :
        #Implement the pop() function
        if self.__head is None:
            return -1
        
        data=self.__head.data
        self.__head=self.__head.next
        self.__count-=1
        return data
def top(self) :
        #Implement the top() function
        if self.__head is None:
            return -1
        data=self.__head.data
        return data

Well be discussing about Queues in the next blog.

Check out my blog if you wanna learn more about python and learn machine learning in the next 100 days.