Let's Learn about Stacks

Vinay — Sat, 19 Nov 2022 20:21:22 +0000

What will you learn?

a) What is stack data structure.
b) Operations we can do on them.
c) How to implement them in python.

First of all, stacks are very important data structure used in many algorithms while solving many problems.
Also, they are the most basic and easy to learn and after some practice you would become great at problems having stacks as their core solution.

"Never underestimate the power of simple things, for example Stacks" - by ME

What is Stack?

The cover image of this blog is a classic example when we are talking about stacks. Imagine that every chair has a number written on it's seat and I asked you to tell me what is the number on the 3rd chair from the top.
Also the chairs are a bit heavy and you can only remove them one by one.
So you'd be required to remove the top two chairs and then you can tell me what's the number written.

If you understand the concept above then you already know 50% about stacks.

Now for the technical definition, A stack follows the concept of LIFO which means Last In First Out i.e. the element that goes in the stack Last comes out first.
You can also say that it follows FILO (First In Last Out) which both means basically the same thing.

Now your stack knowledge bumps upto 60%.

Operations performed on Stacks

There are very few operations that we can do on stacks which makes it simple yet effective.
The main ones among them are:

push()

This function simply means adding a new element onto the stack.
Basically you take a chair with the number written on it and you put it on the chair stack in front of you.

If you haven't added any element in the stack already then you don't have to worry you can simple use this operation to add elements.

Note: In some programming languages there is a limit to how many element you can add to the stack but in python we don't need to worry about this. However if you want to imitate this functionality in python you can easily do that.

pop()

This function helps you to remove the latest element from the stack.
So now you can remove the top most chair from your chair stack.
Remember that the chairs are heavy and you can only remove one at a time. Similarly, pop() function removes element from the top one at a time.

Now, if your stack is empty then pop() function gives an error stating that you cannot remove from the empty stack. Imagine if I told you to remove a chair from the stack when there is no chair, you would look at me like I am stupid.

top()

This function is used when you want to see what's the latest element in the stack is.
So in chair context this tells you what's the number written on the top most chair.

As similar to the pop() function you can't use it on an empty stack.

With this your stack knowledge is now 80%.

Implementation in Python.

There are many ways to implement stack in python. But I will discuss only two here.

The first one is very simple and uses simple lists methods already present in python.

The second one uses classes and so if you know about classes in python then you can go ahead and read this implementation otherwise skip this, it's no big deal because no one uses classes to implement stack in python.

Using python lists

# Let's initialise an empty list to start
stack = []

# Implement push()
# in python you can add elements using append method 
# which adds element at the end of the stack

stack.append(3)
stack.append(10)
stack.append(4)

# after this our stack is: [3, 4, 10]

# implement pop()
# in python you can simply use pop() method
# this will remove the last element from the list
element1 = stack.pop()
element2 = stack.pop()

# after these lines:
# element1 will have 10 as it's value
# because when pop was called 10 was the latest value
# Similarly element2 will have 4
# and our stack will be: [3]

# implement top()
# we can simply access the last element in python
# by using negative indexing which gives elements from the end
last = stack[-1]

# last would contain 3 as it's value
# stack would remain same: [3]

Note: I would encourage everybody reading this to go in any code editor of your choice and play around with this knowledge, try shuffling this operations and breaking the code, produce errors and see if you understand every bit.

Implementation of stack using Classes

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

    def push(self, val):
        self.stack.append(val)

    def pop(self):
        if self.stack:
            return self.stack.pop()
        else:
            print("Cannot pop() from empty stack")

    def top(self):
        if self.stack:
            return self.stack[-1]
        else:
            print("Cannot use top() on empty stack")

    def __repr__(self):
        return str(self.stack)

stack = Stack()

print(stack)

stack.push(10)
stack.push(4)
print(stack)

a = stack.pop()
print(a)
b = stack.pop()
print(b)
c = stack.top()
print(c)

print(stack)

After this Section your understanding of stack is 95%

Time for practice

Before moving on, try these 3 problems it would not take much time:

Now your understanding of stack is 99%, Keep it up...
Thanks for reading, see you in next article.

Forem: Vinay