Data Structure & Algorithms: Stack
Tags: dsalgo
Published: 2022-05-24 10:01:54

Let's add some bowls in an empty glass.


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/p77yxw76d4lfaaxx7vze.png)
Adding one.... 
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/b2tmp2254vu58t1lf6sf.png)
Adding one again...

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/3fts43ypg2c61miin7t9.png)
Adding one more..

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/n2tgxaf5m9a3pur4f8mg.png)
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](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/e09zka5hha2naor0o2r7.png)
So, we will remove in this way

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/euit3gv0pnv1cxj0lozm.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rnrwowgxvshs2915up1e.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/1wqw95fm5xktgfjfrqt5.png)

So, using the linked List, we are going to 
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yk4fcuxzpcdptgyl5tsq.png)
pop an item
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/njlzg5ya4qavsz8dxvq9.png)
also can prepend
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/yk4fcuxzpcdptgyl5tsq.png)

Our stack is going to look like this
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/p945lbxr0xcos4qjofvh.png)

**_Constructor_**
First create a node

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/kjf1a34sdrjqvnowgkck.png)
 Creating the first node

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/737krr757as9fs4ntdak.png)
Setting top & bottom like this:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/gbjgff1wo9iycrlucxuc.png)
Although we are not going to care about the bottom and thus removing the bottom:

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mhhrt9kh6v96pro94awr.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rssv6watdrjnpfs8z3er.png)

So, overall the constructor will look like this:
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/35veu0b5rft6sg1w4bc1.png)

 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
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/mjzs2vdp4slb5qf7xe2o.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/7xoas278albiiokomf3t.png)
case 2:
Adding node to an old stack.

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/uo9rohn1mx5mkkabtzbn.png)


![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/l5c5348qyqdq2u0hdrgr.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/rkwi9hmkxog3yabhpw3a.png)

 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.
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/o7aegbiciiw3jddkanyw.png)

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

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/4pwfu5yle0nuk1tuv2nm.png)
then
![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/znpdk0fgiwa6f4z0kbnb.png)

![Image description](https://dev-to-uploads.s3.amazonaws.com/uploads/articles/v7iuqhthhmx2wa451er7.png)

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

```

<img src="https://c.tenor.com/Tvd3VKwtse0AAAAC/cat-cute.gif">