Understanding Stacks: Concepts and Operations

From this presentation onwards, we are starting with this new chapter called stacks. And in this particular presentation, I will introduce you to the concepts of stacks. So, without any further delay, let's get started. Here is the outline of this presentation. First, we will look into the definition of stack, what a stack is all about. Then we will look into some real-life examples of stacks. And then after that, we will look into what is a stack as an ADT, that is abstract data type. And finally, it is important for us to look into some stack operations, including primary and secondary operations. So without any further delay, let's move on. Here is the definition of stack. A stack is a linear data structure in which insertions and deletions are allowed only at the end, called the top of the stack. Okay. First of all, I want you to note this that stack is a linear data structure, just like array or linked list. Okay. So stack is no different. Stack is a linear data structure, but Insertions and deletions are allowed only at the end in case of stack, right? We know that insertions and deletions are allowed anywhere in case of array and linked list. But here when we talk about a stack, then insertions and deletions are allowed only at the end called the top of the stack, okay? So when we try to imagine a stack, we can imagine it like stack of books or we could have a stack of coins, right? These two are real life examples of stacks. You can see that if you want to place a book, we usually place it at the top. And if you want to access a book, we usually access the topmost book, right? Similar to the stack of coins, if you want to access a coin, the easiest possible way is to access the topmost coin. Or if you want to insert a coin, we can insert a coin at the topmost place. It is easier, right? Obviously, these two are the examples of stacks. Now, in both these examples, there are two things which are common. First is, Any object either book or a coin can be accessed only from the top. And second thing is any object can be added only at the top. Now, you might be wondering or you might ask this question. It is possible to access the chemistry book before accessing the physics book. Obviously, you might argue this. I can access chemistry book before accessing physics book or I can access mathematics book before accessing these two books. It might also be possible that I can access this particular coin before accessing this coin, right? Or maybe I can add a new coin in between in these two places maybe. This is possible, right? But I want you to imagine a stack like this where the objects are placed inside the glass jar. So here you can imagine a stack of books has been placed inside a glass jar. And you can also imagine a stack of coins has been placed inside a glass jar. Now it would be nearly impossible for you to access the chemistry book before accessing the physics book. Isn't that so? Now it is easier to imagine a stack, right? So you can imagine a stack as a glass jar and the objects are placed inside the glass jar. Now you are allowed to access the data only from the top and you are also allowed to add the data only at the top. Okay, there is no other way. Obviously, glass jar is closed at the bottom, right? You can see this. But it is opened at the top. Therefore, there is only one way to insert or delete an object from the stack. Right? There is only one way. Now, I want you to understand what is stack as in ADT, that is abstract data type. When we define a stack as an ADT or abstract data type, then we are only interested in knowing the stack operations from the user point of view. Okay. So when we define a stack as an ADT, we are only interested in knowing the stack operations from the user point of view. Obviously, user is not interested in knowing the implementation details, right. User is only interested in knowing what type of operations we can perform on stack. That is what I want you to imagine. So, when we try to define a stack as an ADT, we will only try to understand what type of operations can be performed on the stack. This simply means we are not interested in knowing the implementation details at this moment. We are only interested in knowing what type of operations we can perform on stack. Okay, only what type of operations. We are not interested in knowing how these operations are performed. Right? Now, we will look into some primary and secondary operations which are sub- ported in case of stack. Let's look into one primary operation that is push operation which actually allows us to insert data onto stack. So imagine a stack like this, a glass jar, okay. And this is the data I want to insert inside the stack. So I'll simply use this push operation and I can simply insert this data after using this push operation inside the stack. This is how it will get inserted. So imagine a data is placed over here. and we just want to move this inside the stack, then we have to call this push operation. It will simply insert data onto stack. Okay? Now the second primary operation is pop operation. It simply deletes the last inserted element from the stack. As simple as that. Okay? So here is the stack and this is the last inserted element in the stack. So it simply deletes this data or it simply moves this data outside the stack. Okay, this is how it looks like, right? This is how you can imagine. Now, there are some secondary stack operations as well like top which simply returns the last inserted element without removing it. So imagine a stack like this and here in the stack we have all these elements. We have these three elements inside the stack, one, two and three, where three is the topmost element. This top operation simply returns the last inserted element without removing it. Okay. So imagine a pointer is pointing to this particular element, then it simply returns this element without removing it. Okay. Then we have the size operation, it simply returns the size or the number of elements in the stack. So if we have three elements inside the stack, then size will obviously be three. Right? Then we have this isEmpty function. It simply returns true if the stack is empty, else it returns false. As the name itself suggests, isEmpty, right? It returns true if the stack is empty, else it returns false. So imagine a stack like this. Now, I would like to ask this question, is stack empty? Obviously it is not, right? You will say no, stack is not empty. Similarly, we have this isFull function which simply returns true if the stack is full, else it returns false. So imagine a stack like this. Now, I would like to tell you that this stack is capable of holding only three elements. Then obviously isFull will return true, right? Because stack is full at this time. You can see that stack is full because there are three elements inside the stack. And I have already told you that this stack is capable of holding three elements. Then obviously isFull function will return true, right? Now here we have a list of commands and I want you to execute all these commands one by one. Okay? Now first command is push one. Means simply push this element inside the stack. Let's say we have these three elements one, two and three and first I'm asking you to insert this element inside the stack. So just push this element inside the stack. That's it. Now second operation is push two. This time you have to push this particular element, right? So just push this element inside the stack. That's it. Now the third operation is push three. You can do this also, it's very easy. Just insert this element onto the stack. Right? You can see that the elements are placed one above the other, right? Just like a stack. Now we have this pop operation which simply deletes the topmost element from the stack, which simply moves the topmost element outside the stack, right? So, if we simply call the pop operation, then it will remove this element or move this element out of the stack, right? That's it. Then I'm asking you to check this, isFull. That means isStack full? Obviously it will return false, right? Stack is not full. The stack is capable of holding three elements, right? Now it is holding two elements, hence stack is not full, right? So these are all the list of commands and you have successfully executed all the commands, right? So congratulations, we are done with all these commands and with this we are done with the introduction to stacks. Now I will see you in the next presentation.

