“My experience learning stacks in data structure”

Greetings to all my readers!

Surprisingly ! I had completed my almost two months in Women In tech program. It was a great experience of being a part of this program. I learnt a lot of things here. Not only related to technical skills but also related to power skills as well. As a part of our weekly milestones we were given with some data structure problems. And as part of this week’s milestones we had given some data structure problems related to stacks.

Before starting with solving the problems directly, I learned about stacks. Although I had brief idea about stacks but still I learned about it a bit more. So, that I could not got confused. While learning about stacks I discovered some interesting points regarding stacks.

What is Stacks?

The stack is a collection of items that follows the last-in, first-out concept.

For the addition of new items, the stack only allows it to push the new item to the top. When it comes to removing items, it only allows us to remove the last added item, or commonly known as the top item.

The main API methods are push (add) and pop (remove). But we can also add other methods as part of the API implementation: size, top, and is_empty.

Stack Implementation

We can create a Stack class as a wrapper and use the Python list to store the stack data. This class will have the implementation of the push, pop, size, top, and is_empty methods.

The first step is to create a class definition and how we are gone store our items.

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

This is basically what we need for now. Just a class and its constructor. When the instance is created, it will have the items list to store the stack items.

For the push method, we just need to use the list append method to add new items. The new items will be placed in the last index of this items list. So the top item from the stack will always be the last item.

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

It receives the new item and appends it to the list.

The size method only counts the number of the stack items by using the len function.

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

The idea of the is_empty method is to verify if the list has or not items in it. If it has, returns False. Otherwise, True. To count the number of items in the stack, we can simply use the size method already implemented.

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

The pop method from the list data structure can also be used to pop the item from the stack. It pops the last element as it is expected for the stack. The last added item.

def pop(self):
    return self.items.pop()

But we need to handle the stack emptiness. For an empty list, the pop method raises an exception IndexError: pop from empty list. So we can create an exception class to handle this issue.

class Emptiness(Exception):
    pass

And uses it when the list is empty:

def pop(self):
    if self.is_empty():
        raise Emptiness('The Stack is empty')    return self.items.pop()

If it is empty, we raise this exception. Otherwise, we can pop the top item from the stack.

We use this same emptiness strategy for the top method:

def top(self):
    if self.is_empty():
        raise Emptiness('The Stack is empty')    return self.items[-1]

If it has at least one item, we get the top, the last added item in the stack.

Runtime and Space complexities

Now about space and runtime complexities for each method implemented.

The space is pretty simple. It’s a list, so it’s O(n) where n is the current number of items in the stack.

The runtime for each method is O(1), constant time.

Experience

My experience with stacks is though very good and interesting as well. As at many points I got confused and even stuck for a long time but after learning about stacks and getting started with stacks its very good to solve it.

THANK YOU