What is a Stack? A is a data structure in which items are added and removed from the same point. It is kind of a one way storage system. It is also known as data structure, which simply means that the item added last will be removed at first. stack Last In First Out People often address it like a , we add plates from the top and we remove plates from the top. If we need the bottom most plate we'd have to remove all the plates above it. pile of plates 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. Now something about linked list and our implementation of stack :) Linked list is a data structure made up of small nodes each of which can store a and an to the next such node. Apart from these nodes, the main node in our implementation is the 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. data item address top The following is a simple stack: 4 <- 5 <- 6 <-7 (top) If we add an element, let’s take , then our stack will look like: 8 4 <- 5 <- 6 <- 7 <-8 (top) Adding an element to a stack is called a operation. Now, if we wish to remove an element (i.e. it is always going to be the topmost element), then our stack will look like: Push 4 <- 5 <- 6 <-7 (top) has been removed from the stack. Removal is known as a . 8 Pop Let's code it out! 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, now let’s implement the object which is going to chain up the nodes into a stack and provide us with the 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 = '') emp = temp.next # renews temp node print() Let's test our stack: stack = Stack() stack.push(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 using linked list. Let’s Revisit We implemented the stack data structure in Python using linked list and OOP (object oriented programming) concepts. We used the following approach while doing so: We devised an object which stores a value and an address to another node. node We created another object which would enable use to perform operations on our node object. The second object we created enabled us to insert/push, remove/pop and traverse the stack. The key note while implementing a stack data structure using linked list is to keep track of the node or else we might create nodes that aren’t interlinked but segregated. top I hope I was able to deliver quality with this brief article.
