3.1 Stack in Data Structure | Introduction to Stack | Data Structures Tutorials

data right we have discussed few data structures like array and linked list how data is stored in array what are the different operations on array what is link list what are the different operations on link list how data is stored in link list right and now we will see what is stack data structure so you can see it is a linear data structure fine and see in array what is there random access is possible you can directly access any data in a constant time in link list Not only sequential excess is possible, right? What about stack? In stack only you can say limited uh access is possible, right? Or you can say it is a ordered list. What is stack? 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 role 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. Uh 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 case says if you want to take out a CD from this CD stand then what you will do? Only one option you can take out from the top. Right? Suppose you want to take out this CD the first CD. Right? So you don't have any option. And 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 stack. Fine. So in this video we will see how logically you are going to represent a stack. What are the introduction uh 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'll see how to implement a stack right using arrays as well as using link list. 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 place another plate then you will put on this plate then third then fourth then 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 Right. This is the last plate or you can say this is the last CD you have put in this CD stand and the last CD would be the first one that you can take out. So last in first out Leo. So the rule on which uh this stack data structure works is what? Leo 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 CD stand you have to take out all the above CDs first of all. Right? So first in 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 representation of the stack is what we represent stack something like this like 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 data from here right there is no other way. This is what a stack logical representation of stack. This is not actual representation of stack, right? That we will discuss in uh later videos, right? And in stack insertion operation when you will insert some data in the stack, 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 stack. Pop means taking out or deleting the topmost data from the stack. Right? Two fundamentals operations. Many more operations are also there that we we will also discuss. Now see this is the only end from where you are going to push and pop the data. Right? So this is known as top top of the stack 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 stack data structure. See first is push and in uh bracket you will write down that data you want to insert into stack. See 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'm inserting two. No you can only insert the data of similar data type either integer all the data should be integer or character or float something like this right? See push second operation is pop operation right here we don't pass any argument here why so because pop means always the topmost element would be popped out from the stack 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, pop 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 one. I have data 1, two and three. If you write down pop, it means it will remove three from the stack. Now this is the stack right and if and on this stack you will perform peak operation or top operation it means it will return three but it will not remove this from the stack. This is the difference right. Fourth operation may be is empty means it will true if the stack is empty. there is no data in the list in the stack right otherwise it will return false. Sec is full. So this function will return true if this stack is full otherwise it 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 can perform search operation, traverse operation, you can find out that minimum element from the stack, maximum ele element from the stack. Right? That thing also we will discuss in later videos. Right? These are some fundamental operations you can perform on 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 star right not actually in the memory this is just a logical representation right for your understanding purpose. Now obviously you want 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 stack. Static means using arrays you can implement stack. Right? Dynamic means using link list you can implement stack. So these implementations we will see in the uh 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 five means the stack can store only five elements either using by static memory allocation or dynamic memory allocation right that thing in detail we will discuss in next video. See suppose the capacity is here five. So you can insert here five elements only. Fine. At starting at starting top is what? Top is equal to minus one. Fine. Five means you can say you can insert five elements. The index would be zero first of all then one then two then three then four from 0 to four. Right? So here five elements I can store. This is the capacity of the stack at starting top is minus one. Right? Minus1 means somewhere here minus one. Hypothetically we assume that here we have minus1 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? Underflow condition. It will return what the stack is empty. So this is what an underflow condition. you can say right and now suppose I'm calling push two right actual implementation al also we will see how to write down the code for push and pop right here I'm just giving you the brief introduction push two means here from the top only you will insert this two right we have only one end so first of all what would happen top is minus one so we will increment this top first of all top plus+ Plus it means top becomes zero. Now now here we have top and now you will insert this two right again if you will call push three. Again first of all top plus right? Now top becomes this one. Top is pointing to this one one. And now you will insert three 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 two means if you want to remove this two, you cannot see pop two and this two would be removed. No, always this element would be removed. Right? So pop three. Pop means the three would be removed from the stack. And now see right now we will do top minus minus Means now again top is zero or second again if you do pop in that case again two would be removed from the list or simply you can do top minus minus means top is now minus one 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 we do do not care what garbage value is there in the stack. Because after that if you will again call push four then first of all top plus+ means now top becomes 0 - 1 to 0 and here we will this two would be overritten and here four would be stored. Right? This thing also we'll discuss how to code push and pop operation. Fine. Now suppose I have called push four times. 1 5 6 and 7. 1 5 6 and 7. Again I'm calling push 8. Now the stack is full because capacity is only five. Right? So now it should return what it is what an overflow condition. We have discussed what is underflow condition. Now here this is what overflow condition. If this top is pointing to this maximum size minus one, the index is four, 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 stack is full. So it would return at this time is full function would return true right and when 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 will you are going to code these function we will see so now what are the applications of stack see the very basic application is if you want to reverse a string or reverse a word then we will use star that is very simple suppose I want to reverse I have a string a b c and d so I want to reverse this I want to print d c b and a so simply what I can do I can push this into stack first of all a b c and d and then pop out first of all d would be popped out then c then b then a this is what we have reversed 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 A B CDE E right in the text editor and in text editor and when you press control Z the shortcut key for undo then E would be deleted then D would be deleted then C then B then A. This mechanism is performed using stack in your text editors. Right. Third application maybe you can use it in recursion or you can say in function call. When you're going to call a function then obviously something would be returned some value would be returned like and recursion means it is you can say a chain of 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 maybe to check the balance of the parenthesis. Parenthesis means like this. The compiler use stack for verifying the balance of the parenthesis. 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 opened. 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 infix to postfix or prefix conversion. When you are going to convert these expressions from infix to postfix or infix to prefix in that case also stack would be used. That thing also we will discuss in detail. Right? And as well as in many algorithms stack data structure is used. You can say in topological sorting in DFS we are using stack. In tower of annoy problem also we are going to use stack. In trade reverser also we will use stack. Right? So there are many applications of stack. And sixth you can say for the evaluation of postfix expression we will use stack. Right? That is also we'll discuss all the application we will discuss in detail. This is just an introductory uh video of the stack to get you familiar with stack. The logical representation of stack. How actually we are going to implement stack? How we are actually going to code these operations? We will discuss in next video. Fine. So I'll see you in the next video. Till then bye-bye.