Data Structure & Algorithms: Stack

Let's add some bowls in an empty glass.

Adding one....

Adding one again...

Adding one more..

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)

So, we will remove in this way

So, using the linked List, we are going to

pop an item

also can prepend

Our stack is going to look like this

Constructor
First create a node

Creating the first node

Setting top & bottom like this:

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

So, overall the constructor will look like this:

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()

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

case 2:
Adding node to an old stack.

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()

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

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

then

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()