Understanding Stacks and Queues

Hey everyone, welcome back to another lecture of the Complete Data Structures Algorithms plus Interview Preparation Bootcamp and we are starting with now Stacks and Queues. This is a very easy topic, it is very easy because it's mostly like implementation based and in the entire bootcamp we have been focused on like what the data structure is, how it works what are its use cases and like how do you optimize it and when to use which data structure and that's what makes this course special that's how i you know uh got so many viewers and subscribers or whatever because they're loving this course so make sure you subscribe and press the bell icon check out com classroom.org the link is in the description uh there you can find all the other amazing courses upcoming boot camps and stuff let's talk about stacks and queues first let's talk about stack then let's talk about queues so stack is something we've already looked at where in recursion so in recursion what happens you make a recursion call right so in recursion something like this happens your function call will go over here this this will call another function call this will go another function call another function call another function call and when this function call is finished it will be popped out of the stack it will be removed from the stack this will be removed this will be removed this will be removed okay i don't have to explain this to you i've created an entire playlist on recursion which is something people have loved so if you want to master recursion if you want to like um if you want to get like um pro pro at recursion or whatever master is not like inclusive naming so if you want to get pro at recursion um you can definitely check that out that playlist you can find it on the same channel let's let's talk about this thing what is happening over here so here you can see that on the left hand side I will put input and on the right hand side I'll put output or let me just shift it a little bit okay let me shift this thing over here in the middle okay so input which thing came in first which function call came in first this one this came in first this came in second you this came inside in this stack data structure this was the third item to be inserted this was the fourth item to be inserted no problem very simple okay let's talk about output which was removed first from the stack data structure which one was removed this one was was removed first this one was removed second this one was removed third this one was removed at the last okay in reality yeah something like that only sound good so here you can see what can we notice over here here we can notice that um what can we notice over here the item that came in at the very first is the last item that will be removed the item that came inside this data structure at the last is the first item that will be removed this is stack la first in last out first in last out first item that was in will be the last item that will be removed i'll go into details of this give me a second and last in first out both are the same thing item that was lastly inserted in the data structure will be the first one to be this is known as stack i'll talk about like you might have confusion how is it working internally it is a stack data structure but what is internally we have only learned about arrays and stuff what is this how does it look like what is it okay so the abstract data types and stuff everything i'll cover in this video itself don't worry we'll actually create our own stack as well and we will also see the stack that is provided by java like collections right but right now focus on what we are doing not how we are doing it okay forget about how we are doing it because that will be covered in this video okay now real world example a real world example is that um when you go to a wedding i love giving wedding examples for some reason all right so when you go to a wedding um plates are stacked on top of the other right you're at a buffet and plates are stacked stacked on one top of the other you know we say plates are stacked that's what it calls by stack right so these are plates like this Stacked for the buffet now whenever you go to take a plate right which which plate would you take? I like oh, this is a red color plate. It's in the middle. I'll take this plate Can you actually do that? There's a risk of all the other plates falling and people will call you like weird, right? So how do people take plates at weddings take the upmost one and when they put plates back they put it just like that first they will put it over here then they'll put it above it above it and then when same people like take plates out of it so you can see the first one that was inserted will be the last one that will be removed right so this is a real life example of stats how stacks work first in last out last in first out okay cool all right okay um that is it yeah so if someone asks you hey in stack if you want to insert an item where does it insert on top you want to insert 10 items insert one by one on top and like hey kunal actually want to remove the middle item somewhere over here i want to remove this one well that's not like the functionality of stacks in stack if you want to remove an item it by default removes the topmost this removal is known as pop the insertion is known as push push in a stack means add one item in the stack pop from the item pop from the stack means shout out dan pop uh pop from the item memes uh remove an item from stack all right i'm coming on the data devops bootcamp in which i'm going to be collaborating with a lot of amazing folks and pop is one of those so shout out to pop popcast pop check it out all right um cool so that's it yeah this is it that's what stacks are now similarly q okay i'll go into the implementation of this after this one and we'll do a lots of nice questions as well and i'll also tell you when to use this infrastructure in questions anyone can teach you implementation and this is something you can find like on so many books also but important thing is when do we use it how do we use it okay what are the custom implementations and now what are the you know we can definitely like use the inbuilt one as well but how can we write it on our own okay that's stack so right now just focus on what we are doing not how we are doing it okay let's let's now move forward and then after that we'll uh write the entire stack class on our own let's talk about q what is q q is also similar to real real life cues when you go to a movie Right? What happens when you go to a movie? Q is there. Not so much anymore because things are now digitalized. But let's, for the sake of the argument, you go to a movie and there's a Q. Or you go to a restaurant, there's a Q, there's a line. And you want to order from that restaurant. Okay? So let's say this is the restaurant, McDonald's or something. okay this is the queue people are standing in line over here okay you want to order something from this stall from this restaurant do you go cut in line do you directly jump into the front no it will cause chaos and people will fight with you like why are you cutting in line this is not a polite thing to do what would a polite person do normally how it happens New person will just come, stand in the back. Same thing happens in metro lines. It doesn't happen in metro lines, but it should. Okay. For the sake of the argument, let's suppose it does. So, you know, when you're in line for checking or whatever, people are standing one behind one another. Not at Rajiv Chow, but anyway. Here you can see that people are standing one behind one another. Okay. Another person wants to take some... something from here they will come back from the line like people say you know go back at the line go back so new people are coming from the end so insertion is happening from the end and which person is going to be removed from the line first the queue first this first person because they came in first it's now their turn they will take their burgers or whatever then they will be Removed. so what happened first person that came in was the first person to go out first in first out fifo or last person to get in will be the last person to get out okay that's it this is this is q that's it we can talk about circular cues dynamic cues and everything we'll cover in this video um but that's q yeah okay q is a sort of a data structure like this where it so follows first in first out last in last out we'll be creating like abstract data types okay what do we mean by that is internally how it's working we don't really care in this course we care because we want to understand how it's working internally but abstract data types have already covered like a little bit about it what it means it means that it is given to us what it does like push will be given to us pop will be given to us internal implementation is hidden from us okay but we will write that internal implementation as well because we love going into the details in this bootcamp okay so let's see this in action first and then i'll show you how it works internally also okay so here you can see if i create an example of stack first let rename this to something like inbuilt examples right so stack is an inbuilt one so stack of type means generics we've already covered generics in object-driven programming if you're not aware of generics check out the object-driven programming playlist so basically it tells that only integer type data will be available in this stack I can say stack is equal to new stack. No problem. A new object is being created of stack in the heap memory. This is in the stack memory. This variable. Okay. And I can say stack dot push. I can insert something like 34. Okay. 45 to 9, 18. Okay. One convention is that whenever something is removed from any data structure, not just stacks and queues, you return the item that is removed. Or you display the item that is removed. So the person knows what is removed. So internally what happens is stack.push actually returns the item. So you can see. It returns an integer because I've set it as integer. So, sorry, pop. Pop returns an integer. over here you can see pop it returns an integer okay generic type so if you set up as integer it will return an integer if you create a stack of strings it will return a string okay so if it is popping the item i can just print it one two three four five items i will remove it five times let's run this okay exactly what we wanted as you can see over here so what happened 34 was inserted no problem in the stack 34 was inter you might be wondering what is this data that looks like this we only know about arrays how arrays work internally in memory and whatever internally this is also arrays only okay cool 34 got inserted 45 got inserted 2 got inserted 9 got inserted and 18 got inserted no problem now when you remove it you're like stack.pop we know that the first item that will be removed will be the last item that was inserted on the top so 18 will be removed that is what is happening first 18 is removed then 9 then 2 45 and then in the end 34 which was the first item that was inserted that's it like kunal if nothing is present in the stack and then you remove something then what will happen see it's given an exception hey you are removing from an empty stack it's not cool all right sound good so that's basically how the stack is implemented so this is something we've already like covered how these things work like generics and new keyword and everything uh in the object imparming playlist if you want to check out how it works internally here you can see stack the constructor push is available over here and pop is available over here and empty and search is available or so on and so forth so many things are available over here stack you know extends the vector class we've learned about this in like uh in the constructions constructors and sorry collections and stuff so here you can see it has a like internally it's itself is a what array okay and when we create our own we will also create it using arrays only like internally this thing that you see on the screen is an array you can imagine it's something like this you can imagine it's stored in the memory something like this in the form of an array 34 45 2 9 18 index number 0 1 2 3 4 so you can see via arrays i am making other data types like stacks like queues like heaps like graphs also hash maps even though we are saying this data structure is a hash map or this is a stack this is a queue internally it is what array so data structures what what what value comes why are we not calling this an array then if internally it's an array because of how it's implemented push and pop why because internally it is an array but i cannot directly modify this array i can't say this thing I can't say something like this. I can't say like object of 0 is equal to something or something like that. I can't do that. Okay, this is not accessible to me. Using this variable, you cannot change the internal internal data type that actually stores the data, the internal array using this. That's what object-oriented programming, you know the principles, abstraction, encapsulation stuff we talked about data hiding and everything. Okay? This is also known as abstract data type. You know push, you know pop. Internally how it's working, we don't care. But we'll see how it works internally. Okay? Users generally don't care. Okay? You only work up to, you care about how it's working. Check out object-oriented programming playlist I've covered this in detail, abstraction, encapsulation and everything. Okay? so that is about like the stacks thing and uh what is the uh time complexity if we talk about it where's the complexity analysis so if we imagine this is an array and you're inserting an element in an array that takes how much amount of time constant and removing constant that's it insert one item remove one item insert one item remove one item okay let's move forward okay now let's talk about the inbuilt um q data structure right and then we'll make it on our own as well i'm just gonna hide this and now we're going to talk about q oops all right one thing i want you to notice over here is that when we talk about q like first element is inserted like people are like getting inserted like this and then getting removed or whatever okay if you reverse this if you imagine that you are like uh you know the line is opposite and you can imagine like okay so basically what is happening is that first item that was inserted so insertion is happening from the back like that and removal is happening from the front like that okay you so insertion is happening from here and removal is happening from the front can you not imagine this as a linked list the implementation this can be like the head every time you need to remove just move the head front we have learnt about linked list isn't this the implementation sort of like a linked list that is what java utilizes So here you can see if I try to create queue. Queue is an interface here. Stack is also, you can see, stack is a class. But Q here is an interface. Okay. Interface we've already covered. It tells us what to do, not how to do it. Okay. I can say integer Q is equal to new. Q will not be available. There is no class called Q. It's only the interface. Like, hey. we have this interface queue and it has some some things like add and offer or remove or pull so many things it had you all know what interfaces are right interfaces basically have some sort of like abstract methods and you have to implement those so internally which is the data type that implements add functionality offer and remove and peak functionalities and all these other things we just discussed it linked list so i can do something like this okay you can see it implements the dq with extends queue this is known as deck uh it's like a doubly ended queue i'll talk more about this afterwards so you can see it extends queue and there we have it all of these are implemented over here okay so now i can say q dot add three q dot add six okay let me just copy paste this thing okay five 19 one knife i remove q dot peak let's say what that does so peak basically you can say it just gets the item but does not remove the item okay the head of this queue let's try to see first item inserted or three so three six five nineteen one first person in the line is three yeah that is true first person in the line is three what if i remove q dot remove 3 will be removed 3 is removed accidentally i debug it never mind 3 is removed i remove it again now 6 will be removed first 3 is removed and 6 is removed okay that's basically q that's how it works right okay so you can see it has a first node and last node the internal implementation of linked list has the head as well and the tail as well that's why it's pretty uh this thing pretty efficient because you can directly add in the back if it does not have any tail you have to traverse the entire linked list something already covered in linked list lecture okay so that's basically about it right and uh let me tell you about deck or dq as well and after that we'll move on to the custom implementation and questions okay so this thing we will be seeing like the internal uh like uh more hands-on stuff when we obviously do questions uh but i want to give you like a little bit of hint as i do in every single video when do we use these stacks and queues and stuff right so simple answer for this is when you want to store the answer so far in questions you know your question get questions like how where you store the answer so far and uh you wanna put some results behind you to use those later on for example right um or you want to have a particular group of elements inside a particular data structure for a period of time such questions and hints and stuff that's when you use like stacks and queues generally okay so when we talk about like uh let's say we talk about reversals okay binary tree traversals and stuff and that will heavily be using stacks and queues one more area in which use you use stacks and queues and stuff like we'll talk about bfs and dfs there we use stacks and queues heavily obviously that will come later on in trees which is obviously after stacks and queues only will be doing trees only that's one place where you use it when you need to convert recursion programs into iteration there also you use stacks and queues okay so these are some use cases where you use stacks and queues obviously it will be much more clear when we do the questions for that keep following the boot camp and i will cover it okay so let's talk about dq or deck it's pronounced as deck so basically the idea is that uh in java or not in java let's say in general what is a dq or deck uh you can insert and remove from both the sides okay so there's a doubly ended queue in the simple queue what was happening you can only insert from the back and you can remove from the front here that is not the case here the counter is on both the sides doesn't make sense uh basically you can insert and remove from both the sides that's as simple as i can tell it simple what is the doubt in that no doubt you can insert from front also back also remove from front also back also anywhere you can insert okay So in Java we have this interface and let's take a look at that interface also. Let me comment this out. Deck interface. So it has a few methods. You can see there's a add first, add last, similar things we did in like linked list. Offer first, offer last, remove, remove last, pull, get first, get last, peek, and first occurrence, last occurrence, so on and so forth. Add. and offer and remove and pull and element and peek or whatever okay so you can find what it what they do but in in simple terms like add you know it adds uh you know it adds in the um in the queue and uh it will throw an illegal state exception if no space is currently available okay when the capacity is restricted so that's add offer on the other hand it will be like uh when the so basically when you are using a capacity restricted deck then this method is generally preferred to the add method why because add method will fail uh to insert an element only by throwing an exception okay so it also does the same thing but uh without violating capacity restrictions okay uh remove on the other hand removes pole on the other hand just you know uh retrieves and uh removes the head of the queue and this removes the head of the queue that is the first element and it will throw an exception if the queue is empty if the deck is empty this will not throw an exception when the deck is empty that's the only difference between these two okay you can find it in the in the what it does internally in details like all the data mentioned over here this basically element it retrieves but does not remove the head of the of the queue okay cool and peak is basically uh the first element of the deck okay and um what else add all basically adds all from like you know arraylist.addall push and pop and whatever cool so that's basically about it but how do we actually make the um object of it so how to create the object what we can do is array deck we can use array deck and taken as integer now what is array deck so array deck class basically provides you know uh us to create an object of the methods that we mentioned in like deck interface you know interface is there so some class should be available over there that implements those interface is methods array deck is available over there So basically it has a resizable array. Okay, let's see what it contains. So here you can find all the information about the resizable array implementation of the deck interface. Okay, so array decks have no capacity restrictions. They grow as necessary. Okay, so you can see the class is likely to be faster than stack when used as a stack and faster than a linked list when used as a queue. This thing. linked list used as a queue this is actually faster than that why because it promotes but promotes like insertion and deletion from both the ends as well okay so you can check out all the description some important points i can mention is like uh as i already mentioned point number one you can add or remove from both the sides and uh null elements are not allowed in this okay uh this is actually not thread safe either okay um it has no capacity restrictions you all know that and we also mentioned that it's faster than linked list and stack okay so that's basically about it so theory does not matter as much as you able to solve that problem and you should be knowing when we will be using deck so when we do trees in that i'll show you a great use of this thing okay sometimes people ask i'll give you a little hint in trees the bfs and dfs folks often asks in interviews like to print left to right right to left or whatever in that case deck really comes in handy so we'll be doing deck uh the use of it um during when we do trees okay so you can say deck dot add something like 89 deck dot you can say add first add last 78 okay you can say deck dot remove remove first or remove last right remove first remove last etc etc cool okay so deck is basically like this in deck you can uh Insert from here also and insert last insert first Delete from here also delete from here also Okay that's basically a DEC or a DQ as many people like to call it Correct pronunciation is DEC okay so that was basically about it and now to the most important part custom implementations let's get it okay so let's move on to like uh writing our own you know stack class so this is a stack class but we are going to write on our own see how a little bit how it works internally so as you can see here the internal data type they have keep an as protected we all know what protected means right so in different packages like you know if it's in a base class you can access or whatever i created an entire table in object to impriming so make sure you check it out you can keep it as a private over here as well if you want because we are not going to be you know going into this much this much depth of creating vector or whatever will directly create stack class only that will not be extending anything so you can give it private also so here basically i'm going to say new java class stack okay or i can call it custom slack or custom stack or something custom stack okay it actually i think refracted this also never mind stack stack custom stack that looks good right okay so we all know that we know internally it has an array inside it like a linked list had a head node or point node itself uh this has array inside it okay let's say we're taking integer you all know about generics we created like generic linked list in the previous lecture so you can do it on your own because that's pretty simple let's look at the basics for now and then after this i'll also do some i'll do a lot more implementations in this i'll show you exceptions dynamic stacks queue circular queue and so on and so forth okay Let's imagine this is not like a dynamic stack. What do we mean by dynamic stack? Something that is not dependent like this is a this is an array it will get full sometimes okay arrays have defined length in that case in this example I'll just throw an error like hey your array is full or whatever okay for that I can take a private static final integer this is a default size default side is less than 10 it's going to be same for all the objects of this custom stack that's why it's static private because i don't want people to change it directly final because i don't want to change it ever myself as well okay sound good and i'm just going to create a constructor i'm going to create a constructor that uh takes in the size it does not take this in it just let's say takes in the size okay so when a custom when a when an object of this stack is being created what should happen let's see what is happening over here so internally the array is like right now empty obviously so when we talk about custom stack we talk about arrays so when an object of stack is created stack stack custom stack stack is equal to new custom stack what should happen obviously an object will be created in heap custom stack object is a stack object inside this stack object i have an array which should be initially empty there should be some default size to this array array should have a default size i'm not using arraylist over here or whatever ArrayList itself internally is an array. You all know this right? Internally it should have some sort of a size. Empty array. This is nothing to worry about, nothing new. It's just literally int array is equal to new int. We have been doing this since array lecture. So basically what I'm trying to say is that this should be something like this.data is equal to what? a new integer array of size that has been passed to you. What if nothing is passed to you? When nothing is passed, I want it to use the default size. And how do we do that? I'll call this with the default size. This particular notation is already covered in Object-20 programming. Calling another constructor with the constructor. Check out the object-driven programming this keyword video. There I have mentioned two use cases for this. One use case for this is to reference the object like the data type and the other use case is to call it as a constructor. So which is a constructor that takes an integer argument? This one, it will call it. It will call this. It will set up a new size of new array of size 10 because that is the default size. If you don't want to use the default size and you pass your own, then this will not be called. Okay. sound good that's basically about it now let's talk about how we are going to maintain the data in this how are we going to insert the data in this let's see so how are we inserting data in the in the array so we have the array now let's say you have we've created a new stack and your array is literally empty size 10. initially like if an integer is there all the all the items are zero something like this we know the index values are 0 1 2 3 4 5 insertion is pretty simple only thing you need to do is you need to maintain a pointer okay initially the pointer will be let's say somewhere over here at minus one when you're like hey i want to insert an item like okay you're actually inserting at the last point of the array right okay you want to insert 30 okay let's say i call this pointer ptr it's gonna be like okay if you want to insert an item increase pointer value by 1 this pointer will be equal to 0 insert the item over here it will be like okay 18 is inserted ptr value is 0 i'll just put it over here ptr value 0 like hey i want to insert another item 30 37 like okay increase the value of this by 1 means index number 1 this is actually acting as an index at index number 1 you have to insert 37 okay 37. when you remove an item you like okay remove the item from this and just decrease the value of ptr ptr will now be equal to again 0. like insert another item 47 okay increase it by 1 add 47 over here this is the pointer thing make sense just using this pointer to go left and right it's always pointing to the last where the last item was added that's what it's pointing to when you want to add a new item increase the value by 1 and add the item over there hence adding an item in the last as i just demonstrated in this example as simple as that all the other checks like if the array is full or if it's throwing any exception or anything can be done basic idea is this right so i can take a pointer i can say int pointer initially is equal to minus one No problem. okay sound good let's push so i'm going to say public int oh no sorry not int boolean we want to know if it was inserted or not int item i'm going to insert an item in this so what do we do to insert an item pointer plus plus and then what add the pointer place the item return true that's it isn't this what we did right now increase the pointer add the item that's it okay but since array may be full sometimes so if the array is already full and you try to access an element that is outside then it will give array out of bound if is full you can create an is full method you can just say return false and print as well stack is full something like that okay you can create is full pretty simple uh is full and say return my pointer is actually equal to equal to data.length means pointer is at last index. If you try to do pointer++ right now, it will go out of bound. Similarly, I can create what is empty. What will be empty? Pause this video, think about it. When will the stack be empty? When pointer is equal to equal to minus one. Make sense? okay now let's push and then i can create a pop also public pop will remove an item of integer type pop okay so pop basically means that uh if it is if it is empty then you can just let's say we throw an exception we can throw an exception okay we've already learned about exceptions we can throw an exception we can say cannot pop from an empty stack something like this okay obviously we have to mention this in the method signature sound good throw and throws the difference between this has been covered in the object-oriented programming playlist otherwise what do we do we return the item removed item will be what data of pointer let me just say pointer minus minus pointer is equal to pointer minus one and then just return the removed item that's it in simple terms you can do it something like this return data of pointer minus minus okay if you want to peak the what is at the top public int peak what is at the top so what do we do just return what is at the top pointer but what if it's empty same thing cannot peek from an empty stack that's it we created our own stack amazing right sound good we created like we learned about custom exceptions so we can create our own exception over here as well stack exception we've learned about exceptions we've learned about custom exception x uh custom exceptions as well you have to extend the exception class over here that's it and you can create a constructor i'm going to select nothing as of now and i'm going to say string message and i'm going to call the parent class if you have doubts in this You definitely have not watched the Object-Owned Programming playlist. stack exception now okay you can have dedicated exception class for your custom slack of stack how cool is that okay let's try to run this and say custom stack stack is equal to new custom stack If I don't provide any size, if I provide any size, I can say initially size is 5 let's say. Internally, first it will create an array of size 5. Means you can only add 5 items. ah because this throws an exception so you have to put it over here as well like okay something is available in this main function that throws stack exception already covered this so should give me the same output 18 9 2 45 34 okay but if you try to remove it one more time then it will give exception cannot pop from an empty stack type stack exception okay covered already you can debug it if you want put a debug pointer over here and debug it a debug pointer over here debug it up to you but it's pretty simple i've debugged it on pen and paper already okay that is basically about it okay but now i may ask kunal that's fine but um you in the original stack it never gets empty sorry it never gets full so how can we do that basically you already know the answer to this we've talked about it in arraylist whenever this data type this array will be full we'll create a new array of twice the size copy all the previous items in this one and then add the item we can do that no problem in that okay so i'll create a dynamic stack this will never be full so since i've already made a lot of things in custom stack i can just extend it make sense i can create a constructor of this as well okay if you don't pass anything it will just call super what is the super going to be what is the constructor in the parent class that does not take any argument this one it will call this please watch object in programming playlist otherwise if you pass a size this will call this one we already talked about super keyword also So, in dynamic stack everything will remain the same. Pop will remain the same, peak will remain same, isFull, isEmpty everything will remain the same. Only problem we are facing is in push. So what can we do? If we want to use the push of this and not of the parent class. Override, override, override the push method. Okay, what do we do when we override this? we just basically say hey if if it is full if this dot is full it's private public is full if it is full double the array size so i can create a temporary array of double the size new integer data.length multiplied by 2. Very simple. You have done recursion and backtracking and this is nothing for you now. Okay. Copy all previous items in new data. Okay. So, for i is equal to 0, i is less than data.length. length and i++ i can say that my temp of i is basically equal to data of i okay you can also enhance it no you can also enhance this by system.array copy okay but for beginners i'll just leave it like that and after that what do we need to do data is equal to temp okay in the end insert item so when i insert item you're like hey this thing takes care of this takes care of it being full so at this point at this point we know that array is not full hence we can insert the item normally super dot push Insert it normal now. It's inserting it normally using this super dot. Please watch out that you're in plumbing I've mentioned what super is already. Okay dynamic stack done That's it. Yeah, so we talk about custom stack and I try to insert one more item It will give error so it I did not throw an error but it gave me like stack is full right i can throw another like uh some error over here if i want to okay i can do that but i just say stack is full your data will not be inserted but 89 or whatever if i do it like dynamic stack then it's inserting it 89 as you can see available over here sound good five items removed and removes all the six items also okay can i put custom stack over here we can do that parent can be used as a type also but uh i in detail mentioned what this represents and what this represents in object-driven programming playlist this means what type of you know um what what all access you can get this thing the type over here means what all access you can get this means what is the type of access that you can get already explained in detail in object-driven programming so please make sure you check out that playlist um it's very in detail explained this line i made a literally an hour long video on just this line i think this should not be a problem now this thing i can uh i can uh write it on whiteboard as well for you all this particular thing this thing the push method if it's being full then what happens so if it's being full means your array is full something like two nine one eight seven it's full your data is equal to it's full so you're gonna be like hey it's full in line number 16 in line number 18 it will create a time of size twice means length 10 so it will create a temp 10 size okay then what will it do uh it will copy all the previous items in the new element so data will be copied over here 2 9 1 8 7 and then in line number 25 data is now pointing to temp so data is now equal to temp okay so data is now equal to this this will be removed by garbage collector this will also be removed by garbage collector it will go out of spoke out of scope why you can see that temp is defined over here so when this is over temp will be removed like over here try to access temp over here you can see you're not able to why it does not exist this also got removed in the end it will just be like data is equal to this thing now it will insert a new item over here 19 and that's it okay new item over here 19 that's it complexity analysis is very simple for this right you can see this is orphan this is full thing but in in on an average it will be amortized constant time we already covered this in array list same same thing goes over here okay rest everything you can see it's pretty simple simple one one line o of n o of one operations okay that was about your dynamic stack very simple okay now let's talk about the internal implementations of queue so in queue also internally it will be a like i can create custom queue i can say new class custom queue okay so q can also have like two pointers because in queue what happens you insert from the last and you remove from the first so you can have two pointers first and last but that's a easy approach you can do that I want to teach you that more not so easy approach where only one pointer is allowed same thing in linked list in linked list you have head and tail but I taught you with the questions that we did were with head only why because that's what they ask in interviews if they give you tail also then even though you know like everything is solved so from the interview standpoint always check out the different like difficult approaches okay first things first custom queue I'm gonna have the same thing okay I can create it as private no worries I can create my default size and my pointer like this okay so let's say pointer is pointing towards the end so that's why I'm calling it right let's try to see how how this will work so I basically do something like this I create the same um copy paste custom queue exactly copy pasting nothing new we're just setting up right now is full and is empty copy pasted oops okay i can call it my end okay and since I'm putting items in the end so what happens in queue what does it happen new items get added in the end okay that's what happens so I'm adding an item and I'm then increasing the end manning an item increasing the end you can also start it from zero if you want here what I was doing what I was doing was I was first increasing it then adding the item but you can also first add the item that in then increase it look a much more cleaner like this something like this make sense so you want to insert in it i'll just copy paste now i'll just create a new one public boolean insert insert an item in it what do we do if is full then i can just say return false otherwise i can say first insert so i can say data of end is equal to item then i can say end plus plus but i can do plus plus over here also you know right that plus plus end and end plus plus are different and plus plus means first it will do what it wanted to do with the end means assign item to it and then it will do and plus plus plus plus end means it will first increment the value of end then assign the item this is same like this okay now i can just say return true insert happens no problem that is it sound good okay see this on like the whiteboard how it's happening actually pretty simple so Q internally it's what internally it's an array custom queue data internally it's an array and something like this you want to insert 34 so 34 basically 0 1 2 3 4 the end basically because we insert from the end always that's why i'm putting at pointer as end initially 0 so insert 34 at 0 okay 34 at 0 increment the value of end 1 now when you want to insert again it will like insert 45 at end 45 will be inserted from here it will be removed 2 so on and so forth when end becomes equal to the size of the array it means it's full how would you remove item from the array how would we do it you have let's say a few items over here okay 3 9 4 18 77 you want to remove the item which item gets removed from the queue first one right so array should look something like this internally after removing one item it should look something like this what did you do you shifted it on the left hand side by one automatically this will be removed that makes sense shifted it to the left hand side by one so when we talk about removing we actually shift it to the left hand side by one what is the complexity of this adding complexity of one because only one step done but in removing your shifting n items so often where n is the size of the element number of elements removal will take o of n time okay we can solve this problem via circular q we'll see we'll see that later on like if this was a circle that would have made things more easy i'll show you that as well okay but for now let's focus on the basics part folks often ask these things okay in interviews so always keep keep track of such things okay So if I want to remove from it, public int remove and this will also throw an exception. Okay, if is empty, I can say throw new exception, Q is empty, something like that. Otherwise, I can say int removed is equal to what first item and in the end i just need to return the item that is removed but we need to shift the elements here okay shift the elements to left from which index will we start shifting the elements index number one or index i is equal to one what is the last element that will be shifted end okay and what do we do over here i can say data of i minus 1 the previous one is equal to the next one make sense in the end and will also be decreased because one item has been removed sound good okay you can also get like public i believe this is clear you start from index number one as you can see over here start from index number one here you're starting from here okay and here in line number 43 you are saying i minus 1 is equal to i means previous is equal to next yeah in the previous position i actually added the next then i will be increased here i will add the next item which is 4 yeah that is true so on and so forth okay now one more uh you can add which is uh equal to just displaying the item what is that front it throws exception copy this otherwise you can just say return data of zero okay that's uh pretty much about it i can create a q main but you can also create like a display function we are not able to display it right so you can create display and uh which is going to be like till end it's going to display so it's just going to be saying that print data of i plus space and in the end just print end or something so in queue main you can say that you'll have public static void main queue custom queue queue is equal to new custom queue let's say five size or something right and then i can say that q dot insert you can just copy from here inbuilt examples q dot add okay and then i can say q dot display so three six five nineteen one end okay that's the queue you wanna make it in a more nice way now you can see okay this person is first sound good you can remove as well see which item was removed q dot remove and then you can do q dot display again so you can see first item will be removed okay three is removed and you can see here three is removed all the other items shifted towards the left one item left so remove actually takes o of n time okay but that's not good for us o of n time just for removing one item yeah not going to we are not happy with that comes into picture let's talk about circular queue now okay so in the previous example in order to remove an element from a queue it was taking o of n time what we can do is we can have like sort of a circular queue structure so internally it will be array only but we can think about it like this let's think about it okay so internally it will be an array only let's say of let's say initially it's of size five okay and it will look something like this let's say we can imagine it something like this okay so here we can imagine one two three four five you can imagine it like this now what is happening over here is we're going to take a few pointers there's going to be a front pointer and an end pointer start and end so let's say front and end are both at the first position right now okay let's say they both are at the first position like the zeroth index right now let's say this is the indices zero one two three four this circle is actually internally a list only like this uh an array basically okay so whenever you want to insert an element obviously an insert an element and at end it will be inserted so you insert an element at the end and you increase the end by one that's it so basically you insert an element in the end so when you insert an element in the end you just insert an element like 8 over here and end will be increased by 1 then you add 9 over here and end will be increased by 1 so on and so forth 8 over here first is over here 9 over here then end is over here make sense very simple stuff okay when you want to remove an element on the other hand what do you do you just increase the value of front by one same thing we'll be doing like in linked list also and like uh array list etc also okay so now font will be moved over here now you're like kunal in reality 8 is not removed from here kunal then how can you say that you are removing an element well we only consider what is in between front and end all the other elements that are available in the list will be overridden when we add it again they will be overridden okay so when you insert another item like 19 and will now come over here 20 and will now come over here 35 now is the real problem like kunal hypothetically this position is empty 8 is over there but it is supposed to be overridden because front lies over here so anything that is not between end and front is empty like this supposed to be empty like when you do this again 19 20 35 kunal how do you reach from 4 to 0 next element to be inserted should be at index number 0. How can I reach from the last element back to 0? If I increase the value of end again, it will be 5. That is index out of bound. It should not be 5. It should be what? It should be 0 back again. What do we use for this? Remainders. Okay. End remainder the size of the array. so 5 modulo 5 is going to be equal to what zero hence it's going to be over here at the zeroth index this modulo size you can imagine as the number of times you have traversed the entire loop this entire loop means the entire array okay so now it will be inserting it over here something like 30 78 or something you insert it over here then let's say you remove one more item obviously item will be removed from front hence this is not the new front now front will always be remaining like this f this is just due to the implementation i put like internally 78 is the front but in reality 78 is the back okay front will always be this you will always read it like this 19 20 35 78 that's how people are standing not 78 empty 19 20 35 no now when you want to insert it again end will again increase by 1 end will now value be equal to 6 so again you will be like 6 modulo 5 is equal to what 1 that's correct you are at index number 1 that is correct index number 1 you will insert something like 199 okay sound good that's basically about it circular array okay so insertion removal takes o of n o of one time over here constant amount of i hope you are able to understand what this model size thing i'm doing with this example it was clear let's code this okay i can create another class i can call it circular q something like that it should have the same um custom queue types and stuff uh okay custom queue and then is full is empty i'm just going to copy paste this be cautious when you're copy pasting sometimes it you know does not look look very nice okay keep this as protected if you that's fine okay uh in default size i need an end and i need a print also initially both are zero so this is uh i'm gonna keep this as protected also okay i'll take a size as well let's maintain a size size is also initially zero uh this is looking good this is also Similar, this is also similar and this time I'm just going to say because end may not be equal to data.length because end will come back to like you know like zero and stuff. That's why I'm taking size over here. Okay, sound good? Now let's try to insert in the array. So insert I'm going to copy paste from here. Okay, so if it is full. then i can just say return false otherwise i can just add the item at the end and i can say end is equal to end modulo the data dot length size of the entire that's it that's the only change also size plus plus because we are taking size that's it as simple as that exactly the same thing we did on whiteboard now in remove We are not required to shift the elements. okay we are not required to shift the elements copy this over here so if it is empty through a new exception and the removed data is equal to data not at zero actually at front okay and in the end you just return the removed data don't need this shift operator now so basically what we are doing is um front is equal to front modulo data dot length and size minus minus and you have to increase front also okay just increase front that's it let's remove as simple as that check out getting the front not data of zero but data of front sound good zero may contain end okay and display as well display will also now not go from zero till end it will go from front till end right but there might be some mistake in uh in display we'll check it when we do when we run it let's see let's see q main if i'm talking about circular queue okay i'm inserting five items initially item and that also are five then i'm displaying it then i'm removing an item and uh let's let's actually you know what draw this to make it uh make it much more clearer so i'm talking about five items should be inserted somewhat like three six five 19 one three six five 19 and one this is my front and this is my like end and now if i try to sorry i try to print this it will be fine but if i remove it so i remove it then front will go over here from at 6 and if i insert one more item let's say 133 and it should print 6 5 19 1 133 i remove an item then i insert an item then i display it again let's try to see let's say i inserted an item after removing it 6 5 19 1 1 33 ah okay so you see what is happening um when i inserted all the items it was something like this let's say so as you can see front and end are both on zero so you should actually do it like um yeah if i just put a debug pointer over here and we debug it after inserting all the items you can see i can go inside this so you can see front is zero and end is also zero make sense so that's why it's not printing anything we have to fix the display function we can do that um we can just display to less than the size and say data dot okay so instead what we can do is that um i can say that start from front till you reach end so if it starts from front it will be like okay zero one two three four five that's it okay while it is not equal to end so if i'm talking about something like this like this and it contains 133 so start from 1 then 2 then 3 then 4 and then 5 so whenever it reaches 5 the I pointer let's say I take an I pointer so I will be equal to 1 it will be like hey print it like 6 and then just increase the value of it I is equal to 2 is 2 equal to end no it's not okay move forward 3 is 3 equal to end no it's not okay print 19 move forward is 4 equal to end no it's not okay print 1 move forward So when i is incremented from 4 to 5 i will again apply this thing i here will again be equal to 5 modulo 5 0 is 0 equal to end no it's not okay print this move forward 6 6 modulo 5 1 is 1 equal to end yes it is terminate that's it okay so we are taking uh an i so i can say i is equal to start from front do this thing what do we want to do i'm going to print whatever is at i okay i want to print that do this thing i++ is also a nice example of do while loop that you have now okay i plus plus and i again modulo equal to what data dot length okay here you can put a check if um is empty you can say empty or something like this okay and here from here you can return if you want while i is not equal to what end and in the end you just say print end and here i'll just say print so it's printing like from front till end like this i will try to display it first let's just try to display this thing run six sorry three six five nine one end that's correct if i remove an item and i insert 133 in it and then i try to display it item should be inserted at the end somewhere over here that is correct because new items are inserted from the end three is removed that's correct absolutely correct it's like six five nineteen one one thirty three 65191133 try to remove it again insert it again and display it again let's try try to see what happens try to let's not insert anything let's just remove something 6 will be removed yeah that's correct uh let's insert something let's insert 99 so 99 will come after 133 obviously that's correct yeah that works complexity o of one not for display obviously display is o of n but for the rest you can see just one single step everything is happening sound good one more thing remaining is what will happen if this is full if this is full then it will be full okay it will return false it will not insert anything so what do we have to do we have to create a dynamic queue dynamic queue is going to be something like dynamic stack where is dynamic stack over here just double the item and everything right so i'm going to create a dynamic queue this is for um so that it does not get full i can extend the circular queue in this okay you can create something like this dynamic queue copy pasting that's it after that i just overwrite overwrite what which one insert okay otherwise in the end just return super insert yeah item that's correct but here just like i did in this if it is full then do something boy paste coil paste so if it is full do something double the size that's correct then i'm just going to say that since it's a circular queue one change that i'll be making is the temp of i is equal to data of what right now it's not going to start from like just i i is like zeroth item not from index number zero it's it's actually zeroth item from front till end this is actually representing the number of items as such so i'm going to say data of what front plus i give like this okay then i can say front is equal to 0 and end is equal to what data dot length because i know it's it's full the array is full that's it that is it so in the end whatever the front and end positions were you know sometimes like in this previous example we saw front can actually be bigger than end initially they start from zero and end is increasing by one but if end represents like comes back then we know that front is actually here in this example as you can see here if i if i remove one more item front will be over here so you can see 2 is actually greater than 1 that's what we're doing over here here you can see i is starting from 0 and it's taking front plus i so it's going to be like front plus i means 2 plus 0 2 plus 1 2 plus 2 2 plus 3 modulo 2 plus 4 modulo how many times it will go data of length times data of length times it's going right and in the new array it's actually adding elements right from zero so in the new element new array it will look something like this after doubling zero one two three four five six seven eight nine you like the zeroth item okay so temp of 0 means 22 is equal to data of 0 no not data of 0 data of front plus i front plus 0 starting from front when you do data of i it means it's starting from 0 itself but we are not starting from 0 itself we're starting from front till end okay so 2 plus 0 modulo 5 which is 2 so whatever is at this index this values second item which is 19 sorry previous example 5 5 will come over here then 2 plus 3 3 modulo 5 is 3 only so 19 then 2 plus i is equal to value 2 2 plus 2 is 4 4 is 4 modulo 5 is 1 1 will come over here then 2 plus i's values is 3 5 5 modulo 5 is what 0 then the 0th index of this array 133 133 will come over here then 2 plus data of length now i is equal to in the for loop of 21 line i is equal to what 4 so 2 plus 4 is 6 modulo 5 is 1 index number 1 6 that will come over here that is correct now i value is 5 5 is actually not less than data dot length hence it will terminate now front will be equal to 0 and will be equal to data dot length front will be over here and will be over here perfect that's it so initially you can see front was greater than end but when i doubled the array it made it into like the normal form like we have seen in previous queue custom queue okay and then you can insert in the like normally as you can see in line number 31 it can insert normally that is basically about it very cool and this is also like o of n and is the number of elements because it's copying all the previous elements right o of n complexity that was it about dynamic queue dynamic stack we talked about deck talked about everything circular queue custom implementation internal implementation and everything uh in the next few videos and this is not over right now see the data structure algorithms bootcamp that i'm doing it there's a pace i cannot do sliding window questions right now because i have not taught you about hash maps if you're watching in the future check out the playlist hash maps would be covered so everything has a time people are like you have done an array of your sliding window no i can't show you that right now you have to know about hash maps and heaps and stuff okay circular qqs and everything will also come in detail when we do more advanced level questions in heaps and stuff and binary trees okay so keep following the playlist and we will reach over there so this is not over right now do you think recursion is over right now absolutely not in in binary trees in trees in general recursion is completely like trees only heaps upheap down heap methods recursion only graph traversals dynamic programming is entirely recursion 90 percent recursion only so even though recursion playlist is done does it mean that in the course recursion is over when did we do arrays we did arrays in the very first lecture our array is over now no we just used arrays in this lecture same thing for queues heaps and all these other things questions will be done quite a lot when we do more complex data structures will we do combinations of questions one questions how it utilizes so many data structures into one that's going to be the highlight of this course so remember how i do like binary search questions like google interview questions cyclic sort linked list google interview questions and amazon and facebook and microsoft interview questions or so on so forth such videos are coming for every data structure as you can see in the past so for this as well and heaps and tp and maps and uh trees everything like we'll have it we'll have like dedicated questions videos as well so this video was about implementations and stuff after this we'll do some stack skews and question video then we'll do trees and you can find the entire syllabus and everything links are in the description assignments and everything have been uploaded make sure you check it out like share and subscribe comment right now and join the dsa like learning public initiative you can check out how you can take part in the description you can use hashtag dsa with kunal on twitter and i'll see you in the next one