Here is the outline of this presentation. First, we will look into the definition of stack, what a stack is all about. Then we will look into some real-life examples of stacks. And then after that, we will look into what is a stack as an ADT, that is abstract data type.

And finally, it is important for us to look into some stack operations, including primary and secondary operations. So without any further delay, let's move on. Here is the definition of stack.

A stack is a linear data structure in which insertions and deletions are allowed only at the end, called the top of the stack. Okay. First of all, I want you to note this that stack is a linear data structure, just like array or linked list.

Okay. So stack is no different. Stack is a linear data structure, but Insertions and deletions are allowed only at the end in case of stack, right? We know that insertions and deletions are allowed anywhere in case of array and linked list.

But here when we talk about a stack, then insertions and deletions are allowed only at the end called the top of the stack, okay? So when we try to imagine a stack, we can imagine it like stack of books or we could have a stack of coins, right? These two are real life examples of stacks. You can see that if you want to place a book, we usually place it at the top.

And if you want to access a book, we usually access the topmost book, right? Similar to the stack of coins, if you want to access a coin, the easiest possible way is to access the topmost coin. Or if you want to insert a coin, we can insert a coin at the topmost place. It is easier, right?

Obviously, these two are the examples of stacks. Now, in both these examples, there are two things which are common. First is, Any object either book or a coin can be accessed only from the top.

And second thing is any object can be added only at the top. Now, you might be wondering or you might ask this question. It is possible to access the chemistry book before accessing the physics book.

Obviously, you might argue this. I can access chemistry book before accessing physics book or I can access mathematics book before accessing these two books. It might also be possible that I can access this particular coin before accessing this coin, right? Or maybe I can add a new coin in between in these two places maybe.

This is possible, right? But I want you to imagine a stack like this where the objects are placed inside the glass jar. So here you can imagine a stack of books has been placed inside a glass jar.

And you can also imagine a stack of coins has been placed inside a glass jar. Now it would be nearly impossible for you to access the chemistry book before accessing the physics book. Isn't that so? Now it is easier to imagine a stack, right?

