hey everyone sorry about the delay but in this video i'm gonna give you a quick ish introduction to stacks queues and decks or double ended queues so let's get started first of all what's a stack well personally i like to think of a stack like a bunch of pancakes so just imagine for a second that these circles represent pancakes with different numbers written on them we could have any type of data here but we're using numbers or integers as an example here and one feature of pancakes the real world pancakes is that you can stack them on top of one another so just imagine that this line here represents a plate and once you have a plate you can have pancakes stacked on top of one another so you could have minus one at the bottom and then you can put three on top of it and then let's say this one nine this pancake right here and then at the top you can put this one and then you might say okay what if i wanna retrieve this pancake right here with the number three written on it then what you would need to do is you would need to take out this one first at the top and then this next one the nine pancake and then finally you can take out this one uh so that's how you know pancakes in a real world work and it's the same thing with the stack data structure so a stack is a collection of data in which you can only add a piece of data at the top of the structure or retrieve a piece of data from the top of the structure so you aren't really able to retrieve data from any position just like you could for example in array so another way to describe the same thing is that whatever piece of data you put in last will need to come out first so in the current structure of these three pieces of data the last piece of data that we put in is nine so that needs to come out first and that's sometimes referred to as last in first out okay so that's how a stack works but how can we implement it well one way to implement it is uh by using an array so we have an array of eight elements here and we're going to try to represent this stack right here to do that the first thing we'll need to do is we'll need to have a pointer or just an integer variable that's going to point to the last element that we put in in this data structure and let's say for now that the stack is empty then there is no last element 2.2 so we can initialize this variable to -1 or the index that would be here but that doesn't exist and this shows that this stack is empty and now what if we want to start putting in some pieces of data here for example -1 here then what we can do is move the pointer here again this is going to always point to the last element that we put in in this data structure and then put -1 here and what if we want to put in a 3 on top of -1 then we can move the pointer again again pointing to the last element that we put in and then put 3 here and then we can keep doing that if we want to put 9 here oh you can move uh the pointer here or increment pointer by one and then put nine here and what if you want to remove uh this number right here nine and to do that all you need to do is you need to move the pointer back by one or decrement this variable by one now you could do something with this number right here you know either erase it or change it to something else but it doesn't really matter because in this data structure we always know that the pointer always points to the number that's at the top of this structure so the numbers following this pointer are not relevant so we can keep going like this if you want to put in 2 here you can move the pointer back here and then update this number right here with two and then if you want to put nine again here you can move the pointer by one and then put nine here and throughout this explanation we saw a few key operations here one is delete sometimes it's called pop that's deleting or removing a number from this data structure and another one is add and that's adding a number on top of this data structure and with this particular implementation you can implement both of them in one or in a constant amount of time and that's assuming that the number of elements that we put in in this data structure doesn't exceed the length of the array and if it does you will need to either zero an error or make a new array that's longer than the original array and transfer all the elements from the first array to the second array and that would take some extra time anyway that's it for a stack let's now take a look at a queue the analogy i use to understand a queue is a bunch of people lining up in a line or in a queue so let's say we have these people with some numbers assigned to them just for convenience and they want to line up to do something for example to see this octopus for whatever reason and this octopus is busy so they need to line up and with a cube i think you already know how it works but you can put people in the queue or in this line and when the octopus is free uh the person that's at the front of the queue you can see the octopus and then go away and then you can add more people in the queue or more numbers in the queue and then the person or the number that's in front of the queue you can see the octopus and then go away so that's the idea of the queue data structure and i think you can see that uh whatever number or whatever person that came in first will go out first too out of this data structure and that's sometimes referred as uh first in first out okay and how can we implement this data structure one way to implement it is with an array again and this time we're going to have two pointers the first one is going to point to whatever is at the front of the queue or in this particular example this number or this person right here and we're going to put this one right here at zero for now and the second pointer is going to point to the space that's right after the last person or the last number in the queue and for now i'm going to put this at the same position as the first pointer at zero and let's say that the queue is empty right now then we're gonna make these pointers uh be initialized to both zero right here and we're gonna implement this data structure so that whenever these two pointers point at the same thing this q is empty okay now let's think about how we can represent a line of people with this particular implementation so let's say that this person comes uh in the line first then we can put number one here and then move the second pointer right here and if there's another person uh right after that let's say 42 then we can put 42 here and then move the pointer here again the first pointer will always be pointing at the first person in the queue or the front of the queue and the second pointer will always be pointing at the space right after the last person or the last number in the queue so let's keep going with this if 13 comes in a line we can put 13 here and then move the pointer move the second pointer right here and what if the octopus is free now and this person one sees the octopus and goes away then uh we can just move the first pointer over here and we don't really have to do anything with this number right here one because in this implementation we'll know that the q is only between these two pointers so we can just keep going like that and just to show you more examples if -4 comes after that we can put -4 here and then move the second pointer over here if zero comes after that we can put zero here and move the second pointer over here or increment the second pointer by one and if 42 goes away we can move the first pointer over here let me just keep going like this and what if you have a situation like this now where you have three people in the queue 0 1 and 42 and you want to add another person minus 4 here to do that we can put minus 4 here and then you would try to move the second pointer over here but that's out of bound to fix that you can just move this pointer back here at zero instead so you can actually visualize uh this array like a circular array where if you try to go out of bound you just go back to zero so let's just keep going like that uh if we want to put 13 after that you can put 13 here and then move the second pointer by one over here and it would work the same way for the first pointer too i've if the first pointer keeps going to the right and if it's about to go out of bound instead of having it go out of bound we can just bring it back to zero right here and another thing to note about this particular implementation is that you're only able to store almost n minus one elements in this data structure assuming that the length of the array is n to explain that let's consider this situation where we have the second pointer right here and we have some elements here here and here if you try to add one more element right here you would need to move the second pointer right here to the same position as the first pointer but we've already said that in this particular implementation uh if these two pointers point to the same thing this q is empty but clearly it's not empty and that's why we would need to stop here and that's why we're only able to store n minus 1 elements where the length of the array is n if you want to store more elements you will need to either throw an error or create a new array that's longer than the original array and then transfer all the elements to the new array anyway in this implementation we saw two key operations one is removing an element or a person or a piece of data from the cube and another one is adding a piece of data to the queue sometimes it's called dq and q and with this particular implementation assuming that the number of elements doesn't exceed n minus 1 we can implement both of those things in o 1 or in constant time and that's it for a queue but let's quickly discuss another data structure and that's a deck or double ndq it's a more generalized version of the queue data structure that we saw and in this data structure deck you're able to put data and remove data from either end of this queue so you can remove this person right here or you can remove this person right here and you can add a person at the front of the queue or at the left side of the queue or add this piece of data at the right side of the queue and one way to implement this is similar to the implementation of the queue that we saw so you can use a circular array still and have the same kind of structure but in this new structure we're able to remove data from either end and add data to either n2 so you would basically have functions that are called something like add lift remove left add right and remove right sometimes they're called top left pop right or other names but you get the idea you should be able to implement all of those operations in one as well okay so that's my introduction to these three data structures but if you want to practice using these concepts one of the resources i recommend is one of my business affiliates algoexpert.io this is my referral link and this is my discount code cs dojo and there's actually an interesting problem that i found on this website for which you can use one of these concepts so i want to give you a quick introduction to that problem in this problem you're given a string of different types of brackets regular brackets square brackets and curly brackets and you want to write a function that takes a string like this and returns true if the brackets are balanced and false if they're not so what does it mean for these brackets to be balanced to explain that i think the best way to do that would be to give you a bunch of examples this one is balanced because there are square brackets inside and regular brackets outside this is not balanced obviously this is not balanced either because you're trying to close before you open this one's not balanced and this one is not balanced either because these two types of brackets are overlapping anyway you should be able to solve this problem in of and in time where n is the length of the string and of n in space as well anyway uh sorry about the delay again uh i'll try to be you know a little bit faster in my video production in the future but thank you so much for sticking with my video and you know my channel okay thank you as always for watching my videos and i'll see you guys in the next one