so with this video we will be starting off with the stack and Q playlist again this is a continuation of the sters a toz DSA course if you haven't checked it out yet you're missing out on something so I'll be leaving out the link in the description make sure you check it out but if we starting off the normal thing hey everyone welcome back to the channel I hope you guys are doing extremely well so this will be an introductory video about stack and Q and what all will I be covering up I'll be covering up what is a stack and what is a q I'll be implementing stack and Q using arrays I'll be implementing stack and Q using link list after that I'll be implementing stack using Q after that I'll be implementing a queue using a stack so the first thing what is a stack stack is nothing but a data structure that holds a certain kind of data a certain kind of data that if you get into complex prob you can store multiple kinds as well I'll not get into that complex stuff as of now as of now just understand stack is a data structure that holds a certain type of data it can be integer it can be a pair it can be a double it can be a long it can be a character it can be a string it can be anything it can be a customized type as well right if you want to store multiple then you'll have to go through the complex thing of custom customizing the data types I'll not get into that so the stack data structure follows the Lio mechanism now what is the Lio mechanism that's nothing but last L for last n i for n first f for first out o for out last in first out mechanism let's understand so the stack provides you with four different functions first one is the push function a lot of places you'll find it as the add function as well push a certain value this value can be an integer a pair a double can be a customized data type as well it also gives you an option to pop out the element I'll explain you this one as well it also gives you an option to get the topmost element in the data structure it also gives you an option to get the size of this particular like how many elements are are there in this particular data structure so I'll be writing certain functions and on the basis of that I'll be understanding the stack data structure so I'll be writing down uh push let's say push two push three push four push one and then I say pop and then I say top then I say again top then I say pop and I say pop then I say size probably I can do some different thing probably let's do a push over here again push of five and then do a top and then let's do a size yeah that should be perfect let's understand how this data structure works so on your brain you can think that it's a container yes it is a container which is storing values of any particular data type that you're assigning it okay first of all I'm asking you to push a value two so let's play with integers if you understand with integers you can then expand it to other data types so I'm asking you to push two into the stack data structure like okay I'll take two perfect after that I'm asking you to push three into the stack data structure perfect I'll take that after that I'm asking you to push four okay I'll take it after that I'm asking you to push one okay if I ask you which one was the last element pushed into the stack data stru you'll be like this one this is the last element pushed correct okay so when I say pop pop always takes out the last element pop always takes out the last element which was the last element that was pushed into the stack data structure one so what will happen is it will end up taking out that one after that if I say top it always gives you the last remember last in first out so one is gone one is gone so now which one is the last one four so the top will give you four remember it will not delet it it will just give you four okay after that I'm again asking you top since it is not deleted it will again give you four after that I'm asking you to pop out if I pop out what will happen is the four will be gone four will be gone after that I'm asking you to push five so five goes inside after that I'm asking you hey which is the last element the top element you say it's five because that that was the one that was last pushed in after that we have an operation size how many elements does the data structure hold three so it'll be returning three so usually we have these four functions in the stack data structure again if you want to have other functions well you can do it yourself but these four are the most common used functions when it comes to stack data structure perfect so you understood what is a stag data structure right I can say yeah done but what is a q data structure okay let's understand that as well so first of all you need to understand Q allows you fif operation that means first in first in first out let's understand that as well again the same thing Q is a similar data structure that allows you to hold certain data types can be integer can be pair can be customized can be character can be string can be anything the Q also gives you the same operation which is the push operation where you can push a certain value into the que it also gives you the top operation it also gives you the pop operation and it also gives you the size operation got it now this is a q I'm not talking about DQ DQ is a two-ended q we'll be discussing about that right at the probably right at the end of the playist not now focus on Q as of now perfect so what I'll do is I'll write certain operations let's quickly write down certain operations so assume I'm asking you to push two I'm asking you to push one push three push four then I ask you pop then I ask you top and I again Ask you pop then I again ask you top then I again ask you to push probably let's say seven and the top and then the size perfect how will this work out I've repeatedly said that it is a similar data structure so again I'm going to visualize it in a similar fashion let's try to go through each and every Operation Push two push one push three push four perfect right after that I'm asking you to pop now you will not be popping out this one because this is a different data structure it does follow first in first out first in which element entered first into the SK data structure this one right so this is the one that will go out first first in first out so what will happen is is this goes off perfect after that I'm asking you the top now again first in first out so you look from the back and this one was the last like the first in entered one so what I'll do is I'll say this is my top element as of now I again ask you to pop out so again this will go up I again ask you the top this time the top is three because this is the first entered one among all of the present values in the Q dat structure perfect next is push of seven push it next is stop again the top will be three first 10 not last 10 first 10 after that I'm asking you the size so the size is three got it perfect so this was the Q data structure okay we have understood what is a q data structure and you might might be thinking hey how do we implement it now usually usually in most of the languages if I talk about C or C++ or Java or python you will find the stack library in it so what you can do is you can have it again the syntax might vary from language to language you can just Google it and you'll get it if I have to store an integer I can really give it something like this stack storing integers and this is the variable name this is the variable name perfect and after this what happens is I simply go ahead and say stack. push there is a push operation I can say six there is a pop operation I can do a pop there is an inbuilt top operation and there is an inbuilt size operation so while you solve problems you don't have to implement a stack there is an inbuilt stack that there's an inbuilt stack for every language that you use similarly you also have a Q inbuilt as well same same way you can Define q data type and then q and you can go ahead and say q. push again value you can say q. pop you can say Q do top and you can say Q do size so in case of solving problems you will not be implementing stack or Q by yourself you'll always be using the internal libraries for C++ can use the STL for Java you can use the collections so similarly according to your language you can just Google it and you'll find it across perfect so we know how to use it but if I ask you a question generically in interviews they would ask you this is the standard uh thing that you'll find in the library but inside the Library how are the Imp implemented right that might be a question that would be asked to you in an interview so let's understand about that so now it's time to understand what happens behind the scenes so you'll be implementing a stack using array at first after that we'll be implementing a q using array let's get into that so a stack using arrays if I have to implement something using an array data structure in order to define the array data structure I need a size so that means in order to implement stack I need to know the size how many elements at Max will you be storing so for this implementation the size has to be known this cannot be dynamic in nature it has to be constant size so imagine they're ask they're telling you that I need a 10 size data structure so what I will be doing is I'll be storing integer in it integer the variable name stack s and the size is 10 so this is what I will be doing right and after that I'll be taking a top variable and I'll be assigning it minus one I'll be assigning it minus one right after this imagine someone is telling you hey can you push four can you push four into your stack data structure now imagine this is your stack data structure so what will you be doing you'll have to store four so logically four should go here first place so what is the first thing yes you'll take the top you'll move it one place ahead and after that you'll take this four and you'll place it at the zeroth index done imagine after this someone comes up and says hey pop out what does pop means you have to delete that element so what you can do is you can take the top and you can move it back to minus1 after this if someone is asking you hey what is the topmost element in your stack you're like Hey listen since this stop is pointing to minus1 that means I don't have an element I don't have an element why I had a four you popped it out so I don't have an element I didn't ER B this for doesn't matter because stop is the variable that will help us determine what elements are there in the stack got it perfect after this again come up and say hey push five so again what you will do is you'll take the top and move to the next point and you'll push five over there after the diue push six so again you'll take top one place up and you'll push six after that I ask you push 10 again you take top one place ahead and push 10 right over here I am asking you hey can you tell me the size what will be the size the top is pointing to the second index the top is storing two so if it is pointing to the second index which means I have three elements so size will not will be nothing but top Plus 1 quite simple right after that imagine I'm asking you hey what is the topmost element what will be the topmost element since the top is no more pointing to minus one it means I still have elements it means I still have elements so what you can do is you can say array or rather the array was stack stack of top perfect this will give you the top simple and since it is under the assumption that the stack will add to Max have 10 elements you don't have to check for top exceeding that size or not if the interviewer is asking you probably we can put a check for that as well got it so if I have to write down the implementation is it tough no it is not usually what we do is again uh the best practice in such cases in an interview because this will not be coming in an online assessment or nowhere it will usually be asked in pen and paper interviews the best practice is maybe you can name a class you can call it as St IML which means stack implementation and inside of it I can have a variable top as minus one I can have a stack in like I can have a stack you can ask the interviewer what is the uh size of the array that you're looking at and probably let's assume we taking a 10 perfect after that I need to write a lot of functions now what are these functions first function is push where I take a variable so let's try to write down the push function how does the push function Works straightforward it will be top equal to top + 1 what is the next thing it will be stack of top equal to X that that is it now if the interviewer is asking you what if uh you have more elements than the size of the stack in that case you can probably enter if condition where you're stating hey if the top is exceeding the size then I can probably print something like size exceeded or something like that okay push is done what is the next thing I need the top element top means I'll have to return something so the return type over here is integer how will I return something very simple I know one thing if the top is pointing to minus one it doesn't have anything so probably you can return or print something that that is something you'll be asking the interv if it doesn't have in that scenario it would be like return stack of top and at the same time do you do a top minus minus no the stop means just give me the element perfect what about pop the next thing is pop right so maybe I can write the pop here so that we can have all the implementations in one screen pop means deleting the top element first of all again the edge case in case there is no top element you will not be deleting anything otherwise you will be doing a top equal to top minus one that's it what is the other function the other function is the size function and I think that's super simple you will be returning top + 1 even if top is - one -1 + 1 is 0 so the size of the stack will be zero got it so if I have to determine the time complexity of each and every implementation so by the way make sure the class is ending over here usually you should Implement in classes again you'll find the notes given below please go through the entire code you will get more confidence okay fine uh so what is the time complexity let's determine the time complexity of the push operation I'm doing it in beo of fun the push operation is done in beo of fun what about the top again in bego of fun what about the pop again in B off one what about the size again in B one so all the operations are done in a Time complexity of B go of one what about the face complexity now this is where the problem problem is now I'll have to take a like over here I took a 10 size no matter what so it's not dynamic in nature like I just required for the example we took we just required a size three but for this probably I'll be declaring a size 10 which might not be of use so we will always be having some extra space right so arrays like the disadvantage with array is you'll have you need the constant it's not dynamic in nature so this is how the implementation of stack using arrays will look like so coming to the next one that is implementing a queue using arrays again since we are using arrays it cannot be dynamic in nature we need a fixed size so assume this time the size is given as four and what we will be doing is we'll be declaring a q array with the size four right and with this we'll be taking a current size variable this current size is going to keep a track of how many elements do you have in the Q data structure along with this we'll be taking couple of variables one is start while the other one is end and both of them pointing to minus one when we start off if you remember Q is nothing but first in first out operation hence we'll be requiring couple of pointers let's take some operations imagine I'm asking you to push three after that I'm asking you to push two after that I'm asking you to push four perfect right at the first operation that is push three you go ahead and check hey first of all do I have capacity the current size is zero and I have a capacity of four so I can still store in the data structure now the next thing you'll check is if the start and end both are pointing to minus one and if that is the case without thinking you will take both the start and end to the next variable to the next value that is zero the start and end both are standing at zero so what you will be doing is you'll be taking the value three and you'll be putting it over here at the same time you'll be increasing current size done and dusted what is the next Operation Push two again you do the same thing what is the current size what is the capacity I can still accumulate so what will happen is this time the start will not move start will not move instead only the end will move n gets to the index one it takes the value two and the current size increases to two after that I move to the next operation four pushing four again I do a similar check what is the current size it is two is it smaller than the capacity it is it is smaller than the capacity so I can still accumulate so what I will be doing is I'll be taking this four but before taking it I'll have to take this end I'll have to place it here and then I'll be pushing this four into it and I'll be increasing the current size to three got it what's happening after this imagine someone comes up and says hey can you give me the topmost element he'll be like why not first and first out so whatever is being stored at the start that will be your element so you can simply return array of start given that given that the start is not pointing to minus one the Q has some values in it keep that in mind got it so top was quite simple now after this imagine I ask you to do pop pop I'm asking you to pop two times so what you will be doing is first of all you'll check do we have elements to pop out that means the current size is three I have elements so just pop it out so in order to pop out what will happen is the start gets to the next so basically what You' have done is you're saying this is your Q data structure the start and end of maintaining your start and end of the Q data structure perfect at the same time the current size will decrease to two after that I'm again asking you to pop again the same thing will happen since we have elements the start will move over here and the current size will decrease to one perfect another pop is done right after this I'm asking you to push two I'm asking you to push three okay first one is super simple pushing two is super simple what you'll go ahead and do is you will will take the end to the next and you'll push two and the capacity will be two rather the current size will be two because you have two elements with you okay after this is The Edge case pushing three if you want to push three you can why because the current size is two and it is lesser than the capacity so you can but the moment you try to do it the end the end is somewhere standing at four the end is somewhere standing at four so what you'll have to do is currently this was the cube but you'll have to take like these spaces are empty you have to put over there so what you will do is if it exceeds if it exceeds just take it and you place it at the front you place it at the front super simple so if I place it at the front this can be replaced with three so the push of operation is done it's quite simple you basically do end equal to end + 1 and you can modularize with the size it will automatically take you like in this scenario end was 3 + 1 and if you modularize that with the size four for modul 4 and a zero index so you basically go to the zero index super simple push is performed as well now what if after this I ask you hey can you pop can you pop two times so for the first time when you pop pop out the start gets over here the start gets over here right and the current size which is two by the way uh I forgot to increase the current SI previously because we did enter an N liit so let's quickly do the pop now so now when you do a pop start gets over here and the current size decreases to two which is sensible because this and this is your Q correct okay so one pop is done after this if I again ask you to pop I'll again pop so what will happen is the start this time will go ahead and the current size will now decrease to one but this time when the start goes ahead it goes to four again you'll have to do a circular array same formula and the start comes out to be here start comes out to be here perfect that that's that's where we are after this what will we be doing we're going to do something very important after this if I have been asked pop that means I'm having a current size one and I'm popping out I'm destroying the queue if I'm destroying the queue what you can do is wherever the end and start out wherever doesn't matter you basically bring them to the starting start and to the end and you make the current size to be zero then lot of edge cases I covered each of them using this particular example right it's time to implement again uh we're going to follow the same format class Q you can open the braces again assuming the size to be 10 and assuming the Q data structure to be of size and we need a current size which is zero and we need a start which is minus1 we need to end which is minus1 now we need to write down the operations let's write down the operations first one is push operation which is quite important so when can I not push obviously if the current size is equivalent to the given size I definitely cannot push so you can fin print a statement and go back okay apart from this if the Q is of size zero which typically means the current size will be zero or the start or end is minus one in that scenario what you will do is you will ask the start to be zero you'll move both of them because you're giving both the starting point and the ending point of the cube perfect but if this is not the case in that scenario only the end will move only the end will move because I I just need to insert at the end and you'll do a modularization with size perfect right after this you simply go ahead and say okay hey Q because the array was Q hey Q on your end can you put a x and once you have done this can you increase the current size to one by one rather and if that is done can you just end up that's it I've covered up all the cases so we have to implement the pop operation now so I'll be adding on the pop so when can I delete if I have something with me right so what if the current size is zero that means I don't have anything so probably you can say that the uh Q is empty and you can return but what if it is not what if the current size is one in that scenario you basically destroy the queue and you get back to the initial configuration but if you're destroying it please make sure you store the element somewhere perfect so if the current size is one I'll be destroying the start and I'll be destroying the end I'll be initializing both of them with minus1 and that is not the case you know what to do since you have taken out the element now you'll simply be moving the start to one place ahead because this element is deleted you shrink like just take it out and the start goes ahead start plus one modularize with size done and dusted and at the end because you're throwing out an element so what you can do is minus equal to 1 shrink the current size and right at the end you could go ahead and return the element which you had picked up right at the beginning got it so this is how the pop operation will work out right after this we need to write down the top operation as well the top operation is quite simple what you can do is you'll be like okay how do I figure out the top if I have an element if I have an element if I don't have an element maybe you can write Uh current size equal to equal to zero that is the case you don't have an liit apart from that you always have an element so what you can do is you can go ahead and return Q of start because that is the starting point of the Q data structure done what about the size I think that's going to be super simple you'll just have to return the current size variable that you are storing simple done and dusted I have to go through the time complexity can I probably yes the push is working in B go off in yeah I'm just doing unit operations the pop is working in B go n again just doing unit operation the top is working in BN the size is working in B and the overall time complexity is B one for all the operations but I'm using some extra space while I'm declaring the CU array right so we're using an extra space of beo of size got it so we are done with the implementation of stack and Q using arrays the only disadvantage with that implementation is we need a constant size what if we want something dynamic in nature that is where linklist comes in you haven't seen my link list playlist please go back and watch it because I'm not going to explain link list over here the first thing that we will be implementing is a stack using link list and these are the operations that we will be doing in order to understand uh this particular implementation first of all what you'll be doing is you'll be taking a top and you will be pointing it to null pointer super simple now we will be doing the push operation that is asking us to push four so what you will be doing is you will be creating a node with that value and you'll make sure that the next pointer of that node because in link list if you take a normal node it will be containing a value and a next pointer make sure that the next pointer is pointing to top which is null as of now one once that is done take the top take the top and make sure you place it at that new node that's it the push operation is done again I'm asking you to push two so what you will be doing is same thing creating a new node with a value two and make sure that the next pointer is pointing to top which is the node four and once that is done take the top and point it to this one push of two is done what is next push of three again the same thing create a new node when the value three make sure that the next pointer is pointing to the next node and right after this take the top and place it over here this is also done what is the next push of one again do the same thing create a new node with the value make that the next pointer is pointing to top and once that is done take the top and place it at that new node that you have created perfect so all of these operations are done after this if I'm asking you top which value is present at the top stack means last end first out and the last entered element was one the last entered element was one so what you can say is top of data top of value if you do that top of value you will get the that value perfect after that I'm asking you to pop out what does pop mean what you can do is temporary equal to top so what that will do is that will place a temporary over here after that you can do a top equal to top. next now what this will do is this will take the top from here and it will place it at the next node once that is done you could go ahead and say delete a bad spelling yeah delete the temp so what will happen is the temp will be deleted with all its references dumb I was able to delete as well after that I'm again asking you to push seven so what you can do is you can again create a new node and make sure the next is pointing to the top and the top goes ate done and after that the size please make sure you count the number of push operations and you subtract when I'm popping out that is the only thing that you'll have to do super simple isn't it implement it yes again the same thing class stack we need a node so again uh the same definition of a node where we have a value and we have the next pointer so maybe we can call it not top and initially we can have it like don't assign anything that means a null pointer and along with this I need a size as well you can give the size as zero we need to implement push so again push with a value let's say X how do I push X into it again super simple I create a new node node star that's a temporary equal to new node again I'm not explaining this already done this a lot of times in link list and then after that temp of next pointer should be pointing to top and once that is done top should be pointing to Temp and along with this size should increase by + one done the push is done what about the pop the pop is again super simple if I have to write down the pop it's going to be I need to take it out right so maybe I can say temp equal to top right a node temp so you can probably Define it as a node start Temp and then I can say top can you just go to the next done after that what I can do is I can straight away delete Temp and before going ahead I can say size equal to size minus one because I've reduced my size by one then what about top that's super simple you just return top de data done what about size you just return size please uh take care of the method and variable naming that they might Collide they might Collide because yeah certain languages it might Collide yeah that's it done what about the time complexity again we of one we of one all unit operations everything is unit what about the space complexity this time I'm not consuming any constant space I'm consuming the space that is required to store if you're giving me three elements I'll consume a space of three I'll not consume a space of 10 got it so the time complexity is much much better this is how we Implement stack using link list so it's time to implement Q using link list if you remember Q uses a fifo mechanism right so we will be requiring a start and an end so that by the end you can just keep pushing elements from the start you can know which was the first entered element initially both of them will be pointing to null just point them to null don't think much okay you can take a size variable which keeps a track of the size whenever we push elements you can increment the size whenever we pop elements you can decrement the size first operation is push s so what I will be doing is I will be creating a new node with the value seven in it right and if if both the start and end are pointing to null that means is the first element so what you will do is you'll take the start and you'll take the end and you'll make sure that both of them are point to this first node and you can increase the size as well done after that I'm asking you to push two so this time what you will do is you will take two again insert it in a new node right and this time just for the end just for the end because this is not the first element this is not the first element otherwise you would have been at null this the second or third or fourth some some of that level element so what you will do is you'll take the end you'll take the end and you will take its next and point it to this one and once that is done you can say hey end not to the start not to the start just to the end can you move ahead done after that I'm asking you to push three again I'll take an element three and I will once that is done the node is created I'll ask the end to point to this one and once that is done I'll take the end and I'll move it here after that I have a push of five I'll again do the same thing I'll take a new node five and I'll make sure that n's next is pointing here and after that I'll make sure that end is over there done after this I'm asking you to pop out I'm asking you to pop out so it's going to be super simple what you will be doing is you'll be like temporary equal to start and after that you will move start after after that you'll move start to start. next so it will go to the next and then you can delete out the temporary you can delete out the temporary done I have popped out after that I'm asking you the top top will be nothing but start do value or start. data done after that I'm again asking you to pop keep it in a temp move the start and then delete the temp done after that I'm again asking you to pop now this time when I'm asking you to pop what will happen keep this in temp move the start to one place ahead and then delete out the temp after that I'm asking you the top what will be your top this one so you can straight away give the value which is five after this if I ask you to pop what is going to happen because this is pointing to a null pointer because this is pointing to a null pointer the start will end up being at a null whenever the start ends up going to a null what you can do is you can also assign end to go to the null pointer you can say hey end can you also go because you're turn and dusted if your start goes out that means you're done both of them can be reassign to null which means we don't have anything left we don't have anything left got it okay so time to write down the pseudo code again the same thing you can take a class you can take a Q and what I will be doing is I'll be taking a node star and I'll have a start and I'll have a end both of them pointing to null and I'll have a size which is zero I need to write the push function so I'll be taking a push of X and over here what I will be doing is I know one thing I need a new node so temporary equal to new node of this value X and maybe I can just declare it node start over here I know one thing if start is equal to equal to null poter which means uh we still don't have elements so I can say start equal to end can you get to the temp done that is not the case that means we have elements so I can say else n next can you point to Temporary and once that is done right at the end can you do a size plus equal to 1 and that's it the push operation is done and dusted what about the pop can I read the pop operation yes I can uh I know one thing if uh the start is pointing to null I don't have anything so you can just handle that case where I don't have anything apart from this I have to pop out right so if you remember we took a temp and we said start can you get stored in it after that we asked start can you go to your next which is start. nextt and right after that we deleted the temp and we'll also have to decrease the value of size which is by one and that should be it yeah that should be it for pop what about top think top is super simple you just say if start is null again if that is null that means you don't have anything otherwise you return start do value or data whatever you are storing what about the size you can Implement that you can straight away return the size yeah that will be it for this class again all the implementations in beo of one complexity and we're using Dynamic space whatever is needed we're using that much nothing extra so the next thing that we will be implementing is a stack using a q data structure since you know both stack and Q this will be an interesting problem so the question is stating you just have a Q you don't have anything else you have a que and you'll have to make sure that this que behaves as a stack if you remember a stack is nothing but last in first out data structure whereas the Q is is a first in first out data structure so obviously if we use the Q directly it's not going to work I'll have to modify the queue I have to do some extra operations so that it ends up behaving as a stag data structure now if you know the stack data structure we have to make sure the top operation returns me the last uh last entered element and the pop deletes the last entered element that is what I have to keep in mind perfect what is the first Operation Push four we'll do that at this moment at this moment it is okay because if I'm pushing four if I'm asking the top it will give me four which is okay for stack the top element is four as of now okay what's the next one pushing nine this is the moment we'll have to think till this moment if I ask you the top element the Q will return you a four the Q will return you a four right which is wrong because the stat means last in first out and the last in element was nine I need nine I don't need four I'll have to make it behave in that way that the top element is nine and not four you can get the inition reverse it reverse the Q yes so what I'll do is whatever was the number of elements before before nine I had one element so I'll just pick it up I'll just pick it up and I'll put it over here done so I've taken out one element and put it over there now if I ask you after this operation give me the top the Q says my top is nine which is okay it is the stack stop okay let's do the next one push off two so if I push two it goes over here in a CU it will go over there so after these many operations if I ask you the top it will give me 9 which is which is wrong which is wrong right so what I will do is before this two I had two elements add two elements I'll bring it here so what you will do is first you will take out nine and you'll place it here after that you'll take out four and you'll place it here done so now if I ask you does it look like a stack top element is two which is yeah after that the top elit is nine after that the top element is four mhm okay next push of five so if I push the five here and I stop here the top element is giving me two which is wrong so I have to take the entire thing and put it over here do it take two take nine take four the stat now looks something like this which is correct ask the Top If ask you the top it will return you five ask you to pop out this goes off ask you to pop out this goes off if I ask you the top it gives you nine which does make sense because the top was five and then you po out the five and then you pop out the two the top will be nine right okay after that I'm asking you to push one so just to understand it better I'll just erase it and write 94 we asked to push one just push one if I push one what will happen is it will not give the correct top so again take 9 and four 9ine first and then four and then if I ask you the top it will give you one which is correct you just have to take the elements out and put it back so that it gets in the reverse order quite simple I have to write down the implementation can I yes I can again class Q rather stack because I'm implementing a stack so I'll be defining a q data structure we can use the inbuilt library over here like the inbuilt library q and after that I'll have to define the push function so push of X is what I'll have to do so can I say I need the size Q do size okay and then I can do Q do push because it is a q I'll be pushing the value X and after that I'll be taking all the use from zero to that size so I'll be running a loop from 0 to size minus one or the best way is I'll be running a loop from one to size whatever the previous elements were and I'll basically do q. push of Q do top or Q do front depending on your language library and I can just pop it out so what I've taken is taken it out put it back and then I've related okay done this will make sure that they're rearranged in the correct order what about the pop operation pop is very simple because the Q is already rearranged you can just call the pop what about the top you can simply return q. top the size q. size Val do super simple what about the time complexity the push will be taking a b go of n near about where n is the current size of the Q data structure all of the operations will be taking a b go of one understood what about the space again dynamic in nature depending on the number of elements given to you the space will be wearing I hope you understood this so the next thing is to implement a queue using a stack data structure in most of the stack implementations you did see that I was using a single variable top and in most of the que implementation I was using a start and an end why was that for stack I know one thing it is a Leo mechanism data structure so I'll be entering at the end and whenever there is a call for getting the top I'll be taking out from the end itself but whenever it comes to Q data structure I will be entering at the end like I'll be pushing it into the end but whenever there is a call for the top I'll be taking out from the back right so that is why in all the queue implementations be it aray be it link list as using start and an end over here as well I'll be using two stacks so the problem statement is I'll have to simulate the mechanism of Q using stack data structure I cannot use a q data structure I'll have to kind of replicate the similar Behavior using stack data structures so what I will be doing is I'll be taking two stacks S1 and S2 what is the first Operation Push four this is this is how the push operation will look like again you will have to know it or you'll have to think a lot during the interview so what you'll be doing as a first step is whatever is there in S1 you'll be putting it into S2 there is nothing so you can stop and you'll put the variable that has to be entered into S1 so I'll be putting it over here and after that for the third step everything from S2 to S1 not needed okay push two now realize why am I following these three steps understand I'm asking you to push two and you push it into the stack right and the Q comes and says Get me the top so what you will do is you'll give the two you'll give out the two because stack stop is two but Q is a FIFA mechanism so it will require four because that was the first entered element and you're not getting it so for the same reason whenever I'm asking you to push two what you'll be doing is you'll be taking out this four yes you'll be taking out this four you'll putting it into S2 then you'll be taking this two putting it into S1 then on the third step you'll be taking out everything from S2 and putting it back so now at this point if someone comes out and ask you hey giveing the top elit you can give out four because that is how it is four first and then two and it is maintained let's check out one more example pushing three so if I've been asked to push three what I'll do is I'll take the first element and put it over here then I'll take the second element and I'll put it over here done after that I'll take the three and I'll put it which is the second step and the third step is get back everything which is first two and then four first two and then four done again if you see it is following it is following 4 2 3 4 2 3 it is following okay what's the next one push five what's the first step take everything out take everything out first it will be four then it will be two then it'll be three so I've taken out everything what's the next step push five into S1 done bring back everything first be three then two then four again if you properly see it is following mechanism it's following that order okay I have to get the top Super simp four will be the top if I have to pop it out you can simply pop it out you can straight away pop it out if I have to again pop it out you can simply pop it out on S1 I have to push six again the same thing take out three take out five push it in and then push six over here and then get it back so I'm getting back first five then three if I again ask you the top that's going to be three which is makes sense it's done does make sense because you popped out twice first two elements were gone and after that you had three does make sense super simple three steps and you're done so if I have to write down the method it will be class Q I'll be requiring Stacks so maybe I can use the internal Library S1 and S2 I need S2 in order to store the elements so that I can get it back so I'll be writing the P operation so I've been given push of X so what I will be doing is I'll be saying hey first of all get everything out from S1 to S2 so maybe what I can do is I can run a loop while S1 do size till we have elements and I can say S2 can you take the element from the top he's like why not and then can you just pop it out so that I can get the next element done that is step one what is step two S1 do push of X done for step three get everything back from S2 so till S2 has something I can say S1 do push of S2 do front or top or whatever you call it and after that can you just pop it out and that is done for the push can I get the top super simple it will be you can simply say S1 do top will be your answer and can I do a pop yes you can simply do S1 pop if you need a size S1 do size so what is the time complexity the time complexity for the push operation is a b go of 2 N if you carefully notice it is a b of 2 N because I'm doing S1 to S2 over here another S2 to S1 over here right so it is taking a lot of time as is Big of 2N what about the space I'm using a big go off two into Dynamic space because I'm using two stacks got it so this will be expensive if I have a lot of if I have a lot of push operations in my problem statement because I'm taking a lot of time to push there are a bunch of push operations this might be expensive so depending on the problem statement if your problem has very limited push uh you know oper then you can use it but if it has significantly higher push operations than the top and the pop then we'll be going for the approach two where the push is going to take lesser time and the top and Bop are going to take more time so the second approach will be focusing on optimizing the push operations assuming that we are doing a lot of push operation and we will be making the pop and the top operation expensive again and uh I've written down the algorithm on the right over here it's a very simple straightforward algorithm there's no intuition behind it the moment you see me doing a dry you'll be like ah that was easy right so there's no intuition it's very simple basic basic maths or basic implementation so let's quickly uh try to do it again uh we'll be taking two stacks one is going to be S1 while the other one will be called as S2 okay first thing push two we'll keep it very simple just push it on S1 push three push it on S1 push four push it on S1 push five push it on S1 now at this moment if someone is coming up and saying top you actually cannot get it from S1 because according to Q according to the Q data structure this is the first element but if you do a stack one do top you'll get this element so what you should be doing is this should be at the first so this is the reason this is the reason whenever there is a top operation what I will do is if there is nothing in S2 if there is nothing in S2 I'll be taking everything from S1 to S2 everything from S1 to S2 why did I do that I'll you'll understand first thing five will go off next thing four will go off next thing three will go off next thing two will go off so I've taken everything from S1 1 to S2 at this point you will see that 2 3 4 5 this should have been the order and this is the order in S2 so if someone is asking you the top you can straight away give by saying take two take two so I'll be giving two and I'll not get it back to S1 why we'll understand again someone is asking the top I've done the transfer I've done the transfer so I can again take two so that is why I'm saying if there are some Els in S2 that means the transfer was done and if there are some why don't you just give me the top so I have optimized it significantly so what I'll do is I'll again get the two perfect at this time when someone is asking me to pop technically the two should go and that is the one that will go if you look at the pop if S2 has something I just take it off so what will happen is the two will go off so pop is also done right after this I'm asking you to push one remember two is gone so you can just cross it off two is gone I'm asking you to push one so what you'll do is you'll push one into S1 okay and done after that I'm asking you to pop so do you need to put it back no because you have three you have three right and that is what pop checks if there is still elements in S2 it means the order is maintained I can still take it out so for this pop what what I'll do is I'll take out a three for this oh my bad this pop is done for this pop I'll take out this four for this pop I'll take out this five okay done so basically what has happened is three three has gone four has gone five has gone after this I've been asked for the top I've been asked for the top this is where I'm saying do we still have elements in order he says no get everything from S1 get everything from S1 so I take it from S1 one put it back and now when I'm being asked to pop I'll just take it off got it I once I do the transfer and let the order flow in right for the top and pop and I keep the push elements with me that is how we can easily implement the approach two so what I'll be doing is I'll be super quickly write down I'll be super quickly writing down the pseudo code so class of Q again very simple I'll be taking stack of I NT with an S1 with an S2 done right after this we'll have to implement a push push is super simple I'll just do an s2. push of X pop is where everything is done very simple if S2 is not empty is not empty so I can simply do a s2. pop otherwise this is where the game starts I say everything from S1 I take everything from S1 and I say s2. push S1 do top at the same time I can say S1 pop so I've taken everything once I've taken everything I can say s2. pop pop out the latest element pop is done similarly can I write top I can what will be top top will be same if s2. Mt can you do an S2 is not empty rather so we're done with pop now the next thing is stop can I do a Sim similar thing yes if S2 is non empty which means not equal to zero I can straight away return S2 do top otherwise I'll have to take out everything from S1 which is S1 do size till I have something can I say S2 do push S1 do top yes I can and I can say S1 do popop at the end of the day I can return S1 dot sorry S2 do top that's it just return this and that will be your element what is the time complexity if I have to analyze I'm doing a push in B go of one and occasionally occasionally I'm taking a b of one where I'm transferring S1 to S2 occasionally over here also I'm taking a b of n when I'm transferring from S1 to S2 that is occasionally not always so I've optimized significant ly but yes I'm using two stacks so two into Dynamic space whatever we need so yeah that is it for this one and I I hope I have covered up everything that we planned to do at the start let's go back and check it out okay this is done this is done this is done this is done yes so yeah that will be it for the introductory video so if you're still now watching and if you have understood everything please please do consider giving us a like and if you're new to our channel do consider subscribing to us as well with this I'll be wrapping up this video let's meet in some the video till then by take care broken golden