So you can imagine a stack as a glass jar and the objects are placed inside the glass jar. Now you are allowed to access the data only from the top and you are also allowed to add the data only at the top. Okay, there is no other way. Obviously, glass jar is closed at the bottom, right?

You can see this. But it is opened at the top. Therefore, there is only one way to insert or delete an object from the stack. Right? There is only one way.

Now, I want you to understand what is stack as in ADT, that is abstract data type. When we define a stack as an ADT or abstract data type, then we are only interested in knowing the stack operations from the user point of view. Okay.

So when we define a stack as an ADT, we are only interested in knowing the stack operations from the user point of view. Obviously, user is not interested in knowing the implementation details, right. User is only interested in knowing what type of operations we can perform on stack.

That is what I want you to imagine. So, when we try to define a stack as an ADT, we will only try to understand what type of operations can be performed on the stack. This simply means we are not interested in knowing the implementation details at this moment. We are only interested in knowing what type of operations we can perform on stack. Okay, only what type of operations.

We are not interested in knowing how these operations are performed. Right? Now, we will look into some primary and secondary operations which are sub- ported in case of stack.

Let's look into one primary operation that is push operation which actually allows us to insert data onto stack. So imagine a stack like this, a glass jar, okay. And this is the data I want to insert inside the stack.

So I'll simply use this push operation and I can simply insert this data after using this push operation inside the stack. This is how it will get inserted. So imagine a data is placed over here. and we just want to move this inside the stack, then we have to call this push operation.

It will simply insert data onto stack. Okay? Now the second primary operation is pop operation.

It simply deletes the last inserted element from the stack. As simple as that. Okay?

So here is the stack and this is the last inserted element in the stack. So it simply deletes this data or it simply moves this data outside the stack. Okay, this is how it looks like, right?

This is how you can imagine. Now, there are some secondary stack operations as well like top which simply returns the last inserted element without removing it. So imagine a stack like this and here in the stack we have all these elements.

We have these three elements inside the stack, one, two and three, where three is the topmost element. This top operation simply returns the last inserted element without removing it. Okay. So imagine a pointer is pointing to this particular element, then it simply returns this element without removing it. Okay.

Then we have the size operation, it simply returns the size or the number of elements in the stack. So if we have three elements inside the stack, then size will obviously be three. Right?

Then we have this isEmpty function. It simply returns true if the stack is empty, else it returns false. As the name itself suggests, isEmpty, right? It returns true if the stack is empty, else it returns false. So imagine a stack like this.

Now, I would like to ask this question, is stack empty? Obviously it is not, right? You will say no, stack is not empty. Similarly, we have this isFull function which simply returns true if the stack is full, else it returns false. So imagine a stack like this.

Now, I would like to tell you that this stack is capable of holding only three elements. Then obviously isFull will return true, right? Because stack is full at this time. You can see that stack is full because there are three elements inside the stack.

And I have already told you that this stack is capable of holding three elements. Then obviously isFull function will return true, right? Now here we have a list of commands and I want you to execute all these commands one by one.

Okay? Now first command is push one. Means simply push this element inside the stack. Let's say we have these three elements one, two and three and first I'm asking you to insert this element inside the stack.

So just push this element inside the stack. That's it. Now second operation is push two.

This time you have to push this particular element, right? So just push this element inside the stack. That's it. Now the third operation is push three.

You can do this also, it's very easy. Just insert this element onto the stack. Right? You can see that the elements are placed one above the other, right?

Just like a stack. Now we have this pop operation which simply deletes the topmost element from the stack, which simply moves the topmost element outside the stack, right? So, if we simply call the pop operation, then it will remove this element or move this element out of the stack, right?

That's it. Then I'm asking you to check this, isFull. That means isStack full? Obviously it will return false, right?

Stack is not full. The stack is capable of holding three elements, right? Now it is holding two elements, hence stack is not full, right?

So these are all the list of commands and you have successfully executed all the commands, right? So congratulations, we are done with all these commands and with this we are done with the introduction to stacks. Now I will see you in the next presentation.

Transcript for:Understanding Stacks: Concepts and Operations

Transcript for:
Understanding Stacks: Concepts and Operations