There's a risk of all the other plates falling and people will call you like weird, right? So how do people take plates at weddings take the upmost one and when they put plates back they put it just like that first they will put it over here then they'll put it above it above it and then when same people like take plates out of it so you can see the first one that was inserted will be the last one that will be removed right so this is a real life example of stats how stacks work first in last out last in first out okay cool all right okay um that is it yeah so if someone asks you hey in stack if you want to insert an item where does it insert on top you want to insert 10 items insert one by one on top and like hey kunal actually want to remove the middle item somewhere over here i want to remove this one well that's not like the functionality of stacks in stack if you want to remove an item it by default removes the topmost this removal is known as pop the insertion is known as push push in a stack means add one item in the stack pop from the item pop from the stack means shout out dan pop uh pop from the item memes uh remove an item from stack all right i'm coming on the data devops bootcamp in which i'm going to be collaborating with a lot of amazing folks and pop is one of those so shout out to pop popcast pop check it out all right um cool so that's it yeah this is it that's what stacks are now similarly q okay i'll go into the implementation of this after this one and we'll do a lots of nice questions as well and i'll also tell you when to use this infrastructure in questions anyone can teach you implementation and this is something you can find like on so many books also but important thing is when do we use it how do we use it okay what are the custom implementations and now what are the you know we can definitely like use the inbuilt one as well but how can we write it on our own okay that's stack so right now just focus on what we are doing not how we are doing it okay let's let's now move forward and then after that we'll uh write the entire stack class on our own let's talk about q what is q q is also similar to real real life cues when you go to a movie Right? What happens when you go to a movie?

