STACK IMPLEMENTATION USING LINKED LIST - DATA STRUCTURES

[Music] hello friends welcome back to our channel so in the previous session we have seen the linear data structures stacks and queues so here come to the stacks stack is a linear data structure where the elements are all merged in a sequential manner and it follows the lastin first-out mechanism only for mechanism so what are the element which is inserted at the last that should be removed first and there will be always a top of the stack and if you want to insert an element first we have to update the first and then we have to insert the element if you want to delete the element first ideally remove the element and just decrement this top value so that we have seen in the previous sessions so stack can be incremented in implemented in two ways that is by using errors and using linked lists so in the previous session we have seen how to implement a stack using errors so there there is the only one disadvantage of you that implementation that is it Eris will be having the static memory allocation so the number of elements is restricted so that if you want to insert more number of elements beyond that size so that cannot be possible so for that purpose we are moving on to the second category that is implementation of a stack using linker list so here before inserting an element we will give an dynamic memory allocation so we need not specify the size before implementing the stack so let us see the implementation of a stack using linker list in this session implementation of stack using linkedlist so first we need to write a structure for an load so we do that in node in the linked list is represented in two compartments that is one is with the data value and other one is the pointer value which points to the address of the next node so first we will create a structure for an order then we will start writing the operations so start the node and some paint data so this is for data inserting the needle next self referential structure spot node star next yes so here we will create some new more temporary node so top means top of the stack to represent the top element of the step now we will see the push operation so we know that the stack consists of three two operations mainly one is push head pop push means inserting an element you to the step pop means removing the element from the stack right I'm going to push in min so we need to do if you want to insert an element we have to allocate the dynamic number I mean we have to look at the memory in a dynamic so let it be mu is equal to start start Lord will not function size of start moon so hard yeah at that-air memory is allocated for the new now we need to insert the data in new of data and if you want to insert the address of the next node in Europe next so initially there is no element in the stack so let it be first C so this is a stack right so let me show you is it initially top is foldable so similarly we will go with the link register presentation all right so first term first this is the first row to be inserted then just read the greater scanf percentage D and present anyway so we are reading the data so that data should be in that element should be storing this data now live is equal to is equal to level that means if it is a first node if it is a first node what should be so new of data is equal to L remained see right next new of next is equal to so this is the first element so it should hold the address of the next one right so address of next one is 0 right because this is the first one see in the link register presentation also we can use this one this is the first one right so it is a stack it is a stag so wherever you are at inserting another relevant that element should be presented here not here right to the left hand side out to the right hand side here also if you want to insert into the stand that element should be yet this position not this position okay so hope you understood this one so here they element for example some 10 mm will be here and this is another because no other element is there I mean right so is equal to now now we have to change the top also initially top whistles on top is equal to new so whenever you are inserting 10 automatically the top is changed to here right so hope you understood if you are inserting an element into the stack what elements should be insulated on the left hand side on the right hand side in the simplest representation of the stack representation it should be on the above the element right so this field I mean this faith is a next field it should hold the address of the next element so address of the next element means there is no element because this is the only first element right yes yes yes but when this else part will be executed if the stack consists of any one element right if the stack consists of any one is it mean then what should be done so if you want to insert the second element that means already the stack consists of one element another it means see again or in the push operation new node will be created some memory will be allocated for the new one element will be taken from the keyboard that is 20 and if pump is equal to scold is on top is not equal to none hope is not equal to learn so this part will all be getting signal paid coming to the else part here also now we can write news of data is equal to elevate similarly move next is equal to C 20 which address should be plus here it should hold the address of the next node what is the next node n so this address should be placed here what is the address of this one right here see hundred node is created on the left hand side so 20 is here this holds the address of the next one what is the next one is here right so that means so this error should be placed right here right so the link will be establishing from here hope you understood so now power should be changing that means Tom should be position with the first and so o is equal to right so hope you understood this one so this is a simple logic for inserting an element into the stack which is implemented using a good list so slight difference between the implementation of a stack using errors and linkedlist right so the same representation if you if you consider the stack representation the last element so see if you are considering this one if you insert the 20 it will be inserted here if you insert text and we'll be here that means 20 is the last statement and 10 is the last but one element and if you understood 30-something will be presented here so 20 is the last element fast but one end and the top of the element in the top of the stack is 30 so whatever the inserting from first element we are inserting that will be the last element in the stack right so that's why we know that in the linked list that last element the address of the last 10 filled with love so here if you are applying the push operation for the first element because it is in last element in the list hope you wrestle again if you perform this push operation again if you perform this push operation you can see that 30 to be insulted so top is equal to none so after changing the taotie's position here office position here right so this part will not get executed this part will be executed only in well we are inserting the first element into this time now s part will be executed numerator is equal to in the main so 30 will be inserted here 30 will be inserted here move next equal to top me off next make this 100 change okay so hope you understood this simple logic for push operation we will go with the pop operation pop means removing the element which is at the top position right so here both the in the stack we have discussed in the previous session that both the insertion and the deviation will be done from one position that is the top of the stack so what are the element we are inserting recently that will be removed first so example also we have seen that organizing plates in a Eric right yes so the push operation right now pop operation so before applying the power operation let us take a three image and then we will delete it hey this is the first element to being second now pop means we have to remove the element from the top of the stack so whatever the element we're assigning at the top that element should be removed first so that's why here pop first we have to check whether the stack is empty or not so if it is if the stack is empty and still if you are trying to remove the element from the stack that implies it is a underflow under flow condition which we have discussed in the stack implementation stack in turn right so first we we need to check for the under flow condition so if is equal to is equal to null top is equal to now this there is no element in the stack so that's why simply we can write here pretty def stack these empty I think but other so else if this is not equal to null then which one should be removed this one should be remove so we need to change the top to the next statement so that's why it's not supposed to assign that into a temporary variable so that is it will do temp is equal to top now just move that up to the next position so top is equal to top all in next so pop off next pop off next week mm right mm will be a sign into top that means this stop will be moved here the stop will be moved to here next simply we can fight so this is a 10 okay so in the first one we have just assigning 10 to 12 so damn Oh next is equal to another so this we can place it as it is okay and this element capitulated or else or else so just we can write whichever it is so here we can write element is equal to so right so then we can find display printf percentage D is deleted what the person is D top of data after that after that this statement top is equal to move next 10th of next equal to none or simply we can use the free function so here we are not deleting the memory just wear disguise the link from one note with angle or simply we can write the free of M so we know that there is a there are different functions in dynamic memory allocation right so what is a mellow kellogg and real and free function free function is used to remove the memory clear the memory which is allocated by using the melaka cannot functions so that's why we can simply free of em so temp is this one free of 10 means whatever the memory allocated for this load that will be removed right so automatically the element is deleted not the top of the stack is 20 right this one this is a simple logic for deleting an element from the stack so deletion can be deletion will be done from the top of the element so before deletion we need to check the underflow condition so if tau is equal to that means there is no element of there is no node existent in the stand so then we can very simply display the message that stack is empty if it is not equal to null that implies there are some elements in the stack that maybe one augment or more than one element so then we need to say the pop to temporary variable and then we need to retrieve the element which is going to be deleted so which is going to be the top of data will be assigned to in when anyone is deleted then we should move the pump to the next element because the first element should be removed the top should be moved to the second element because after decision the second element will be the first segment so then this this statement moves will pop to the second movement now we have to remove the first element so two ways one is f of X equal to love placing the value at the next position so the link will be disconnected or we can use a free function which is available in dynamic memory allocations so which is used to delete or free the memory which is allocated for this particular node so that's why I'm free of M right so this is how we will implement this pop operation now we will see the display of freshness so display how to display the elements of a stack implemented a lincolnís see let us take the three elements here let us take the three elements here so this is the 3000 and us so this is the 2000 a dress so this is the Oh right now display function so how to display all the elements how to display all the elements of a stack which is implemented using the impedance now here also we need to check the under flow condition so if o is equal T is equal to hell that it means no element is inserted in the anymore element is available in the stack so then we can simply a printer stack is empty stack is empty therefore remained available in very increased yes we need to print we need to print this one so first initialize the talk to temporary node because we have we have we need to travel from first element to the last element without changing the power so for for I is equal to top I sorry so simply we can write a when statement okay so why simply we can write here but of not equal to love so unless the power is equal to 1 the loop will be incentive I mean the loop will be a traitor we can simply print printer percentage DD top of data up of data right or simply we can write we can use here M because we need not change the top so temp right so instead of using top in a final attempt so we have to move the temple next in M is equal to M / next 30 so automatically in the first iteration it will check whether pump is equal to null that is false yes condition temp is equal to top so can we be here so temp is recorded 3000 position while stamp or equal to learn to printf temp of data can 50 Atomics 30 will be printing here right temp is equal to temp of next so temp is equal to temp of next 22,000 that visit 2000 so 2000 here so empowered equal to love yes f operator will be printed what is the temp operator temperature for 2000 data in 2000 this won't be so font in here and again M physical type of next so temp is equal to temp of next that will spells it so again the loop will be started m4 equal to null so this is true this is true this and for Sunday's attempt of data so whatever you and the temp well then that is 10/10 will be printed here temp is equal to temp of next what is the time value no temp is equal to temp of mix that's not right next to the value 10 or equal to sign em hard equal to 1 files automatically loop will be exited right so the control will come up from the loop okay so this simple operation of display function so displaying the elements of a stack which is implemented by using the link list right so initiation we have seen the three operations push pop and display so here we are representing the stack operations using linked list so in the insertion the first insertion the first inserted element will be the last element in the stack right so likewise we need to implement the push and pop operations and the display operation right so hope you understood all these are all these operations if you are having any doubts regarding this session feel free to post your doubts in the comment section so that definitely I will try to clarify all your dopes if you really understood my sessions like my sessions share my sessions with your friends and don't forget to subscribe to our channel thanks for watching thank you very much

Channel: Sundeep Saradhi Kanthety

Views: 51,006

Keywords: sundeep, saradhi, kanthety, data structures, fundamentals, basics, arrays, lists, linked lists, stacks, queues, trees, graphs, searching, sorting, insertion, deletion, operations on data structures, primitive, non primitive, linear, non linear, binary trees, binary search trees, stacks using arrays, push, pop, display, top of stack, overflow, underflow, index, array size, stack full, stack empty, LIFO, LAST IN FIRST OUT, LINKED LIST, dynamic memory, malloc, free, stack using linked lists

Id: lTzK54VQd8Y

Length: 23min 15sec (1395 seconds)

Published: Wed Jun 12 2019