馃攳
Implement A Queue Using Stacks - The Queue ADT ("Implement Queue Using Stacks" on LeetCode) - YouTube
Channel: Back To Back SWE
[0]
All right so what we're going to talk about today聽
is how do you implement a queue with two stacks聽聽
[11]
so implementing a queue with stacks so first off聽
let's establish what is a queue a queue is not a聽聽
[19]
data structure it is an abstract data type so what聽
is an abstract data type an abstract data type is聽聽
[27]
just a certain policy we define and we say for聽
an item to be this type it has to support these聽聽
[36]
functionalities what are those functionalities so聽
a queue has to support an NQueue function and it聽聽
[44]
has to support a DeQueue function for it to be聽
the queue abstract data type so our job is to聽聽
[51]
supports this enqueue and dequeue functionality聽
it is to support first-in-first-out functionality聽聽
[59]
first-in first-out which is what a queue does聽
using stacks which a stack is last in first-out聽聽
[66]
in behavior so there's a problem here and this聽
is going to be difficult at first it doesn't聽聽
[73]
make sense how do you use stacks to implement a聽
queue so the key here is if the if you got this聽聽
[79]
interview and you've never seen it before key is聽
to see the mental barriers see the mental blocks聽聽
[84]
that you're going to face as you solve this what聽
problems does a stack give us when we try to get聽聽
[90]
our first-in-first-out behavior with a queue what聽
problems do we face and then once we have those聽聽
[96]
problems we can see how we solve them so this is聽
an approach you can take and what we're gonna do聽聽
[101]
is we're gonna walk through the thought process聽
right now okay so what are we going to do we're聽聽
[107]
going to walk through this trying to implement聽
a queue with just a single stack so what we need聽聽
[113]
to do is we need to see what problems does a聽
stack give us when we're trying to implement a聽聽
[118]
queue with it so what do we need to do we need to聽
insert these items into the stack and when we get聽聽
[125]
a DeQueue we need to give them the the item they聽
want in a queue fashion so you'll see what I mean聽聽
[131]
let's walk through this so let insert one into the聽
queue and notice how I said cue yes we're working聽聽
[137]
with Stacks but our caller of this function the聽
outside person using this code has no idea what聽聽
[143]
we are doing all they know is that this is a queue聽
so we're imagining this is a queue but we're using聽聽
[149]
stacks to implement our queue underneath this is聽
the underneath functionality so they just called聽聽
[154]
enqueue we added one so they call enqueue again so聽
we add two so they call enqueue again and they add聽聽
[162]
three and our outside caller no idea they do not聽
know what is happening underneath the alt for all聽聽
[168]
they know we're using a normal queue we're using聽
an array underneath they don't know we're using聽聽
[172]
a stack so this is what's happening underneath聽
and then they en queue again with the item four聽聽
[177]
and then our caller and queues again with the聽
item five so do you remember the order that our聽聽
[184]
items were put into this queue so let me write聽
out the order they were put in so if this were聽聽
[189]
a normal array and we just implemented this as a聽
normal queue without all of the stack craziness聽聽
[194]
going on we would have one is at the front of聽
the queue five is at the back of the queue this聽聽
[198]
is what our caller expects our caller expects this聽
behavior they see it from the outside as this is聽聽
[205]
what's happening this is what I want as a caller聽
because you are saying you're supporting the queue聽聽
[210]
abstract data type so I expect this behavior so聽
how do we give them the behavior when we have a聽聽
[217]
stack here a stack is only going to give me access聽
to five once I remove five I only have access to聽聽
[224]
four once I remove four I only have access to聽
three only have access to two and then only have聽聽
[229]
access to one as we go down so what is the item聽
if I call DeQueue right now if I remove from this聽聽
[237]
queue what item gets removed one and our caller聽
expects a one but we we can't do that we have a聽聽
[243]
stack underneath and this is barrier number one we聽
realize that the LIFO behavior of a stack clashes聽聽
[252]
with the first-in first-out behavior of a queue聽
so how do we give them one the only way the only聽聽
[262]
way I can give them one is if I perform a linear聽
time operation where I remove all these items so聽聽
[269]
that I have access to the one and it's linear聽
time in respect to the amount of items in the聽聽
[274]
stack because we have to remove some fractional聽
component of the total items to get to one right聽聽
[280]
so what we're going to do is let's remove five聽
we're trying to get down to one let's remove聽聽
[286]
five and then let's remove four and remember we're聽
trying to get tapped down to one that's our goal聽聽
[291]
right now let's remove three and then let's remove聽
two and now I have access to the item that my聽聽
[299]
caller wants so I have access to this one so you聽
see I can give my caller one now but what is the聽聽
[306]
problem what is the problem and this is where our聽
ability to analyze run time is very important we聽聽
[312]
see this is linear in run time and you would tell聽
your interviewer this yeah I see this problem this聽聽
[316]
is linear in run time and we just had to remove聽
all these elements and now we have access to what聽聽
[322]
we want so yeah give the caller the one and then聽
what should we do next so we gave our caller the聽聽
[329]
one and I guess we just put all the items back we聽
only have one stack so let's just return all the聽聽
[334]
items through the stack so I push two again and聽
again remember our caller has no idea we're doing聽聽
[339]
this underneath we're just doing this to support聽
their expected behavior the caller wants something聽聽
[345]
from the outside they have no idea this is going聽
on underneath okay so we reinserted all the items聽聽
[351]
from the queue so our caller asks us to DeQueue聽
again so what we have to do is our next item is聽聽
[361]
is to that's the next item our caller expects and聽
our 2 is buried under the stack and we see that we聽聽
[368]
need to remove all the items so I guess let's just聽
remove all the items again we need to get to this聽聽
[373]
two so let's remove five four and three so remove聽
five remove the four and remove the three we can聽聽
[380]
now give our caller the two so give the caller聽
their - okay so that was linear time so let's push聽聽
[387]
all these items back and again this is a linear聽
time operation to push the item back and again聽聽
[392]
overall we're going to stay linear in asymptotic聽
complexity the asymptotic nature of the deck is聽聽
[398]
going to be linear so what we're going to do is聽
we're going to push all the items back and then聽聽
[404]
yeah yeah what's up oh so I think you should be聽
why yeah yeah yeah let's rewind I think we missed聽聽
[412]
something okay so look at the stack so you see聽
that the items right next to stack if you look聽聽
[422]
at what the caller expects to my right you see聽
that the items right there to the right of the聽聽
[428]
stack are actually in the order we already want聽
them so when we do that removal to get to our聽聽
[434]
one what we're doing is we're actually putting all聽
the other items into position that actually belong聽聽
[441]
in the order that they belong so why would we move聽
all the items back when we just put them back into聽聽
[447]
the order that we expect as a caller so why don't聽
we create a second stack because we'd stay within聽聽
[454]
the parameters of the question let's make a second聽
stack and see how things work out okay so so Ben聽聽
[460]
just helped us out there and he helped us notice聽
something he helped us notice that on our rights聽聽
[465]
when we popped from that stack we had the items聽
in the order we already wanted them so why would聽聽
[471]
we put them back into the wrong order when we put聽
them back into the stack so now we have one stack聽聽
[477]
for pushing we have one stack for popping items so聽
what I'm going to do is I'm going to walk through聽聽
[483]
this again using this new optimization we have聽
and we're going to see how that changes things聽聽
[488]
and then we'll look at complexity's and see why聽
it changes things so let's push one to the push聽聽
[494]
stack this stack is for en queues we we push to聽
this stack and again remember this is underneath聽聽
[499]
the caller has no idea this is going on so we push聽
one and then I push two another en queue from the聽聽
[506]
caller and then there's another en queue from the聽
caller I push three okay and now our caller says I聽聽
[512]
want the first item in the queue I want to DeQueue聽
so what does the queue actually look like okay so聽聽
[519]
this is what our caller sees from the outside what聽
the caller knows all I know is I'm getting a 1 2聽聽
[525]
and then a 3 but we have a 3 and then a1 so what聽
we need to do is what we did before we need to聽聽
[532]
move all our items over but this time here's the聽
difference we have our other stack this is the pop聽聽
[538]
stack so I'm going to try to pop off of the pop聽
stack it's empty I know there's no items here to聽聽
[545]
pop and now I need to get my items from the stack聽
that gets pushes and I need to move them to the聽聽
[550]
pop stack and you'll you'll notice notice how this聽
helps us so move the item push the three onto the聽聽
[556]
pop stack and then push the two onto this stack聽
and then push the one onto this stack and now we聽聽
[564]
have what are called once we have the one but you聽
notice how we just improved we improved by seeing聽聽
[570]
now we have the two if I give my caller the one聽
now I have the two if a caller says I want to聽聽
[577]
DeQueue again they're going to get their two if聽
they say I went to DeQueue again they're going聽聽
[582]
to get their three so let's get a push the caller聽
just called enQueue with the item four so let's聽聽
[589]
add that to the push stack so we just added four聽
and what if the caller calls DeQueue well we're聽聽
[595]
ready right here we have this pop stack and we can聽
pop this off for a DeQueue and the caller expects聽聽
[602]
a two and again let me add the four to what they聽
expect so we give them their two and then if they聽聽
[607]
call DeQueue again that does not influence this聽
stack this stack is just receiving pushes and聽聽
[613]
this stack is just handling pops or de queues and聽
enqueues so we give them their three if they want聽聽
[619]
to DeQueue and now they call enqueue and then they聽
call DeQueue and on DeQueue we look at the stack聽聽
[626]
where we DeQueue from this pop stack and we see聽
that we don't have any items we don't have any聽聽
[632]
items ready to pop so what we're going to do is聽
we're going to take from the push stack and they聽聽
[638]
expect a four and then a five so we need to move聽
these items over here so that they're in the right聽聽
[644]
order and then we preserve that order and give聽
the caller what they expect so now we're ready to聽聽
[650]
DeQueue and we move the five off and the caller聽
says DeQueue again and we remove the four off聽聽
[656]
but what if the caller says I'm gonna DeQueue聽
again well look we'll see this stack is empty聽聽
[660]
if this stack is empty let's move items over聽
from the push stack the push stack is empty if聽聽
[666]
that is empty I know my queue is empty I can not聽
fill this with anything and I cannot do anything聽聽
[674]
here to flip items over so both stacks are empty聽
so our queue is empty so what you see here is聽聽
[680]
actually a queue for all the caller knows is that聽
this is a queue they don't know this is happening聽聽
[687]
again I need to stress this because this is a聽
key concept in programming it's abstraction it聽聽
[693]
is called abstraction where we don't need to聽
tell a caller how we're doing anything we're聽聽
[698]
doing what we're doing we can optimize however聽
we want for different types of situations and聽聽
[703]
the caller won't know all the caller gets is what聽
they expect so now that we did a walkthrough let's聽聽
[709]
look at the time and space complexities so what聽
are our complexities so if we declare the number聽聽
[716]
of items in the queue as n so we're going to use聽
event space that kind of seems obvious because a聽聽
[721]
maximum we're going to be holding the amount of聽
items that were given between the two stacks no聽聽
[727]
matter what we do but where it's more interesting聽
is the time complexity of enQueue & DeQueue stay聽聽
[735]
constant and this may be confusing until you聽
realize or become familiar with something聽聽
[740]
called amortized analysis so the core idea behind聽
amortized analysis is that we don't want to look聽聽
[749]
at each operations worst case we want to look at聽
the overarching algorithms worst case so yes the聽聽
[757]
worst case on DeQueue is that we have an empty聽
stack that we DeQueue from and we need to get聽聽
[762]
items from the other stack it's going to take聽
linear time to move all those items over to the聽聽
[768]
empty stack we DeQueue from so yes the worst聽
case on that operation is linear time but the聽聽
[775]
key to amortized analysis is how often does that聽
operation happen the key is that we realize that聽聽
[783]
this is such a rare operation or not really rare聽
but it does not happen enough that it needs to聽聽
[789]
impact the way we bounce that time so the way we聽
bound the time is on the very usual very expected聽聽
[797]
case that we're going to have items in our stack聽
that we DeQueue from we expect that and that is聽聽
[804]
going to be the normal case the very expected case聽
so it stays constant in time because we expect us聽聽
[811]
not to have to do that worst case operation where聽
you also see this is in the ArrayList class of聽聽
[817]
Java where the ArrayList needs to double in size聽
to stay dynamic this happens underneath may keeps聽聽
[823]
it constant in time because it's amortized the聽
way we analyze it is amortized so that is the聽聽
[831]
key to it it's so we don't make an expensive聽
operation make us-bound very differently than聽聽
[837]
if we made a more reasonable bounding based on聽
what we really expect so those are the time and聽聽
[844]
space complexities so if you liked this video聽
hit the like button subscribe to this channel聽聽
[849]
my goal is to build one of the world's largest聽
software engineering resources for helping people聽聽
[855]
study for software engineering interviews I聽
know I say this every video but I feel like聽聽
[859]
we get a little closer every single video that聽
I do but at the same time I'm so far away from聽聽
[866]
the goal and the vision that I see that I want聽
to map out with these videos in this channel so
Most Recent Videos:
You can go back to the homepage right here: Homepage