Q is there. Not so much anymore because things are now digitalized. But let's, for the sake of the argument, you go to a movie and there's a Q. Or you go to a restaurant, there's a Q, there's a line. And you want to order from that restaurant.

Okay? So let's say this is the restaurant, McDonald's or something. okay this is the queue people are standing in line over here okay you want to order something from this stall from this restaurant do you go cut in line do you directly jump into the front no it will cause chaos and people will fight with you like why are you cutting in line this is not a polite thing to do what would a polite person do normally how it happens New person will just come, stand in the back. Same thing happens in metro lines.

It doesn't happen in metro lines, but it should. Okay. For the sake of the argument, let's suppose it does. So, you know, when you're in line for checking or whatever, people are standing one behind one another. Not at Rajiv Chow, but anyway.

Here you can see that people are standing one behind one another. Okay. Another person wants to take some...

something from here they will come back from the line like people say you know go back at the line go back so new people are coming from the end so insertion is happening from the end and which person is going to be removed from the line first the queue first this first person because they came in first it's now their turn they will take their burgers or whatever then they will be Removed. so what happened first person that came in was the first person to go out first in first out fifo or last person to get in will be the last person to get out okay that's it this is this is q that's it we can talk about circular cues dynamic cues and everything we'll cover in this video um but that's q yeah okay q is a sort of a data structure like this where it so follows first in first out last in last out we'll be creating like abstract data types okay what do we mean by that is internally how it's working we don't really care in this course we care because we want to understand how it's working internally but abstract data types have already covered like a little bit about it what it means it means that it is given to us what it does like push will be given to us pop will be given to us internal implementation is hidden from us okay but we will write that internal implementation as well because we love going into the details in this bootcamp okay so let's see this in action first and then i'll show you how it works internally also okay so here you can see if i create an example of stack first let rename this to something like inbuilt examples right so stack is an inbuilt one so stack of type means generics we've already covered generics in object-driven programming if you're not aware of generics check out the object-driven programming playlist so basically it tells that only integer type data will be available in this stack I can say stack is equal to new stack. No problem. A new object is being created of stack in the heap memory. This is in the stack memory.

