Data Structure and Algorithm Implementation In Python: Stack

Not comparing with other's But there are nice and great tutorial on data structure and algorithm implementation in python. But in this series of blog we will be more focused on academic requirement and algorithm based implementation. So Alert!! there will be some cheesy theory on related topics.

In these series of blogs we will try to cover some examples of data structures with it's algorithm, theory and implementation in python.

We will dive into the following topics

• Stack
• Queue
• Linked List (singly, doubly, circular)
• Hash Table
• Heap Data Structure
  
• Binary Tree

After one or may be two topics covered we will switch our session and continue with another post.

Why one should learn data structure and algorithm?

The very first answer is it improves your problem solving skill. Learning Data structure and algorithm shows you how the coding follows algorithm. whenever you develop a program you have to handle various data and data structure storage format to those data and organizing all data items. So when you learn varieties of data structures then you can determine where to use proper data structure so that your code can be optimized. Data structure will help you to manage storage and to write effective code. This is why data structure is widely preferred and yeah the very frequently asked questions in various top companies interview is from data structure. They will ask you to write effective code that will solve problem faster choosing best data structure and algorithm. For your reference, watch google interview in YouTube.

What is Data Structure?

Whenever you try to develop a program with a given algorithm, you need appropriate data structure because you gonna handle different types of data through out the program. So here comes the importance of data structure. Data structure is the way of organizing all data items, providing storage format and establishing relationship among data items so that they can be used effectively. Data structure can be consider as a building block of program therefore from above idea we can say that given algorithm and the associated data structure forms a program.

On the basis of derivation or origination of data structure it can of two type.

1. Primitive Data structure: These are the basic data structure that is provided prior in the programming language. i.e they directly operate in machine instruction level. For example: integers, float, char etc.
2. Non-primitive data structure: These data structures are derived from primitive data structure and are complex structure to provide special format to different or same data items. These kind of data structure emphasizes relationship of data for a particular user defined format of storing those data. Lists, Stack, Queue are examples of non primitive data structure.

If we categorize on the basis of this and on the basis of that, the type of data structure becomes more and more like one type of data structure is static data structure which is such type of data structure whose capacity is fixed while creating it and another type is dynamic data structure whose capacity is variable and blah on the basis of blah and blahh.

For different classification, lets see this figure

One thing you might notice while studying data structure is ADT. The very 'Abstract Data Type', and let me make you clear. If you see that 'this' data structure is ADT then you should get that the particular data structure have some theoretical set of specification of a data set and the set of operations that can be performed on the data within a set. OHhh Confusing?

A data structure is termed abstract when it is independent of various concrete implementation. Still Confusing?

If your operations on data structure don't care about the type of data used it's called abstract data structure. For example: stack data structure have operations like push(), pop(), add(), delete() not caring about what type of data you push pop or delete. Your technique of implementing those operations? we don't care about that but it should work on the basis specified theoretical set of specification and result should be efficient. 

Formally defining, An abstract data type is a data type whose representation is hidden from and of no concern to application code. The behavior is defined by a set of values and a set of operations. ADT only mentions what operations are to be performed but not how those operations will be implemented. You can use your way of implementation. Just like we will be using python list to implement stack and you can use array to implement that also.

Too much chubby cheesy theory for introduction of data structure. Let's dive into Stack.

Stack

(Source Code)Direct... Last in first out (LIFO) Discipline. i.e. A stack is an ordered collection of items into which insertion and deletion both done from the top of the stack.

Operations done in Stack:

PUSH operation: To push or insert elements in stack. Adding element or data to stack. The pushed item goes at the top of the stack.

POP operation: POP means to pop out or delete or remove a item from stack. We remove that item which is in the top of the stack (The recent one added). 

These operations are basic or you can say primitive operations for stack. Other operations are also used to check if stack is full, empty, to display size or number of elements in the stack.

We will be using following operations:

• push(item): This function will push an item at the top of the stack
• pop(): This function will remove the top of the stack and returns the item removed.
• isEmpty(): This method will check if the stack is empty or not and return true if stack is empty, false otherwise.
• top(): Will return the value at the top of the stack. If there is no item left in the stack we will raise an error.
• noOfElement(): This method will return the size of the stack. The number of elements currently in the stack.

So the above is basic outline we will use to implement our stack in python using List and we will be sticking with the following algorithm for stack.

To initialize a stack

1. Setup a list to hold items in the stack
2. Set variable top = -1 to denote top of the stack

The top is set to -1 because when you insert an item to the stack then top is incremented by 1 and it's value will be 0. That means now top will point to 0th index of the list and you know what I mean.

To push item in the stack

1. Append the item in the stack using inbuilt method append for list
2. increment top by one i.e. top = top + 1

To pop item from the stack

since we pop that item which is in the top of the stack so the element at the value of variable 'top' indicating the position of the element in the top of the stack will be removed

1. Check if the stack is empty or not. if empty stack raise an error
2. decrement the value of top by one i.e. top = top - 1
   
3. Use inbuilt pop function to remove an item from the list

To display item at the top of the stack

1. Check if the stack is empty or not, if empty then raise an empty stack error
2. Return stack list's top index value. list[top]

To display number of items in the stack

1. return length of the list using inbuilt len method in list. len(list)
   

Now without waiting lets code the above algorithm. Please notice those comments in the code:

class EmptyStackError(Exception):
    #use to throw custom error when stack is empty
    pass

class Stack:
    
    def __init__(self):
        
        self.list = []         #Hold items in the stack.
        self._top = -1          #Denotes the top of the stack

    def isEmpty(self):
        
        return self._top == -1 #returns True if top is equal to -1

    def push(self, item):
        
        self.list.append(item)
        self._top += 1 #Just like in the algorithm
        
    def top(self):
        
        if self.isEmpty():
            raise EmptyStackError("Stack is Empty: Trying to peek into an empty stack")

        return self.list[self._top]    

    def pop(self):
        
        if self.isEmpty():
            raise EmptyStackError("Stack is Empty, stack underflow")

        self._top -= 1
        return self.list.pop()

    
    def numberOfElement(self):
        
        return self._top + 1 #Just like in the algorithm

Now lets make a instance of the class Stack and play with it's methods

s = Stack()
# initial push (without user input)
s.push("item1")
s.push("item2")
s.push(3)
s.push(4)

print(s.numberOfElement())
print(s.list)
print(s.top())

# push with user input 
item = input("Enter an item to push into stack")
s.push(item)

print(s.list)
# pop operation
s.pop()
print(s.list) # notice the output before and after pop. The new one inserted i.e. 'gagan' should be pop out first

You just code your very first Stack. Now let's move on to Queue in another Post.

Next ->

References:

• Carnegie Mellon University: Stacks and Queue
• Data Structure Using C by A. K. Sharma
• Packt: Data Sturctures and Algorithms

Resources:

• Source Code