3.1 Stack in data structure | Introduction to stack | data structures

Yeah right we have discussed few data structures like array and Ling lists how data is stored in array what are the different operations on array what is linked list or what are the different operations on linked list how data is stored in linked list right and now we will see what is the stack data structure so you can see it is a linear data structure fine and seen array what is their random access as possible you can directly access any data in a constant time in linked list what only sequential access is possible right what about stuck in stack only you can say limited access is possible right or you can say it is a ordered list what is that it is an ordered list or you can say it is a collection or you can say it is a container which is going to follow a rule for insertion and deletion of the data right and what is that rule or what is that restriction you can say or what is that principle right which that stack data structure follow so that rule is insertion and deletion is possible only from one end right this is applied on both insertion and deletion insertion and deletion is possible from only one end like you can take a real life example suppose you have a CD stand right like this you are going to put CDs here first CD then second third fourth fifth obviously like this you are going to put suppose you want to insert another CD in that case you have only one way to insert CD from the top only you cannot insert CD here from the bottom you cannot insert from the left or right the only way is from the top only you can insert that CD right second K says if you want to take out a CD from this series stand then what you will do only one option you can take out from the top right suppose you want to take out in this city the first CD right so you don't have any option the only option is first of all you will have to take out all the CDs which are placed above this CD after that only you can take out this CD right that is the restrictions on insertion and deletion in stock fine so in this video we will see how logically you are going to represent a stack what are the introduction introductory part of stack some basic operations on stack what what are the meaning of those operations as well as some applications of stack in next video we will see how to implement a stack right using arrays as well as using link inst so now like this if you map this real-life stack obviously this is what a stack only or you can say a stack of plates right one plate is you have put one plate here if you want to play a place another plate then you will put on this plate then third and fourth and fifth like this you are going to place if you want to remove a plate then first plate you will take out first right so the principle is what last in first out you can say right this is the last plate or you can say this is the last CD you have put in the CD stand and the last CD would be the first one that you can take out so last in first out leaf oh so the rule on which this stack data structure works is what leave for last in first out or you can say first in last out this CD was first in but if you want to take out this CD then this would be the last one you can take out because for for taking out this CD outside of the series 10 you how to take out all the above CDs first of all right so first any last out and if you will map this real-life example of stack in this with this stack then you can say the logical represent datian of the stack is what we represent stack something like this like this this is what a stack you will represent this it is a container which has only one open end you can insert data from here you can delete a data from here right there is no other way this is what a stack logical representation of stuff this is not actual representation of stack right that we will discuss in later we use right and in stab insertion operation when you will insert some data understand that operation is known as push right and deletion operation is known as pop so two fundamental operations are there on the stack one is push one is pop push means inserting or putting a data into the strap pop means taking out or deleting the topmost data from the stack right two fundamental operations many more operations are also there that if you are we will also discuss now see this is the only and from where you are going to push and pop the data right so this is known as top top of the step right you can insert a data and you can delete data from top of the stack that end is known as top from where you can insert you can push and pop data right so now we will see some operations that are performed on star data structure see first is push and in bracket you will write down that a data you want to insert into stack C stack is what it is a collection of similar data type only it's not like that this is stack and here the first data is suppose integer and after that I'm inserting a character after that again I am inserting to know you can only insert the data of similar data type either in teaser all the data should be integer or character or float something like this right see push second operation is pop operation right here they don't pass any argument here why so because pop means always the topmost element would be popped out from the step right so no need to pass anything in this function these are two fundamental operation third operation may be peak operation or somewhere it is also known as top operation it means what it is going to return the topmost element of the stack without removing that element from the stack see Bob will return the topmost element from the stack as well as it will remove that element from the stack see suppose this is what I have stack and in this I have data type 1 I have data 1 2 & 3 if you write down pop it means it will remove 3 from the stack now this is the step right and if on this stack you will perform peak operation or top operation it means it will return 3 but it will not remove this from the step this is the difference right fourth operation may be is empty means it will true if the stack is empty there is known data in the list just in the stack right otherwise it will return false sake another may be is full so this function will return true if this stack is full otherwise it will return false see these are not the only operation you can perform there are many more operation you can perform on stack like you cannot perform search operation reverse operation you can find out that minimum element from the stack maximum value element from the stack right bad thing also we will discuss in a later videos right these are some fundamental operations you can perform one stack fine now we will see the logical representation of stack as well as we are going to perform these operations right so this is how we logically represent the step right not actually in the memory this is just a logical representation right for your understanding purpose now obviously you want do you want to push some data in the stack right so you need to know the capacity of the stack or you can say the size of the stack so you need to allocate some memory to the stack right and how to fix that size how you will get to know the size of the stack you can allocate the memory either using static memory allocation or dynamic memory allocation there are two ways to implement stack static memory allocation and dynamically you can implement step static means using arrays you can implement stack write dynamic means using linked lists you can implement stack so these implementations we will see in the next video with the proper with the help of an example plus code right so now suppose I have taken the size of the stack as 5 means the stack can store only five elements either using by static memory location or dynamic memory allocation right that thing in detail we will discuss in next video see suppose the capacity is here 5 so you can insert here 5 elements only fine at starting at starting top is what top is equal to minus 1 fine 5 means you can say you can insert 5 elements the index would be 0 first of all then 1 then 2 then 3 then 4 from 0 to 4 right so here 5 elements I can store this is the capacity of the stack at starting top is minus 1 right minus 1 means somewhere here minus 1 hypothetically we assume that here we have minus 1 index right now suppose in the empty stack you call this pop operation what would happen pop means the topmost element would be removed but here we don't have anything stack is empty in this case it is what under flow condition it will return what the stack is empty so this is what an under flow condition you can say right and now suppose I'm calling push to write actually implementation or loose also we will see how to write down the code for push and pop right here I am just giving you the brief introduction push 2 mins here from the top one you will insert this 2 right we have only one end so first of all what would happen top is -1 so we will increment this top first of all top plus plus it means top becomes 0 now now here we have top and now you will insert this to write again if you will call push 3 again first of all top plus plus right now table becomes this one top is pointing to this one 1 and now you will insert 3 here in the stack fine if you call pop no need to pass any argument here why so because only the topmost element would be removed from the stack you cannot write here pop 2 means if you want to remove this 2 you cannot see pop 2 and this 2 would be removed no always this element would be removed right so pop 3 pop means the 3 would be removed from the stack and now see right now we will do top minus minus means now again top is 0 Oh second again if you do pop in that case again though would be removed from the list or simply you can do top minus minus means top is now minus 1 right and if you will not remove this if you will not take out this from the stack that is also fine because this is now a garbage we do not care what garbage value is there in the stack because after that if you will again call push for then first of all top plus plus means now top becomes 0 minus 1 to 0 here we will this too would be overwritten and herefor would be stored right this thing also will discuss how to code push and pop operation fine now suppose I am going to push four times one five six and seven one five six and seven again I am calling push eight now the stack is full Vegas capacity is only five right so now it should return what it is what an overflow condition we have discussed what is under flow condition now here this is what overflow condition if this dope is pointing to this maximum size minus one the index is for maximum size is five in that case it would return overflow condition you cannot insert any data in the stack because stack is full so this is what overflow condition and now here if you will call is full function means it will return true if the stack is full and now the condition is status full so it would return at this time is full function would return true right and when there is nothing in the stack suppose we have popped out all the data and after that we call is empty in that case it would return true because stack is empty how you are going to code these function we will see what so now what are the applications of stack see the very basic application is if you want to reverse a string or in reverse a word then we will use stack that is very simple suppose I want to reverse I have a string ABC and D so I want to reverse this I want to print a DC B and a so simply what I can do I can push this into stack first of all ABC and D and then pop out first of all D would be popped out then C then B then e this is what we have reversed to the string second application is for undo mechanism in text editor I guess everybody have used this undo mechanism suppose you have written something I have written ABCDE right in the text editor in text editor and you press ctrl-z the shortcut key for undo then you would be deleted then D would be deleted then C then B then a this mechanism is performed using step in your text editors right third application maybe you can use it in recursion or you can say in function call when you are going to call a function then obviously something would be returned some value would be return like and recursion means it is you can say a chain or function call a function is calling itself again and again right so whenever that function would return something then that values would be stored in stack how actually recursion will work that also we will discuss when we will discuss recursion fourth may be to check the balance of the parentheses parentheses means like this the compiler use stab for verifying the balance of the parentheses means for each opening parenthesis there is proper closing parenthesis at right place right suppose here is opening again here I have opened again here I hope open so it means there should be three closing brackets right so this balance would be checked using step this thing also we will discuss in detail right fourth application may be in fix to postfix or prefix conversion when you are going to convert these expressions from infix to postfix or in fix to prefix in that case also starting to be used that thing also will discuss entity right and as well as in many algorithm stack data structure is used you can say in topological sorting in DFS we are using staff in Tower of Hanoi problem also we are going to use staff in tray traverser also we will use step right so there are many applications of staff and sixth you can say for the evaluation of postfix expression we will use step right that is also we'll discuss all the application we will discuss in detail this is just an introductory video of this tag to get you familiar with stack the logical representation of star how actually we are going to implement stack how we are actually going to code these operations we will discuss in next you fine so I'll see in the next video till then bye-bye take

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

Views: 339,377

Rating: 4.9245176 out of 5

Keywords: data structures tutorials, operating system, data structure and algorithms, what is stack, stack in data structure, ADT, stack ADT, stack vs queue, stack operations, implementation of stack, ugc net computer science preparation, gate, GATE cs, coaching classes, ds, dsa, ds notes, jenny's lecture, jenny data structures, jayanti khatri lamba, c programming, cs it youtube channels, stack implementation in c/c++, introduction to stack, algorithms, linked list in data structure

Id: bxRVz8zklWM

Length: 17min 40sec (1060 seconds)

Published: Sat Sep 07 2019