This variable. Okay. And I can say stack dot push. I can insert something like 34. Okay.

45 to 9, 18. Okay. One convention is that whenever something is removed from any data structure, not just stacks and queues, you return the item that is removed. Or you display the item that is removed. So the person knows what is removed. So internally what happens is stack.push actually returns the item.

So you can see. It returns an integer because I've set it as integer. So, sorry, pop.

Pop returns an integer. over here you can see pop it returns an integer okay generic type so if you set up as integer it will return an integer if you create a stack of strings it will return a string okay so if it is popping the item i can just print it one two three four five items i will remove it five times let's run this okay exactly what we wanted as you can see over here so what happened 34 was inserted no problem in the stack 34 was inter you might be wondering what is this data that looks like this we only know about arrays how arrays work internally in memory and whatever internally this is also arrays only okay cool 34 got inserted 45 got inserted 2 got inserted 9 got inserted and 18 got inserted no problem now when you remove it you're like stack.pop we know that the first item that will be removed will be the last item that was inserted on the top so 18 will be removed that is what is happening first 18 is removed then 9 then 2 45 and then in the end 34 which was the first item that was inserted that's it like kunal if nothing is present in the stack and then you remove something then what will happen see it's given an exception hey you are removing from an empty stack it's not cool all right sound good so that's basically how the stack is implemented so this is something we've already like covered how these things work like generics and new keyword and everything uh in the object imparming playlist if you want to check out how it works internally here you can see stack the constructor push is available over here and pop is available over here and empty and search is available or so on and so forth so many things are available over here stack you know extends the vector class we've learned about this in like uh in the constructions constructors and sorry collections and stuff so here you can see it has a like internally it's itself is a what array okay and when we create our own we will also create it using arrays only like internally this thing that you see on the screen is an array you can imagine it's something like this you can imagine it's stored in the memory something like this in the form of an array 34 45 2 9 18 index number 0 1 2 3 4 so you can see via arrays i am making other data types like stacks like queues like heaps like graphs also hash maps even though we are saying this data structure is a hash map or this is a stack this is a queue internally it is what array so data structures what what what value comes why are we not calling this an array then if internally it's an array because of how it's implemented push and pop why because internally it is an array but i cannot directly modify this array i can't say this thing I can't say something like this. I can't say like object of 0 is equal to something or something like that. I can't do that.

