19
Implementing Stack in Python
A stack is a data structure in which items are added and removed from the same point. It's kind of a one way storage system. Also known as Last In First Out data-structure. Which simply means that the item added at the last will be removed at first.
People often address to it like a pile of plates...we add plates at the top and we remove plates from the top.If we need the last plate we'd have to remove all the plates above it.
So, stack is kind of a single entrance cum exit hiding place in which the first person who goes in is the last to come out and the last person who goes in is the first to come out.
Stack is a data structure made up of small nodes that each can store a data item and an address to the next such item.
Apart from these nodes,the main node is the top node which is just like all other nodes but also acts as a gateway for addition and deletion of elements and therefore our program must keep track of this node specifically.
The following is a simple stack:
4<-5<-6<-7(top)
if we add an element...say 8
then our stack will look like:
4<-5<-6<-7<-8(top)
Adding an element to a stack is called a push operation.
Now, if we wish to remove an element (i.e. it is always going to be the topmost element) our stack will look like:
4<-5<-6<-7(top)
8
has been removed from the stack.Removal is known as a pop.
Firstly, we are going to create the node object that will form our stack:
class Node:
'''
This class will represent a unit node of the stack
'''
def __init__(self,value): # the initializer is going to take a value which will be stored in the node
self.value = value
self.next = None # this stores the address for the next such node and it is set to none cause this will be assigned by the stack class
That's it, Let's now implement the object which is going to chain up the nodes into a stack and provide us with operations for the stack:
class Stack:
'''
This class will use the node objects to create a node
'''
def __init__(self,value = None): # value is set to none so that we can initialize our stack with or without a value
self.top = None # initially the top points to None
if(value): # the following code will run only if the value has been passed
self.push(value) # this calls the push method which we will define in a while
def push(self,value): # takes the value to be inserted as an argument
node = Node(value) # creates a node object
if(self.top == None): # checks if the top exists already or not, if not run's the following code
self.top = node
else:
node.next = self.top # assigns the address of top to the next variable of the node object
self.top = node # top now points to the new node
def pop(self):
if(self.top == None): # checks if stack is empty or not
return 'Empty Stack..!'
else:
node = self.top # assigning the node that top holds to a new node
self.top = node.next # setting the node next to top as the new top
node.next = None # erasing the address of the new top from the old one
value = node.value # getting the data item of the old top
del node # deletes the node object
return f'Popped {value}'
def traverse(self): # this method just prints all the values in the stack
if(self.top == None): # checks if the stack is empty
print('Empty..!')
else:
temp = self.top # referencing the top with a temporary value
while(temp != None): # this loop will run unless the temp variable equals None
print(f'{temp.value}->',end = '')
temp = temp.next # renews temp node
print()
Let's test our stack:
stack = Stack(9)
stack.push(8)
stack.push(10)
stack.traverse()
print(stack.pop())
print(stack.pop())
print(stack.pop())
print(stack.pop())
stack.push(8)
stack.traverse()
Outputs:
10->8->9->
Popped 10
Popped 8
Popped 9
Empty Stack..!
8->
That's it..! we successfully implemented the stack data structure...Will be back with another one soon...till then...Happy Coding :)
19