May I begin by saying that the stack is a remarkable, absolutely remarkable data structure, one of my favorites. In fact, this is part one of three in the stack videos. Part Two will consist of looking at a stack implementation, and part three will be some source code for how a stack is implemented using a linked list. So here are the topics we'll be covering in this video as well as the others. First, we will answer the question about what is a stack and where is it used. Then we will see some really really cool examples of how to solve problems using stacks.

Afterwards, we will briefly look at how stacks are implemented internally and the time complexity associated the stacks operation. And lastly, of course, some source code. Moving on to The discussion about stacks. So what is a stack? A stack is a one ended linear data structure which models the real world stack by having two primary operations, namely, push and pop. Below you can see an image of a stack I have constructed, there is one data member game popped off the top of the stack and another day a member getting added to the stack.

Notice that there is a top pointer pointing to the to the block at the top of the stack. This is because elements in a stack always get removed and added to the top of the pile. This behavior is commonly known as l i f. Or last in first out. Let's look at a more detailed example on how a stack works and how things are added and removed from a stack. So, let's walk through an example on the left side, I have some instructions on what we need to add and remove to the stack. So the first operation is a pop, so we remove the top element from the stack, which is Apple.

So boom, Apple is going. Now we push onion onto the stack. So we add on into the top of the stack. Next instruction says to push celery onto the stack. Next is watermelon, which we put on top of the stack. Next operation says the pop so we remove the element at the top of the stack.

This is the watermelon we just added. The next operation also a pop so we remove from the top of the stack. This is celery and last operation push this onto the stack so we add lettuce on the very top of the stack. So as you can see, everything operates on the top of the stack, we don't have access to anything else but the top of the stack. This is critical in our understanding of how a stack works. So when in Where is a stack used, stacks are surprisingly used absolutely everywhere.

They're used in text editors to enter text you've written in browsers to navigate backwards forwards. They're used in compilers to make sure you have the correct number of matching braces, and in the right order. stacks are used to model real world stacks such as books, plates, and even games like the Tower of Hanoi, which we'll get to shortly. stacks are also used behind the scenes to support recursion by keeping track of previous function calls. When a function returns it pops the current stack frame off the stack and rewinds to the Next function that is on stack. It's rather remarkable that we use stacks all the time and programming and never even notice it.

Something else you can use stacks for us to perform a depth first search on the graph. A depth first search can be done manually by maintaining your own stack, or by using recursion. Well guess what both use stacks as we've just discussed, complexity analysis. So the following complexity table assumes that you implemented a stack using a linked list. Pushing takes constant time because we have a reference at the top of the stack at all times. Well, the same argument goes for popping and peeking.

Searching however, still takes linear time. The element we're searching for isn't necessarily at the top of the stack. So we may need to scan all the elements in the stack. Hence required Linear amount of work. Now here's a cool example of a problem using stacks problem. So given a string made up of the following brackets round brackets square brackets curly brackets determine whether the brackets properly match.

So analyze examples below to understand what type of bracket sequence is valid and which ones are invalid. So before I show you the solution, try and come up with a solution yourself. Hint use stack. Okay, in this first example, consider the following bracket sequence. As we are processing the string from left to right, I will be displaying the current bracket and the associated reversed bracket. So let's begin.

Forever every left bracket we encounter we simply push those on The stack. So this is a left square bracket that I have highlighted in light blue. So we push this one on the stack. Same goes for the next left square bracket and for this left curly bracket Okay, this is a right square bracket. So we encountered a right square bracket, we need to do two checks. First we check if the stack is empty if so the bracket sequence is invalid.

But if there are still things in the stack, then we pop the top element and check if its value is equal to the reversed current bracket. Right now the top element is equal to the reversed bracket so we are good. Next is a right square bracket again, so is the stack empty No, it isn't. So we're good. Is the top element of stack equal to the reversed bracket? Yes, it is.

So let's keep going around left bracket. Let's push it on to the stack. A right bracket. Is the stack empty. No. Okay, so we're good.

Is the top element of the stack equal to the reverse bracket? Yes. Okay. So we're good. Another right bracket. Is the stack empty?

No. Okay, good. And is the top element of the stack equal to the reverse bracket? Yes. Okay, good. And now we're done processing the string, we need to make sure the stack is empty.

Now. Why is that? Well, in case the last few characters and the bracket sequence were left brackets, they would still be in the stack, right? But our stack is empty. So we can conclude that this bracket sequence is indeed valid. All right, let's do another example with another bracket sequence.

So trying to work this one out. So the first bracket is a left bracket, so we push on to the stack. The second bracket is also a left bracket, so we will push onto the stack. This next bracket is a right bracket. So let's check if the stack is empty. No, that's good.

And is the top element of the stack equal to the reverse bracket? Yes, it is. This next bracket is a right bracket. Is the stack empty. No. So we're good.

And is the reverse bracket equal to the bracket at the top of the stack? No it isn't. So this bracket sequence is invalid. So here's the pseudocode of the algorithm we just ran through. So if we let us be a stack For every bracket in our bracket string, we can get the reversed bracket for that turn bracket easily. So if our bracket is a left bracket, push it onto the stack.

Otherwise we check if the stack is empty, and if the element of the top stack is not equal to the reversed. If either of those conditions are true, then we return false otherwise we return whether the stack is empty or not. And if it is empty, then we have a valid bracket sequence. Otherwise, we do not want to take a moment and look at the Tower of Hanoi, a very popular game amongst mathematicians and computer scientists to see how it relates with stacks. The game is played as follows. You start with a pile of disks on the first peg on the left, and the objective of the game is to move all the discs to the right most This pile, and each move, you can move the top desk of any pile to any other pile with a restriction that no disk be placed on top of a smaller disk.

So we can think of each peg as a stack, because we're always moving the top element in a peg and placing it on another peg. So shall we play, I will let the animation run and you will see how each peg acts like a stack. It's pretty cool. So you just saw how transferring elements from one peg to another is exactly the same as public hopping a disk from one stack and pushing that same disk onto another stack, given that the disk you're placing on top is smaller. So that's really cool. All right, in the next video, we're going to quickly look at how a stack is actually implemented.

If you're interested in some actual source code for a stack that can be found at the link at the bottom of the slide. I will also be going over the source code for a stack in the last video of the stack series. So stay tuned for that and thank you so much for watching.