Okay, this is not accessible to me. Using this variable, you cannot change the internal internal data type that actually stores the data, the internal array using this. That's what object-oriented programming, you know the principles, abstraction, encapsulation stuff we talked about data hiding and everything.

Okay? This is also known as abstract data type. You know push, you know pop. Internally how it's working, we don't care.

But we'll see how it works internally. Okay? Users generally don't care. Okay? You only work up to, you care about how it's working.

Check out object-oriented programming playlist I've covered this in detail, abstraction, encapsulation and everything. Okay? so that is about like the stacks thing and uh what is the uh time complexity if we talk about it where's the complexity analysis so if we imagine this is an array and you're inserting an element in an array that takes how much amount of time constant and removing constant that's it insert one item remove one item insert one item remove one item okay let's move forward okay now let's talk about the inbuilt um q data structure right and then we'll make it on our own as well i'm just gonna hide this and now we're going to talk about q oops all right one thing i want you to notice over here is that when we talk about q like first element is inserted like people are like getting inserted like this and then getting removed or whatever okay if you reverse this if you imagine that you are like uh you know the line is opposite and you can imagine like okay so basically what is happening is that first item that was inserted so insertion is happening from the back like that and removal is happening from the front like that okay you so insertion is happening from here and removal is happening from the front can you not imagine this as a linked list the implementation this can be like the head every time you need to remove just move the head front we have learnt about linked list isn't this the implementation sort of like a linked list that is what java utilizes So here you can see if I try to create queue.

Queue is an interface here. Stack is also, you can see, stack is a class. But Q here is an interface. Okay. Interface we've already covered.

It tells us what to do, not how to do it. Okay. I can say integer Q is equal to new. Q will not be available. There is no class called Q.

