Basic Algorithm for Stack Data Structure

Hello again. In this tutorial I'm going to develop the idea of building a stack using one dimensional array. Let us build a stack of integers. I have taken one one dimensional array of integers and in order to keep the track where the last element was inserted, we need to have a variable and we usually declare this variable as the top variable. So the purpose of having the top variable is just to hold the index of the last inserted element into the stack so that we can go on inserting the next element when the next push is called. And also we can delete the top just by using that top variable. So here we go. We take the top variable and we usually initialize this top variable at the very beginning at minus one. Minus one is an invalid index. And since the array is empty, so the index of the last inserted element is invalid in this case. And so we are taking minus one. Now, whenever we need to push an element, then what we will do, we will increment the top by one and then the top goes to the zeroth element. Now the value of top is zero and we can push the number here at zeroth element right now. So the top is holding zero and that is the index where the last insertion taking place. Now, if another push operation is called, then we can just increment the top by one once more. And the top goes here at one and we can assign the value here so you can see that the top is holding the position of the last inserted value. Now, let me just insert one more element here. So if we call the push operation once more, then the top will be incremented to the index two and then we can insert here. Now before we increment increment the top in order to assign the next integer value to the top of the array, we must ensure that the array has provision for the elements. That means the array is not in the overflow state. Now, if we go on inserting the elements in this way, ultimately the top will reach to the index four and then the overflow will occur. Now, whenever the top comes here at this index, by filling these two elements, then another insertion is not possible. We say that in that case it's overflow the size of the array. You can see that it's five actually, it can contain five elements at most, and the indices starts from 0 to 4. So let me just go ahead and insert two more elements to make you understand what exactly happens when the array is full. So if I go ahead and try to push another element, Top will be here at index three and let me just have 15 here. And then if I call the push operation once more, the top will be here at index four and in that case we can insert here. So now if we call the push operation once more, we are unable to do that because the array is full. So the condition that we need to check each time prior to perform the push operation is that if the top is size minus one. If the top equals with the size minus one size is now five, size minus one is four. So if the top is at the index four, then we are unable to push any more with this particular array. So in the push operation, the first thing that we need to do is to check for the overflow. If the top is size minus one, then we cannot insert its overflow. The push has to be rejected. Otherwise we can increase the top by one and then assign the value at the top index of this array. So that's pretty straightforward. So let me just go ahead and show you the algorithm for push operation. Now, it is pretty straightforward, and I have written this algorithm here. Here is the algorithm for push operation. The procedure push takes a value as parameter that it intends to push into the stack. We have considered a stack of size equals to 100 elements and the top is the integer that is going to hold the index of the last inserted element into the stack and initially. And initially we have assigned minus one to the top. So when the procedure push starts, it receives a parameter that it intends to push. So here, first of all, at line number two, you can see that we are checking the top with size minus one. If it indeed equals with size minus one, then it says that stack is overflow and we are exiting the push. Otherwise, if this condition is false, we are coming here at line number six and we are increasing the top by one and we are assigning the value V at the top index of the stack S. So that's the straightforward push operation. So while we pop, we do the reverse thing. We actually get the element from the top of the stack. And we then decrement the top by one. But prior to doing that, we need to check whether the stack is empty or not. That means whether the stack is in underflow state or not. If the stack is not underflow, in that case we can just pop the stack. Otherwise not. Let me show you that. Here was our example and we have these five elements inserted into the stack. And now if we call the pop operation, it's going to check whether the top is at minus one or not. If the top is at minus one, that means the stack is empty. In that case, the pop operation just is going to be rejected, cannot be done. So here the top is four. It's not minus one, so it's not underflow. So what do we do? We fetch the element at top index in some value. And then what do we do? We decrement the top by one. So the last inserted element gets deleted from the stack. And again, if the pop operation is called, it's 15, that will be fetched and then the top is going to be decremented by one again. So in this way it goes on unless and until it reaches minus one. So here's the straightforward algorithm for pop operation. You can see that the pop operation, first of all, is checking whether the top is minus one or not. If the top is at minus one, it is actually saying that stack is underflow and it is exiting the pop operation. Otherwise, it is fetching the value from the top index into a variable V and then it is decrementing the top by one and then it is returning the value v. It should not be E, it is v. So that's the way we do the pop operation. So the next tutorial I'm going to develop a C program where we will be implementing this push and pop operation for a stack. Thank you.