DEV Community

Shahriyar Al Mustakim Mitul
Shahriyar Al Mustakim Mitul

Posted on

Data Structure & Algorithms: Stack

Let's add some bowls in an empty glass.

Image description
Adding one....
Image description
Adding one again...

Image description
Adding one more..

Image description
Now, the thing is that we can take one bowl outside and guess which bowl can we take outside first.

Is it the 3rd one? 2nd one ? or 1st one?

Yes, it is the 3rd one and it follows LIFO (Last In First Out)

Image description
So, we will remove in this way

Image description

Image description

Image description

So, using the linked List, we are going to
Image description
pop an item
Image description
also can prepend
Image description

Our stack is going to look like this
Image description

Constructor
First create a node

Image description
Creating the first node

Image description
Setting top & bottom like this:

Image description
Although we are not going to care about the bottom and thus removing the bottom:

Image description

Image description

So, overall the constructor will look like this:
Image description

Code for that:

#Node class : Creates node
class Node:
    def __init__(self, value):
        self.value = value
        self.next = None

#Creates a stack class
class Stack:
    def __init__(self, value):
        #creates a node by calling the Node class
        new_node = Node(value)
        #pointing the top to that node
        self.top = new_node
        #adding the length to 1
        self.height = 1
    #Prints the stack untill it finds None
    def print_stack(self):
        temp = self.top
        while temp is not None:
            print(temp.value)
            temp = temp.next

#Creating a stack with node 4
my_stack = Stack(4)

#Printing the stack
my_stack.print_stack()

Enter fullscreen mode Exit fullscreen mode

Push
Case 1:
When the stack is empty, we will add the node and assign it to the top also
Image description

Image description
case 2:
Adding node to an old stack.

Image description

Image description

Image description

Code for this:

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class Stack:
    def __init__(self, value):
        new_node = Node(value)
        self.top = new_node
        self.height = 1

    def print_stack(self):
        temp = self.top
        while temp is not None:
            print(temp.value)
            temp = temp.next
    #push method
    def push(self, value):
        new_node = Node(value)
        #When there are no nodes in the stack
        if self.height == 0:
            self.top = new_node
        #When there are nodes in the stack   
        else:
            new_node.next = self.top
            self.top = new_node
        self.height += 1

#Creates a stack of 2
my_stack = Stack(2)

#pushing 1 to the stack
my_stack.push(1)

my_stack.print_stack()

Enter fullscreen mode Exit fullscreen mode

Pop
Case: 1
when we have nothing in stack, we are not going to return anything.
Image description

Case 2:
When we have a stack and we are going to return the last value entered.
First setting temp to it.

Image description
then
Image description

Image description

class Node:
    def __init__(self, value):
        self.value = value
        self.next = None


class Stack:
    def __init__(self, value):
        new_node = Node(value)
        self.top = new_node
        self.height = 1

    def print_stack(self):
        temp = self.top
        while temp is not None:
            print(temp.value)
            temp = temp.next

    def push(self, value):
        new_node = Node(value)
        if self.height == 0:
            self.top = new_node
        else:
            new_node.next = self.top
            self.top = new_node
        self.height += 1
        return True

    def pop(self):
        #when we have no nodes in the stack
        if self.height == 0:
            return None
        #when we have nodes in the stack
        temp = self.top
        self.top = self.top.next
        temp.next = None
        self.height -= 1
        return temp

#A stack of nodes 7,23,3,11

my_stack = Stack(7)
my_stack.push(23)
my_stack.push(3)
my_stack.push(11)

#poping a node from the stack. Note: pop returns the last value intered into the stack[last in first out]
print(my_stack.pop(), '\n')

my_stack.print_stack()

Enter fullscreen mode Exit fullscreen mode

Top comments (0)