It's only the interface. Like, hey. we have this interface queue and it has some some things like add and offer or remove or pull so many things it had you all know what interfaces are right interfaces basically have some sort of like abstract methods and you have to implement those so internally which is the data type that implements add functionality offer and remove and peak functionalities and all these other things we just discussed it linked list so i can do something like this okay you can see it implements the dq with extends queue this is known as deck uh it's like a doubly ended queue i'll talk more about this afterwards so you can see it extends queue and there we have it all of these are implemented over here okay so now i can say q dot add three q dot add six okay let me just copy paste this thing okay five 19 one knife i remove q dot peak let's say what that does so peak basically you can say it just gets the item but does not remove the item okay the head of this queue let's try to see first item inserted or three so three six five nineteen one first person in the line is three yeah that is true first person in the line is three what if i remove q dot remove 3 will be removed 3 is removed accidentally i debug it never mind 3 is removed i remove it again now 6 will be removed first 3 is removed and 6 is removed okay that's basically q that's how it works right okay so you can see it has a first node and last node the internal implementation of linked list has the head as well and the tail as well that's why it's pretty uh this thing pretty efficient because you can directly add in the back if it does not have any tail you have to traverse the entire linked list something already covered in linked list lecture okay so that's basically about it right and uh let me tell you about deck or dq as well and after that we'll move on to the custom implementation and questions okay so this thing we will be seeing like the internal uh like uh more hands-on stuff when we obviously do questions uh but i want to give you like a little bit of hint as i do in every single video when do we use these stacks and queues and stuff right so simple answer for this is when you want to store the answer so far in questions you know your question get questions like how where you store the answer so far and uh you wanna put some results behind you to use those later on for example right um or you want to have a particular group of elements inside a particular data structure for a period of time such questions and hints and stuff that's when you use like stacks and queues generally okay so when we talk about like uh let's say we talk about reversals okay binary tree traversals and stuff and that will heavily be using stacks and queues one more area in which use you use stacks and queues and stuff like we'll talk about bfs and dfs there we use stacks and queues heavily obviously that will come later on in trees which is obviously after stacks and queues only will be doing trees only that's one place where you use it when you need to convert recursion programs into iteration there also you use stacks and queues okay so these are some use cases where you use stacks and queues obviously it will be much more clear when we do the questions for that keep following the boot camp and i will cover it okay so let's talk about dq or deck it's pronounced as deck so basically the idea is that uh in java or not in java let's say in general what is a dq or deck uh you can insert and remove from both the sides okay so there's a doubly ended queue in the simple queue what was happening you can only insert from the back and you can remove from the front here that is not the case here the counter is on both the sides doesn't make sense uh basically you can insert and remove from both the sides that's as simple as i can tell it simple what is the doubt in that no doubt you can insert from front also back also remove from front also back also anywhere you can insert okay So in Java we have this interface and let's take a look at that interface also.

Let me comment this out. Deck interface. So it has a few methods.

You can see there's a add first, add last, similar things we did in like linked list. Offer first, offer last, remove, remove last, pull, get first, get last, peek, and first occurrence, last occurrence, so on and so forth. Add.

and offer and remove and pull and element and peek or whatever okay so you can find what it what they do but in in simple terms like add you know it adds uh you know it adds in the um in the queue and uh it will throw an illegal state exception if no space is currently available okay when the capacity is restricted so that's add offer on the other hand it will be like uh when the so basically when you are using a capacity restricted deck then this method is generally preferred to the add method why because add method will fail uh to insert an element only by throwing an exception okay so it also does the same thing but uh without violating capacity restrictions okay uh remove on the other hand removes pole on the other hand just you know uh retrieves and uh removes the head of the queue and this removes the head of the queue that is the first element and it will throw an exception if the queue is empty if the deck is empty this will not throw an exception when the deck is empty that's the only difference between these two okay you can find it in the in the what it does internally in details like all the data mentioned over here this basically element it retrieves but does not remove the head of the of the queue okay cool and peak is basically uh the first element of the deck okay and um what else add all basically adds all from like you know arraylist.addall push and pop and whatever cool so that's basically about it but how do we actually make the um object of it so how to create the object what we can do is array deck we can use array deck and taken as integer now what is array deck so array deck class basically provides you know uh us to create an object of the methods that we mentioned in like deck interface you know interface is there so some class should be available over there that implements those interface is methods array deck is available over there So basically it has a resizable array. Okay, let's see what it contains. So here you can find all the information about the resizable array implementation of the deck interface. Okay, so array decks have no capacity restrictions.

They grow as necessary. Okay, so you can see the class is likely to be faster than stack when used as a stack and faster than a linked list when used as a queue. This thing.

linked list used as a queue this is actually faster than that why because it promotes but promotes like insertion and deletion from both the ends as well okay so you can check out all the description some important points i can mention is like uh as i already mentioned point number one you can add or remove from both the sides and uh null elements are not allowed in this okay uh this is actually not thread safe either okay um it has no capacity restrictions you all know that and we also mentioned that it's faster than linked list and stack okay so that's basically about it so theory does not matter as much as you able to solve that problem and you should be knowing when we will be using deck so when we do trees in that i'll show you a great use of this thing okay sometimes people ask i'll give you a little hint in trees the bfs and dfs folks often asks in interviews like to print left to right right to left or whatever in that case deck really comes in handy so we'll be doing deck uh the use of it um during when we do trees okay so you can say deck dot add something like 89 deck dot you can say add first add last 78 okay you can say deck dot remove remove first or remove last right remove first remove last etc etc cool okay so deck is basically like this in deck you can uh Insert from here also and insert last insert first Delete from here also delete from here also Okay that's basically a DEC or a DQ as many people like to call it Correct pronunciation is DEC okay so that was basically about it and now to the most important part custom implementations let's get it okay so let's move on to like uh writing our own you know stack class so this is a stack class but we are going to write on our own see how a little bit how it works internally so as you can see here the internal data type they have keep an as protected we all know what protected means right so in different packages like you know if it's in a base class you can access or whatever i created an entire table in object to impriming so make sure you check it out you can keep it as a private over here as well if you want because we are not going to be you know going into this much this much depth of creating vector or whatever will directly create stack class only that will not be extending anything so you can give it private also so here basically i'm going to say new java class stack okay or i can call it custom slack or custom stack or something custom stack okay it actually i think refracted this also never mind stack stack custom stack that looks good right okay so we all know that we know internally it has an array inside it like a linked list had a head node or point node itself uh this has array inside it okay let's say we're taking integer you all know about generics we created like generic linked list in the previous lecture so you can do it on your own because that's pretty simple let's look at the basics for now and then after this i'll also do some i'll do a lot more implementations in this i'll show you exceptions dynamic stacks queue circular queue and so on and so forth okay Let's imagine this is not like a dynamic stack. What do we mean by dynamic stack? Something that is not dependent like this is a this is an array it will get full sometimes okay arrays have defined length in that case in this example I'll just throw an error like hey your array is full or whatever okay for that I can take a private static final integer this is a default size default side is less than 10 it's going to be same for all the objects of this custom stack that's why it's static private because i don't want people to change it directly final because i don't want to change it ever myself as well okay sound good and i'm just going to create a constructor i'm going to create a constructor that uh takes in the size it does not take this in it just let's say takes in the size okay so when a custom when a when an object of this stack is being created what should happen let's see what is happening over here so internally the array is like right now empty obviously so when we talk about custom stack we talk about arrays so when an object of stack is created stack stack custom stack stack is equal to new custom stack what should happen obviously an object will be created in heap custom stack object is a stack object inside this stack object i have an array which should be initially empty there should be some default size to this array array should have a default size i'm not using arraylist over here or whatever ArrayList itself internally is an array.

You all know this right? Internally it should have some sort of a size. Empty array. This is nothing to worry about, nothing new.

It's just literally int array is equal to new int. We have been doing this since array lecture. So basically what I'm trying to say is that this should be something like this.data is equal to what?

a new integer array of size that has been passed to you. What if nothing is passed to you? When nothing is passed, I want it to use the default size. And how do we do that?

I'll call this with the default size. This particular notation is already covered in Object-20 programming. Calling another constructor with the constructor. Check out the object-driven programming this keyword video.

There I have mentioned two use cases for this. One use case for this is to reference the object like the data type and the other use case is to call it as a constructor. So which is a constructor that takes an integer argument?

This one, it will call it. It will call this. It will set up a new size of new array of size 10 because that is the default size. If you don't want to use the default size and you pass your own, then this will not be called.

Okay. sound good that's basically about it now let's talk about how we are going to maintain the data in this how are we going to insert the data in this let's see so how are we inserting data in the in the array so we have the array now let's say you have we've created a new stack and your array is literally empty size 10. initially like if an integer is there all the all the items are zero something like this we know the index values are 0 1 2 3 4 5 insertion is pretty simple only thing you need to do is you need to maintain a pointer okay initially the pointer will be let's say somewhere over here at minus one when you're like hey i want to insert an item like okay you're actually inserting at the last point of the array right okay you want to insert 30 okay let's say i call this pointer ptr it's gonna be like okay if you want to insert an item increase pointer value by 1 this pointer will be equal to 0 insert the item over here it will be like okay 18 is inserted ptr value is 0 i'll just put it over here ptr value 0 like hey i want to insert another item 30 37 like okay increase the value of this by 1 means index number 1 this is actually acting as an index at index number 1 you have to insert 37 okay 37. when you remove an item you like okay remove the item from this and just decrease the value of ptr ptr will now be equal to again 0. like insert another item 47 okay increase it by 1 add 47 over here this is the pointer thing make sense just using this pointer to go left and right it's always pointing to the last where the last item was added that's what it's pointing to when you want to add a new item increase the value by 1 and add the item over there hence adding an item in the last as i just demonstrated in this example as simple as that all the other checks like if the array is full or if it's throwing any exception or anything can be done basic idea is this right so i can take a pointer i can say int pointer initially is equal to minus one No problem. okay sound good let's push so i'm going to say public int oh no sorry not int boolean we want to know if it was inserted or not int item i'm going to insert an item in this so what do we do to insert an item pointer plus plus and then what add the pointer place the item return true that's it isn't this what we did right now increase the pointer add the item that's it okay but since array may be full sometimes so if the array is already full and you try to access an element that is outside then it will give array out of bound if is full you can create an is full method you can just say return false and print as well stack is full something like that okay you can create is full pretty simple uh is full and say return my pointer is actually equal to equal to data.length means pointer is at last index. If you try to do pointer++ right now, it will go out of bound. Similarly, I can create what is empty.

What will be empty? Pause this video, think about it. When will the stack be empty?

When pointer is equal to equal to minus one. Make sense? okay now let's push and then i can create a pop also public pop will remove an item of integer type pop okay so pop basically means that uh if it is if it is empty then you can just let's say we throw an exception we can throw an exception okay we've already learned about exceptions we can throw an exception we can say cannot pop from an empty stack something like this okay obviously we have to mention this in the method signature sound good throw and throws the difference between this has been covered in the object-oriented programming playlist otherwise what do we do we return the item removed item will be what data of pointer let me just say pointer minus minus pointer is equal to pointer minus one and then just return the removed item that's it in simple terms you can do it something like this return data of pointer minus minus okay if you want to peak the what is at the top public int peak what is at the top so what do we do just return what is at the top pointer but what if it's empty same thing cannot peek from an empty stack that's it we created our own stack amazing right sound good we created like we learned about custom exceptions so we can create our own exception over here as well stack exception we've learned about exceptions we've learned about custom exception x uh custom exceptions as well you have to extend the exception class over here that's it and you can create a constructor i'm going to select nothing as of now and i'm going to say string message and i'm going to call the parent class if you have doubts in this You definitely have not watched the Object-Owned Programming playlist.

