3.3 Stack implementation using linked list | data structures

the topic is stack implementation using linked lists right so the prerequisite of this video is you should know about stack and link lists right we have already discussed what is stack and how to implement stack using arrays or what are the different operations on stack right in the previous videos as well as we have discussed the topic linked list all the type of linked list as well as how to perform insertion deletion traverser all the operations on linked list for those with videos you can check out the description box right so I assume that you know the what is stack and what is linked list right now we are going to implement stack using linked list see we will implement stack using linked list right so you have to follow the rule of the stack and what is that rule that is leaf or principle stack always follow what leaf or principle last in first out right that thing we have discussed in the previous video right for that video you can check out the side button so stack is what it is an ordered list or you can say it is a collection where the insertion and deletion always perform from one end only and how we are going to represent the stack the logical represent is something like this it is a container which is having one open end right this insertion is also from this end and deletion would also perform from this end and this end is known as top so the push and pop operations will be performed always from the top of the stack and what is a linked list see when I am saying a linked list it means we are discussing about singly linked list by default right so this is what a singly linked list this is a node in the linked list two parts are there one is data part one is address part this address part or link part is containing address of the next node right that is four hundred here hundred the last node is containing null because this is not pointing to any node and head pointer head is containing address of the first node so when you are going to program the linked list then what we have the information we have is what head pointer only the head pointer right not head in order this is head pointer this is what you can say head node the first right we have only the header pointer that is address of the first node fine this is what a link lists now you have to implement tag using link list so here we will store the Atty in the form of nodes as well as we have to follow the rules that is only for principle and we have discussed the push and pop operation the two fundamental operations push and pop is going to take order of one time complexity is order of one only in the form of stack so you have to take care of this thing also so now we can perform insertion and deletion from the one end all right so in linked list suppose I am taking linked list so that end can be the stale or the head you can insert and delete both from the tail and only also as well as from the head also from the starting also right so two options you have so if you insert and believe the data from the tail here from the end of the linked list then see the time complexity would be suppose this is the list and we will we want to insert another node in the list so here you are going to insert suppose I am taking that approach that from and only I can insert and here only I can delete right so now you can directly insert the data here why so because in link list only sequential access is possible so you have to traverse the list till here after that you can only insert that thing we have discussed in detail right so for that the time complexity would be order of n for inserting order of a node you can say work for this push operation order of n if there are three node in the list then you have to traverse three nodes if there are ten node in the list and after that you want to insert then you will have to traverse all the ten nodes means it depends on the number of nodes order of n second thing if you want to Bill it from the end only in that case also time complexity would be order of n so in case of purple so it would be order of n because we cannot directly delete the data from the end if you want to delete this then you will have to traverse the list till here after then you will do what you will store here is zero then this link would be broken after then after that you can free this data fine so you have to traverse still here so that also depends on the number of nodes present in the list this thing also we have discussed in detail when we were discussing the delete operation from a singly linked list right but in stab see we have discussed these push and pop operation should take order of one so obviously we are implementing step so you should follow these rules now second option is you can insert and delete from the beginning of the list right suppose you want to insert a new node here at the beginning of the list then the time complexity would be you just have to update the links means now head would point to this node and here in the next part you will store address this one and this will spawn to this one right so it is going to take order of one only you no need to traverse the list it does not depend on the number of nor present in the linked list same if you want to delete the first node suppose this is the first node this node I want to delete simply what you need to do one link you will set here head good point two here and you can simply free this node that's it this is also going to take order of one it does not depend on the number of nodes present in the list right so for implementing stack using linked list we will follow which approach we will always push and pop from the beginning or you can say from the head or a right and here we are taking head and instead basically we are taking that name top so here we will take this name as top we are not taking head we are taking top and second thing while implementing stack using linked list you need to take care is see suppose I have called first pushes push to means I want to insert two so here we will create a node because we are using linked list in the data part we will insert two and at star thing I'm taking top is equal to null that is zero or null because we are here considering link list so head rather than head we are taking top and top is equal to null so now suppose we will create a new node this says we have already discussed how to create a node and thus new node pointer is containing address of this one that is 100 suppose it is containing fine so now here what you will do here in the next part we will store this top value is initially top value 0 so here we will store a 0 after that now we have inserted we have pushed one node in the stack so top the top should point here so now top should contain hundred right so suppose top is containing hundred address of this one like this this is the stack now next suppose I am inserting five so another node will be created that is five right and suppose address is two hundred in that case this new node would contain two hundred means new node is going to point here fine so now how we will insert this data here in that case this newly created node this next part of this link part would contain address of this node this node we have inserted right so here you will store hundred from where you can get hundred because top is containing one hundred right so now see as you can see this is pointing to this node and now you will do what top is equal to new node that is top to be rude contain 200 so now pop is pointing to this node third suppose you want to insert it here I have created another node here I have eight and in that case new node would point suppose the address is 300 so a new node is containing 300 and you know dude point here now what I will do here you will store address of this node that is 200 from where I can get 200 from top so here I have 200 and this will point to this node now we will change this top top would contain 300 that is address of this node and now top is this one and this is what a stack right vertically I am writing the link so now as you can see the difference here in the link list always when you will insert a new node in that case the previous node would contain here the address of the new node but in this case the differences here I have created this new node this new node is containing address of the this previous node this is the difference fine we have changed the policy a little bit and why we have changed with this policy to implement step to follow the rules of stack right now suppose if you want to represent this stack in horizontal form then this would be the step in the form of link list as you can see see top is pointing to this node 8 this node is containing address of this node that is address of this node 200 this node is containing address of this node that is 100 fine firstly we have inserted to find after that we have inserted 5 means 5 becomes the first node and as we have discussed to implement stack to follow these rules the rules of stack we will insert always from the beginning in the linked list we will not insert from the end that we have discussed why we are following this approach because of this time complexity now when we will insert it then it would become the first node that is why it would become the first node right if you will call push again push 10 then here you will insert 10 now top would point here and this node would contain address of this node that is here 300 and top good point suppose address is 400 so in table there would be 400 so this is how you can implement stack using link list you will always insert and delete from one end and that end would be the beginning now we will write down the code for this push and pop operations see here if you write the pop it means after inserting only the 3 3 nodes these few nodes the popped item will be this one it and now top would become pointing to this one and after that you can free this node right same here suppose I have inserted only the 3 nodes top is still pointing to here and if you want to delete then always we will from the head only from the one in Nolan's insertion and deletion so when you will delete this thing - oh good point - here after that you can free this node right now we will write down the code for this push and pop operations so suppose in step I want to push three elements first is 2 then 3 then 10 I have called push 3 times right and we have passed the value whatever I want to push fine after that I will display the data after that we will call the peek function peek means it will return the topmost element from the stack without removing that element fine pop means the topmost element would be popped out from the stack fine after that again peek and after that we will display we will called all these functions fine so this is what a stack and we are using the link list that is why obviously for pushing this data to a node would be created fine so struct node we have defined a round area type for that node two parts would be there data part and one is link part pointer part or the next part as you can see fine we have taken one pointer that is top also and this top is of type struct node means type-ins here we always write the data type of that variable or that thing whose address this pointer is going to store and this pointer this top pointer is going to store address of the node proper fine right and that idea type of that node is struct node struct node we have defined this thing we have already discussed when we were discussing the linked list and initially we initialize the top is equal to null means top is not pointing to any node fine now we will define this push function so now here what you need to write here in these arguments what you need to write because I am passing value to so obviously you need some variable integer time because the data type is integer to receive this value fine that is why I am taking here int X parameter of this function void position int X fine now obviously we are going to create a node so and how to create a node that thing we have discussed many times when you are discussing link list so please check out those videos was fine here we will use what a dynamic memory allocation so no need to specify the stack size as we have discussed in Aries in Aries you have to specify the stack size in that example we have taken five so here in that case we have inserted only the five elements but here if you are using the link list means dynamic memory allocation funda we are using so no need to specify the stack size this is what the advantage of using linked list fine now and for dynamic memory allocation we will use what my log function so I guess everybody knows the meaning of this line because we have discussed many times one node has been created and using malloc function dynamic memory allocations and take says we will take how much byte we want how much byte in memory you want sizeof struct node the datatype of this this node is what struct node fine Milo code it and avoid a pointer that is the way you have to typecast this thing because in the new node pointer is what pointer to a node so here you will type cast struck no district and whatever this malloc would return it would be we will store that address into new node new note the address of this node 100 this is what how many bytes has been allocated 8 bytes for for this integer data and 4 bytes for this pointer four bytes for this pointer in 32-bit compiler in 64-bit compiler it could take 8 bytes right and in typical compilers the integer is going to take 4 bytes somewhere it is going to take two bites fine so now here you will store in the data part we will store to have you will store that thing how you can access this part we can access the structure members using the pointer only with this pointer is pointing to this node so new node arrow and that this name of this part is data is equal to X because in X we are going to receive this value to write so here we have to now now the next thing is simple rule is what here in the next part what you will store new node next here I am going to store the value whatever the value in top is equal to top right in top I have null so here we will store null fine now firstly we have inserted this data in the stack so top should point to this node right so now in top what you will store address of this node that is hundred and from where you will get this hundred see a new node I have 100 so top is equal to new that's it again suppose if you call push is equal to 3 3 will be power passed X is equal to now 3 fine again a new node would be created a new node would be created right now this new node suppose address is 200 so now in new node point that I have 200 means this is now pointing to this node right new node data is equal to X in X I have 3 now right new node next means new node next this part would contain top top is containing 100 so here hundred it means 100 is that is of this thing so this is pointing to this node right now top is equal to a new node top is equal to a new node a new node I have 200 so top is containing 200 means top would point to this node now right again if you call push is equal to 10 in X now I have 10 again a new mode would be carried suppose address is 300 so in new node after creating this this node addresses this one 3 hundreds fine new node datum means here we will store X in X I have now 10 new node next is equal to top new node next is equal to top top is containing 200 means it is pointing to this node now and now top is equal to a new node means top is pointing to this node that is here we will store 300 and this is what a stack this is what a logical representation of stock right now suppose if you call this display function it means it should display first of all 10 then 3 then 2 right because top is bonding to this node somewhere you will find out that they will display the data from here 2 3 and 10 but here we will implement this logic fine because from here only we can display so first of all 10 we let's play then three then two so now how you will display the data see see in the push operation we haven't checked for the old flow condition why so because in the staff we haven't fixed the size suppose we have fixed the size that is three so in that case we haven't we we are not able to insert forth data that is why we check no flow condition right when we were implementing stack using areas but here we haven't specified the size of the stack that is why we haven't checked the overflow condition fine now however we are going to display the data first of all I will display n then three then two where you are going to stop when it becomes zero the next part of this becomes zero so you need to take another pointer you can say m pointer fine because top is always going to point the topmost element we cannot move this top for for displaying first of all you will display this data then this then this so we have to move some pointer so here you will take another pointer that is temp pointer and initially temp would point to top right because we are going to start from here temp is equal to top it means temp is now containing whatever the top value that is three hundred so now temp is pointing to this node right here you can check for under flow condition if there is no node in the list in that case obviously we cannot print anything less than M pretty fine so here you can check if top equal to equal to null right in that case here in printf you can say let's assemble take write in else part what you will do obviously we are going to take a loop so here I am taking a while loop while temp not equal to none right till then what we are going to print the data first of all so here what you will write in printf percentage D and temp data this is Javier boom to access the spot temp data means 10 would be printed right now I want to print 3 so you have to move this them in temp now I want to store 200 right address of the previous node from where I can get 200 here I have 200 so here what I can write M is equal to M and then this name of this part is linked now m p-- is equal to temp link means 200 now temp is containing 200 means temp is pointing to this node right while time not equal to none yes temp is not equal to null so again control will enter to the soup print f percentage D temp data template i streets you would be printed temp is equal to temp of link in temp of link I have hundred so in here I will update that M that is hundred so temp is pointing to this node now again check time not equal to none yes temp is 100 it is not equal to null again temp of data means to be printed again temp is equal to temp link in temp link now say in temp of link I have 0 so in temp now I will store 0 it means temp is not pointing to anywhere now check the condition temp not equal to null this condition is not true because temp is now 0 and 0 is equal to 0 so control will not enter into the slope right and what you have printed all the rate at 10 3 & 2 so now you can close this else and this display function right this is how we are going to traverse the stack or you are going to display the data of the step so now next function is peak function see the coding of this function what peak function will return it will display the topmost element what is the top element of the data we are just going to see the top element of the data that's it right they are not going to do top - - or anything fine so now suppose we don't have anything in this stack then it should print a proper message suppose top is equal to is equal to null it means here you can write printf stack as empathy right else else what you can print printf top element is percentage D and how we will print this element how you can exist this end this part pointer to this node is top so where you can write top data this is how you can access the data part and that's it when you will call this big then it will print and fine this is what the peak operation is now we will see the coding for the pop operation so now pop means this topmost element would be removed and after that the size of style becomes here now the size of stack is 3 so now after that size of struct becomes 2 means after popping this the top should point to this node right and if you don't delete this thing then you can simply do top in top I want to store 200 so in top is equal to top link right and after that top would point to this node but we should not leave this node like this the memory is still allocated to this node and memory is very crucial resource so you have to clean this thing this is now our busines you have to clean this garbage so simply you can do you can free this node free and you can use a free function that we have discussed when we were discussing the linked list concept and we can do suppose pointer when pointer is pointing to this node M and we can pass free M after that this memory would be freed right if you will not free this memory that is also fine that is also you have done the popping operation that is also fine but the better approaches you should free this memory and for this thing obviously we are going to take another pointer struct node 10 pointer so that we can pass this pointer in that free function fine so we have taken free sorry struct node M and now Pam should point to top so temp is now containing that is whatever the top is containing three hundred so temp is pointing to this knob right now suppose there is no load in the list in that case under flow condition is there right so here you can check if top equal to equal to none so here you can print printf under flow right there is no node in the list else now what you can do if you want to print the pop element if you want to print that the pop element is then in that case what you will do see first of all here you can print printf here you can write the pop element is percentage D I am writing only this thing and what this thing I want to print so here either you can access this by 10 power by top it's up to you right because both hunters are pointing to this no time is assessing this by top top data top data right so now this you would print 10 after that we can do what after that after removing this you because I want to remove this thing now so the stop should point to this node right so after that I can do top is equal to and this of this node I want to so that is 200 from where I can get 200 here I have 200 so I can write top is equal to top link or you can write top is equal to temp link because this node is having two pointers temp and top so you can access these parts either by temple top it's up to you so you can write top is equal to temp off link that is also fine now top is containing two hundred so now top is pointing to this node right now you can free this node here I can write free and the pointer still pointing to this node is 10 right now this is how we have deleted this node and if you don't want to print the pop element then no need to write down this line simply top is equal to top of length and here this would be pointing right and if you will not free this memory free of them if you will not take this temp pointer that is also fine fine but you should take this for freeing this memory right because we cannot leave this garbage like this so now the output of this pop function would be in because we have deleted we have print printed the state a table data now again if you call peak in that case it should print what three only because now after popping one data the topmost element is three so it should print three and when you will display the function sorry when you call the display function then it would display three two so here three and two this would be the output right and now could have this display would be 10 3 to 10 3 n 2 right so this is how we are going to implement stack using link list so next video we will discuss some more applications of stack using code as well as we will discuss about queue data structure fine so as soon the next video till then bye bye take care

Channel: Jenny's lectures CS/IT NET&JRF

Views: 222,546

Rating: 4.9242649 out of 5

Keywords: data structures tutorials, operating system, data structure and algorithms, stack implementation using linked list, stack in data structure, what is stack, stack operations, linked list in data structure, how to implement stack using linked list, stack implementation using arrays, ds notes, dsa, ugc net computer science coaching classes, GATE cs, cs it youtube channels, c programming, jenny's lectures, jenny data structure, jayanti khatri lamba, net exam, data structure notes

Id: T_UXDTy23DQ

Length: 27min 0sec (1620 seconds)

Published: Tue Sep 10 2019