Basic Algorithm for Stack Data Structure

A free video tutorial from Shibaji Paul
Programming Instructor with 16+ years of experience
7 courses
31,381 students
Lecture description
Understanding and development of basic algorithms for Push and Pop operations of Stack.
Learn more from the full course
Fundamental Data Structures & Algorithms using C language.
Learn Data Structures and algorithms for Stack, Queue, Linked List, Binary Search Tree and Heap ( using C Programming ).
15:39:49 of on-demand video • Updated April 2020
Recursion, Stack, Polish Notations, infix postfix, FIFO, Circular & Double Ended Queue, Linked List - Linear, Double & Circular, Stack & Queue using Linked List
What is stack, algorithms for Push and Pop operation. Implementation of Stack data structure using C.
Using Stack - checking parenthesis in an expression
Using Stack - Understanding Polish notations, algorithm and implementation of infix to postfix conversion and evaluation of postfix expression
What is a FIFO Queue, understanding Queue operations - Insert and delete, implementing FIFO Queue
Limitations of FIFO queue, concept of Circular Queue - Implementation of Circular queue.
Concept of Double ended queue, logic development and implementation of double ended queue.
Concept of Linked List - definition, why we need linked list.
Singly Linked List - developing algorithms for various methods and then implementing them using C programming
Doubly Linked List - developing algorithm of various methods and then implementing them using C programming
Circular Linked List - developing algorithm of various methods and then implementing them using C programming
How to estimate time complexity of any algorithm. Big Oh, Big Omega and Big Theta notations.
Recursion, concept of Tail recursion, Recursion Vs Iteration.
Binary Tree, definition, traversal (in-order, pre-order and post-order), binary search tree, implementation.
Heap - concept, definition, almost complete binary tree, insertion into heap, heap adjust, deletion, heapify and heap sort.
English [Auto]
Hello again in this tutorial, I'm going to develop the idea of building a stack using one dimensional attic. Let us build a stack of integers, have taken one one dimensional array of issues. And in order to keep the track we have, the last element was inserted. We need to have a variable and we usually declare this valuable as the top variable. So the purpose of having the target 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 old 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 area is empty, so the index of the last inserted element is invalid in this case. And so we are taking minus one whenever we need to push an element. Then what do you do? Will increment the top by one and then the top goes to the zero element. Now the value of top is zero and we can push the number here at zero element right now. So the top is holding zero and that is the index where the last insertion taking place. Now, if another Bush operation is called, then we can just increment the top by one once more. And the top schools here at 1:00 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 Bush operation once more than the top will be incremented to the index two and then we can insert here before we increment increment the top in order to assign the next Intisar value to the top of the area. You must ensure that the ATI has provision for the elements. That means the ad is not in the overflow state. 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 failing these two elements, then another insertion is not possible. We say that in that case, it's overflow the size of the area. You can see that it's five actually. It can contain five elements at most and the indices starts from zero to four. So let me just go ahead and insert two more elements to make them understand what exactly happens when the air is full. So if I go ahead and try to push another element, top will be here at three. And let me just have 15 here. And then if I call the Bush operation once more, a top will be here at index four. And in that case, we can insert here. So now if we call the Bush operation once more, we are unable to do that because the area is full. So the condition that we need to check each time prior to perform the Bush operation is that if the top is size minus one. If the top equals with the size minus one size is now five sides, minus one is four. So if the top is at that index full, then we are unable to push any more with this particular area. So in the Bush 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 bush has to be dissected, otherwise we can increase the top by one and then sign the value add the top index of this add. So that's pretty straightforward. So let me just go ahead and show you the algorithm for Bush operation. Now it is pretty straightforward and I have written this algorithm here. Here is the algorithm for Bush operation, the procedure Bush exit value as a barometer that it intends to push into the stack you have considered a stack of size equals to one hundred elements. And the top is the interior 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 starts, it receives a barometer 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 to add the top index of the stack. So that's the straight forward push operation. So when 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 by doing that, we need to check whether the stack is empty or not. That means whether the stack is underflow, state or not in 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 operation is going to check whether the top is at minus one or not. If the top is at minus one, that means that stack is empty. In that case, the pop operation just is going to be rejected, cannot be done. So here the top is full. It's not minus one, so it's not underflow. So what do do we pitch the element at top index in some values? And then what do you do with the top one? So the last element gets deleted from the stack, and again, if the population is called is 15, that will be fetched and then the top is going to be diclemente by one again. So in this way, it goes on unless and until it reaches minus one. So here's the straightforward algorithm for cooperation. You can see that the pop operation, first of all, is checking with the top is minus one or not in the top is at minus one. It is actually saying that Stack is underfloor 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 DiClemente in the top by one and then it is returning the value V should not be EDV. 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.