stack exception now okay you can have dedicated exception class for your custom slack of stack how cool is that okay let's try to run this and say custom stack stack is equal to new custom stack If I don't provide any size, if I provide any size, I can say initially size is 5 let's say. Internally, first it will create an array of size 5. Means you can only add 5 items. ah because this throws an exception so you have to put it over here as well like okay something is available in this main function that throws stack exception already covered this so should give me the same output 18 9 2 45 34 okay but if you try to remove it one more time then it will give exception cannot pop from an empty stack type stack exception okay covered already you can debug it if you want put a debug pointer over here and debug it a debug pointer over here debug it up to you but it's pretty simple i've debugged it on pen and paper already okay that is basically about it okay but now i may ask kunal that's fine but um you in the original stack it never gets empty sorry it never gets full so how can we do that basically you already know the answer to this we've talked about it in arraylist whenever this data type this array will be full we'll create a new array of twice the size copy all the previous items in this one and then add the item we can do that no problem in that okay so i'll create a dynamic stack this will never be full so since i've already made a lot of things in custom stack i can just extend it make sense i can create a constructor of this as well okay if you don't pass anything it will just call super what is the super going to be what is the constructor in the parent class that does not take any argument this one it will call this please watch object in programming playlist otherwise if you pass a size this will call this one we already talked about super keyword also So, in dynamic stack everything will remain the same.

Pop will remain the same, peak will remain same, isFull, isEmpty everything will remain the same. Only problem we are facing is in push. So what can we do? If we want to use the push of this and not of the parent class.

Override, override, override the push method. Okay, what do we do when we override this? we just basically say hey if if it is full if this dot is full it's private public is full if it is full double the array size so i can create a temporary array of double the size new integer data.length multiplied by 2. Very simple.

You have done recursion and backtracking and this is nothing for you now. Okay. Copy all previous items in new data. Okay. So, for i is equal to 0, i is less than data.length.

length and i++ i can say that my temp of i is basically equal to data of i okay you can also enhance it no you can also enhance this by system.array copy okay but for beginners i'll just leave it like that and after that what do we need to do data is equal to temp okay in the end insert item so when i insert item you're like hey this thing takes care of this takes care of it being full so at this point at this point we know that array is not full hence we can insert the item normally super dot push Insert it normal now. It's inserting it normally using this super dot. Please watch out that you're in plumbing I've mentioned what super is already. Okay dynamic stack done That's it.

Yeah, so we talk about custom stack and I try to insert one more item It will give error so it I did not throw an error but it gave me like stack is full right i can throw another like uh some error over here if i want to okay i can do that but i just say stack is full your data will not be inserted but 89 or whatever if i do it like dynamic stack then it's inserting it 89 as you can see available over here sound good five items removed and removes all the six items also okay can i put custom stack over here we can do that parent can be used as a type also but uh i in detail mentioned what this represents and what this represents in object-driven programming playlist this means what type of you know um what what all access you can get this thing the type over here means what all access you can get this means what is the type of access that you can get already explained in detail in object-driven programming so please make sure you check out that playlist um it's very in detail explained this line i made a literally an hour long video on just this line i think this should not be a problem now this thing i can uh i can uh write it on whiteboard as well for you all this particular thing this thing the push method if it's being full then what happens so if it's being full means your array is full something like two nine one eight seven it's full your data is equal to it's full so you're gonna be like hey it's full in line number 16 in line number 18 it will create a time of size twice means length 10 so it will create a temp 10 size okay then what will it do uh it will copy all the previous items in the new element so data will be copied over here 2 9 1 8 7 and then in line number 25 data is now pointing to temp so data is now equal to temp okay so data is now equal to this this will be removed by garbage collector this will also be removed by garbage collector it will go out of spoke out of scope why you can see that temp is defined over here so when this is over temp will be removed like over here try to access temp over here you can see you're not able to why it does not exist this also got removed in the end it will just be like data is equal to this thing now it will insert a new item over here 19 and that's it okay new item over here 19 that's it complexity analysis is very simple for this right you can see this is orphan this is full thing but in in on an average it will be amortized constant time we already covered this in array list same same thing goes over here okay rest everything you can see it's pretty simple simple one one line o of n o of one operations okay that was about your dynamic stack very simple okay now let's talk about the internal implementations of queue so in queue also internally it will be a like i can create custom queue i can say new class custom queue okay so q can also have like two pointers because in queue what happens you insert from the last and you remove from the first so you can have two pointers first and last but that's a easy approach you can do that I want to teach you that more not so easy approach where only one pointer is allowed same thing in linked list in linked list you have head and tail but I taught you with the questions that we did were with head only why because that's what they ask in interviews if they give you tail also then even though you know like everything is solved so from the interview standpoint always check out the different like difficult approaches okay first things first custom queue I'm gonna have the same thing okay I can create it as private no worries I can create my default size and my pointer like this okay so let's say pointer is pointing towards the end so that's why I'm calling it right let's try to see how how this will work so I basically do something like this I create the same um copy paste custom queue exactly copy pasting nothing new we're just setting up right now is full and is empty copy pasted oops okay i can call it my end okay and since I'm putting items in the end so what happens in queue what does it happen new items get added in the end okay that's what happens so I'm adding an item and I'm then increasing the end manning an item increasing the end you can also start it from zero if you want here what I was doing what I was doing was I was first increasing it then adding the item but you can also first add the item that in then increase it look a much more cleaner like this something like this make sense so you want to insert in it i'll just copy paste now i'll just create a new one public boolean insert insert an item in it what do we do if is full then i can just say return false otherwise i can say first insert so i can say data of end is equal to item then i can say end plus plus but i can do plus plus over here also you know right that plus plus end and end plus plus are different and plus plus means first it will do what it wanted to do with the end means assign item to it and then it will do and plus plus plus plus end means it will first increment the value of end then assign the item this is same like this okay now i can just say return true insert happens no problem that is it sound good okay see this on like the whiteboard how it's happening actually pretty simple so Q internally it's what internally it's an array custom queue data internally it's an array and something like this you want to insert 34 so 34 basically 0 1 2 3 4 the end basically because we insert from the end always that's why i'm putting at pointer as end initially 0 so insert 34 at 0 okay 34 at 0 increment the value of end 1 now when you want to insert again it will like insert 45 at end 45 will be inserted from here it will be removed 2 so on and so forth when end becomes equal to the size of the array it means it's full how would you remove item from the array how would we do it you have let's say a few items over here okay 3 9 4 18 77 you want to remove the item which item gets removed from the queue first one right so array should look something like this internally after removing one item it should look something like this what did you do you shifted it on the left hand side by one automatically this will be removed that makes sense shifted it to the left hand side by one so when we talk about removing we actually shift it to the left hand side by one what is the complexity of this adding complexity of one because only one step done but in removing your shifting n items so often where n is the size of the element number of elements removal will take o of n time okay we can solve this problem via circular q we'll see we'll see that later on like if this was a circle that would have made things more easy i'll show you that as well okay but for now let's focus on the basics part folks often ask these things okay in interviews so always keep keep track of such things okay So if I want to remove from it, public int remove and this will also throw an exception. Okay, if is empty, I can say throw new exception, Q is empty, something like that. Otherwise, I can say int removed is equal to what first item and in the end i just need to return the item that is removed but we need to shift the elements here okay shift the elements to left from which index will we start shifting the elements index number one or index i is equal to one what is the last element that will be shifted end okay and what do we do over here i can say data of i minus 1 the previous one is equal to the next one make sense in the end and will also be decreased because one item has been removed sound good okay you can also get like public i believe this is clear you start from index number one as you can see over here start from index number one here you're starting from here okay and here in line number 43 you are saying i minus 1 is equal to i means previous is equal to next yeah in the previous position i actually added the next then i will be increased here i will add the next item which is 4 yeah that is true so on and so forth okay now one more uh you can add which is uh equal to just displaying the item what is that front it throws exception copy this otherwise you can just say return data of zero okay that's uh pretty much about it i can create a q main but you can also create like a display function we are not able to display it right so you can create display and uh which is going to be like till end it's going to display so it's just going to be saying that print data of i plus space and in the end just print end or something so in queue main you can say that you'll have public static void main queue custom queue queue is equal to new custom queue let's say five size or something right and then i can say that q dot insert you can just copy from here inbuilt examples q dot add okay and then i can say q dot display so three six five nineteen one end okay that's the queue you wanna make it in a more nice way now you can see okay this person is first sound good you can remove as well see which item was removed q dot remove and then you can do q dot display again so you can see first item will be removed okay three is removed and you can see here three is removed all the other items shifted towards the left one item left so remove actually takes o of n time okay but that's not good for us o of n time just for removing one item yeah not going to we are not happy with that comes into picture let's talk about circular queue now okay so in the previous example in order to remove an element from a queue it was taking o of n time what we can do is we can have like sort of a circular queue structure so internally it will be array only but we can think about it like this let's think about it okay so internally it will be an array only let's say of let's say initially it's of size five okay and it will look something like this let's say we can imagine it something like this okay so here we can imagine one two three four five you can imagine it like this now what is happening over here is we're going to take a few pointers there's going to be a front pointer and an end pointer start and end so let's say front and end are both at the first position right now okay let's say they both are at the first position like the zeroth index right now let's say this is the indices zero one two three four this circle is actually internally a list only like this uh an array basically okay so whenever you want to insert an element obviously an insert an element and at end it will be inserted so you insert an element at the end and you increase the end by one that's it so basically you insert an element in the end so when you insert an element in the end you just insert an element like 8 over here and end will be increased by 1 then you add 9 over here and end will be increased by 1 so on and so forth 8 over here first is over here 9 over here then end is over here make sense very simple stuff okay when you want to remove an element on the other hand what do you do you just increase the value of front by one same thing we'll be doing like in linked list also and like uh array list etc also okay so now font will be moved over here now you're like kunal in reality 8 is not removed from here kunal then how can you say that you are removing an element well we only consider what is in between front and end all the other elements that are available in the list will be overridden when we add it again they will be overridden okay so when you insert another item like 19 and will now come over here 20 and will now come over here 35 now is the real problem like kunal hypothetically this position is empty 8 is over there but it is supposed to be overridden because front lies over here so anything that is not between end and front is empty like this supposed to be empty like when you do this again 19 20 35 kunal how do you reach from 4 to 0 next element to be inserted should be at index number 0. How can I reach from the last element back to 0?

If I increase the value of end again, it will be 5. That is index out of bound. It should not be 5. It should be what? It should be 0 back again. What do we use for this? Remainders.

Okay. End remainder the size of the array. so 5 modulo 5 is going to be equal to what zero hence it's going to be over here at the zeroth index this modulo size you can imagine as the number of times you have traversed the entire loop this entire loop means the entire array okay so now it will be inserting it over here something like 30 78 or something you insert it over here then let's say you remove one more item obviously item will be removed from front hence this is not the new front now front will always be remaining like this f this is just due to the implementation i put like internally 78 is the front but in reality 78 is the back okay front will always be this you will always read it like this 19 20 35 78 that's how people are standing not 78 empty 19 20 35 no now when you want to insert it again end will again increase by 1 end will now value be equal to 6 so again you will be like 6 modulo 5 is equal to what 1 that's correct you are at index number 1 that is correct index number 1 you will insert something like 199 okay sound good that's basically about it circular array okay so insertion removal takes o of n o of one time over here constant amount of i hope you are able to understand what this model size thing i'm doing with this example it was clear let's code this okay i can create another class i can call it circular q something like that it should have the same um custom queue types and stuff uh okay custom queue and then is full is empty i'm just going to copy paste this be cautious when you're copy pasting sometimes it you know does not look look very nice okay keep this as protected if you that's fine okay uh in default size i need an end and i need a print also initially both are zero so this is uh i'm gonna keep this as protected also okay i'll take a size as well let's maintain a size size is also initially zero uh this is looking good this is also Similar, this is also similar and this time I'm just going to say because end may not be equal to data.length because end will come back to like you know like zero and stuff.

That's why I'm taking size over here. Okay, sound good? Now let's try to insert in the array. So insert I'm going to copy paste from here. Okay, so if it is full.

then i can just say return false otherwise i can just add the item at the end and i can say end is equal to end modulo the data dot length size of the entire that's it that's the only change also size plus plus because we are taking size that's it as simple as that exactly the same thing we did on whiteboard now in remove We are not required to shift the elements. okay we are not required to shift the elements copy this over here so if it is empty through a new exception and the removed data is equal to data not at zero actually at front okay and in the end you just return the removed data don't need this shift operator now so basically what we are doing is um front is equal to front modulo data dot length and size minus minus and you have to increase front also okay just increase front that's it let's remove as simple as that check out getting the front not data of zero but data of front sound good zero may contain end okay and display as well display will also now not go from zero till end it will go from front till end right but there might be some mistake in uh in display we'll check it when we do when we run it let's see let's see q main if i'm talking about circular queue okay i'm inserting five items initially item and that also are five then i'm displaying it then i'm removing an item and uh let's let's actually you know what draw this to make it uh make it much more clearer so i'm talking about five items should be inserted somewhat like three six five 19 one three six five 19 and one this is my front and this is my like end and now if i try to sorry i try to print this it will be fine but if i remove it so i remove it then front will go over here from at 6 and if i insert one more item let's say 133 and it should print 6 5 19 1 133 i remove an item then i insert an item then i display it again let's try to see let's say i inserted an item after removing it 6 5 19 1 1 33 ah okay so you see what is happening um when i inserted all the items it was something like this let's say so as you can see front and end are both on zero so you should actually do it like um yeah if i just put a debug pointer over here and we debug it after inserting all the items you can see i can go inside this so you can see front is zero and end is also zero make sense so that's why it's not printing anything we have to fix the display function we can do that um we can just display to less than the size and say data dot okay so instead what we can do is that um i can say that start from front till you reach end so if it starts from front it will be like okay zero one two three four five that's it okay while it is not equal to end so if i'm talking about something like this like this and it contains 133 so start from 1 then 2 then 3 then 4 and then 5 so whenever it reaches 5 the I pointer let's say I take an I pointer so I will be equal to 1 it will be like hey print it like 6 and then just increase the value of it I is equal to 2 is 2 equal to end no it's not okay move forward 3 is 3 equal to end no it's not okay print 19 move forward is 4 equal to end no it's not okay print 1 move forward So when i is incremented from 4 to 5 i will again apply this thing i here will again be equal to 5 modulo 5 0 is 0 equal to end no it's not okay print this move forward 6 6 modulo 5 1 is 1 equal to end yes it is terminate that's it okay so we are taking uh an i so i can say i is equal to start from front do this thing what do we want to do i'm going to print whatever is at i okay i want to print that do this thing i++ is also a nice example of do while loop that you have now okay i plus plus and i again modulo equal to what data dot length okay here you can put a check if um is empty you can say empty or something like this okay and here from here you can return if you want while i is not equal to what end and in the end you just say print end and here i'll just say print so it's printing like from front till end like this i will try to display it first let's just try to display this thing run six sorry three six five nine one end that's correct if i remove an item and i insert 133 in it and then i try to display it item should be inserted at the end somewhere over here that is correct because new items are inserted from the end three is removed that's correct absolutely correct it's like six five nineteen one one thirty three 65191133 try to remove it again insert it again and display it again let's try try to see what happens try to let's not insert anything let's just remove something 6 will be removed yeah that's correct uh let's insert something let's insert 99 so 99 will come after 133 obviously that's correct yeah that works complexity o of one not for display obviously display is o of n but for the rest you can see just one single step everything is happening sound good one more thing remaining is what will happen if this is full if this is full then it will be full okay it will return false it will not insert anything so what do we have to do we have to create a dynamic queue dynamic queue is going to be something like dynamic stack where is dynamic stack over here just double the item and everything right so i'm going to create a dynamic queue this is for um so that it does not get full i can extend the circular queue in this okay you can create something like this dynamic queue copy pasting that's it after that i just overwrite overwrite what which one insert okay otherwise in the end just return super insert yeah item that's correct but here just like i did in this if it is full then do something boy paste coil paste so if it is full do something double the size that's correct then i'm just going to say that since it's a circular queue one change that i'll be making is the temp of i is equal to data of what right now it's not going to start from like just i i is like zeroth item not from index number zero it's it's actually zeroth item from front till end this is actually representing the number of items as such so i'm going to say data of what front plus i give like this okay then i can say front is equal to 0 and end is equal to what data dot length because i know it's it's full the array is full that's it that is it so in the end whatever the front and end positions were you know sometimes like in this previous example we saw front can actually be bigger than end initially they start from zero and end is increasing by one but if end represents like comes back then we know that front is actually here in this example as you can see here if i if i remove one more item front will be over here so you can see 2 is actually greater than 1 that's what we're doing over here here you can see i is starting from 0 and it's taking front plus i so it's going to be like front plus i means 2 plus 0 2 plus 1 2 plus 2 2 plus 3 modulo 2 plus 4 modulo how many times it will go data of length times data of length times it's going right and in the new array it's actually adding elements right from zero so in the new element new array it will look something like this after doubling zero one two three four five six seven eight nine you like the zeroth item okay so temp of 0 means 22 is equal to data of 0 no not data of 0 data of front plus i front plus 0 starting from front when you do data of i it means it's starting from 0 itself but we are not starting from 0 itself we're starting from front till end okay so 2 plus 0 modulo 5 which is 2 so whatever is at this index this values second item which is 19 sorry previous example 5 5 will come over here then 2 plus 3 3 modulo 5 is 3 only so 19 then 2 plus i is equal to value 2 2 plus 2 is 4 4 is 4 modulo 5 is 1 1 will come over here then 2 plus i's values is 3 5 5 modulo 5 is what 0 then the 0th index of this array 133 133 will come over here then 2 plus data of length now i is equal to in the for loop of 21 line i is equal to what 4 so 2 plus 4 is 6 modulo 5 is 1 index number 1 6 that will come over here that is correct now i value is 5 5 is actually not less than data dot length hence it will terminate now front will be equal to 0 and will be equal to data dot length front will be over here and will be over here perfect that's it so initially you can see front was greater than end but when i doubled the array it made it into like the normal form like we have seen in previous queue custom queue okay and then you can insert in the like normally as you can see in line number 31 it can insert normally that is basically about it very cool and this is also like o of n and is the number of elements because it's copying all the previous elements right o of n complexity that was it about dynamic queue dynamic stack we talked about deck talked about everything circular queue custom implementation internal implementation and everything uh in the next few videos and this is not over right now see the data structure algorithms bootcamp that i'm doing it there's a pace i cannot do sliding window questions right now because i have not taught you about hash maps if you're watching in the future check out the playlist hash maps would be covered so everything has a time people are like you have done an array of your sliding window no i can't show you that right now you have to know about hash maps and heaps and stuff okay circular qqs and everything will also come in detail when we do more advanced level questions in heaps and stuff and binary trees okay so keep following the playlist and we will reach over there so this is not over right now do you think recursion is over right now absolutely not in in binary trees in trees in general recursion is completely like trees only heaps upheap down heap methods recursion only graph traversals dynamic programming is entirely recursion 90 percent recursion only so even though recursion playlist is done does it mean that in the course recursion is over when did we do arrays we did arrays in the very first lecture our array is over now no we just used arrays in this lecture same thing for queues heaps and all these other things questions will be done quite a lot when we do more complex data structures will we do combinations of questions one questions how it utilizes so many data structures into one that's going to be the highlight of this course so remember how i do like binary search questions like google interview questions cyclic sort linked list google interview questions and amazon and facebook and microsoft interview questions or so on so forth such videos are coming for every data structure as you can see in the past so for this as well and heaps and tp and maps and uh trees everything like we'll have it we'll have like dedicated questions videos as well so this video was about implementations and stuff after this we'll do some stack skews and question video then we'll do trees and you can find the entire syllabus and everything links are in the description assignments and everything have been uploaded make sure you check it out like share and subscribe comment right now and join the dsa like learning public initiative you can check out how you can take part in the description you can use hashtag dsa with kunal on twitter and i'll see you in the next one

Transcript for:Understanding Stacks and Queues

Transcript for:
Understanding Stacks and Queues