Data Structures and Algorithms in JavaScript Implementing a Queue with Two Stacks Solution

[00:00:00]
>> Bianca Gandolfo: So the first thing you probably need to do is import your stack code here. So here we are, stack, stack, stack. Got our stack stuff. And the secret here is, we have an in stack and an out stack. So whenever you push something in, you put it in the In storage.

[00:00:24]
>> Bianca Gandolfo: No, this should say stackIn.
>> Bianca Gandolfo: And then, when your dequeue, this is where the tricky thing happens. So when your stackOut equals 0, which is the beginning, right? Whenever you start to dequeue. You wanna transfer your stacks. My gosh, what does that mean? Well, let's check it out.

[00:00:49] So while your stackIn is full, has something in it, you're gonna push. I'm sorry, you're gonna pop everything from your stack. And you're gonna push it, your stackIn, and you're gonna push it into your stackOut. Again, I'm gonna draw this out for you in a second. Great, and then once you have a stackOut, you're just gonna pop it off.

[00:01:14] Cool, we're good? All right.
>> Speaker 2: Wait, what's the like use case that we're storing, like in the data?
>> Bianca Gandolfo: Why would we do this? Just to be tricky on an interview, to confuse you. It's not really useful other than that.
>> Speaker 2: But is the goal to drive the two stacks?

[00:01:38] Like what's the relationship between in and out supposed to be for two stacks?
>> Bianca Gandolfo: Yeah, good question. So for our, let me see. Let's see, I'm trying to draw here.
>> Bianca Gandolfo: Finally, I can draw. Okay, so, let's just draw, where is my thing? Okay
>> Bianca Gandolfo: Okay, so here's my, [LAUGH] drawing, my God.

[00:02:13] [LAUGH] Here's our end stack. I'm gonna get better at this, I promise. Okay, so here's our in stack. And here's our out stack, okay. So remember, for a queue, we want the first one in to also be the first one out. True? Okay. So,
>> Bianca Gandolfo: Out, okay. So now as you can see here, whenever we wanna push a value, so let's say, come on, just start with one.

[00:03:02] I'll push it here, 1, 2, right? And then, so the difference is is whenever we're pushing something in what we're using the in stack and whenever we're popping something out, we have to put it all in to the out stack because you need to flip it over for it to work.

[00:03:25] Because for the queue, you want it to come out the first, you want one to be the first one to come out, right? But in this case since it is a stack, the only thing we can take out is two. So if we pop everything out of this end stack and you put it here, that's supposed to be an arrow.

[00:03:47] We'll pop it and we'll go here.
>> Bianca Gandolfo: And here. And so since it's a stack, we can now take it out.
>> Bianca Gandolfo: Does that make sense? So that's the basics of it. And so, when we transfer stacks, it's whenever this reaches 0. So we're gonna, this is gone.

[00:04:14] That's like the core of how this works, cool? I'm gonna go over it one more time. You have a question?
>> Speaker 3: It's just reversing the stack, so it acts like a cube?
>> Bianca Gandolfo: Mm-hm.
>> Speaker 3: Okay.
>> Bianca Gandolfo: Yeah.
>> Speaker 2: Are you're keeping them sync the whole time?
>> Bianca Gandolfo: No, you only switch them when you start copying.

[00:04:34]
>> Speaker 2: When you need more to put in the out queue?
>> Bianca Gandolfo: Yep.
>> Speaker 2: Okay.
>> Bianca Gandolfo: Yup, yup.
>> Speaker 4: Question from Victoria, wouldn't it just be easier to use unshift?
>> Bianca Gandolfo: Wouldn't it just be easier to use unshift? I don't think the point of this exercise is because it's easier, no, it's just one of those interview questions.

[00:04:53]
>> Speaker 4: So are you constraining it to only use push and pop?
>> Bianca Gandolfo: Yeah, cuz it's Q and NQ.
>> Speaker 4: Right, but your implementation is an array of push and pop?
>> Bianca Gandolfo: Yeah, yeah, yeah, push and pop. Yes, cuz that's the implementation of a stack has to be push and pop.

[00:05:17]
>> Bianca Gandolfo: Does that make sense? It's clicking? Yeah, great.
>> Speaker 4: I guess unshift would be inefficient, right? Because-
>> Bianca Gandolfo: Well, unshift is not a stack thing.
>> Speaker 4: Okay.
>> Bianca Gandolfo: Yeah. But yes, it does do the same thing, exactly. Cool. All right, so my drawing skills suck, I'm just gonna stop doing that now.

[00:05:47]
>> Bianca Gandolfo: Can someone explain to me in their own words, how the in-stock and the out-stock work together to emulate a queue?
>> Bianca Gandolfo: Is my question clear? What's the relationship between the in stack and the out stack?
>> Speaker 5: The out stack is the reverse of the in stack.
>> Bianca Gandolfo: Mm-hm.

[00:06:19]
>> Speaker 5: Since with a stack, you always, a stack is last and first off.
>> Bianca Gandolfo: Mm-hm.
>> Speaker 5: So then if you reverse it, it becomes-
>> Speaker 3: A queue?
>> Speaker 5: A queue, yeah.
>> Bianca Gandolfo: Cool, awesome.
>> Speaker 2: [INAUDIBLE] is kind of like an on the fly calculator queue when you need it, it seems like.

[00:06:43]
>> Bianca Gandolfo: The second one, the out-stack?
>> Speaker 2: Yeah.
>> Bianca Gandolfo: Yeah, the out-stack is only for popping.
>> Speaker 2: Yeah, it's like an impromptu queue when you need to pop something.
>> Bianca Gandolfo: Yeah, except it's still a stack.
>> Bianca Gandolfo: Yeah. So again, these are one of these tricky questions that you find in interviews.

[00:07:05] It's kind of a mind bender, cuz you're like, well, how is that possible? And that's kind of why I throw it in here, because it's really hard to come up with this stuff on your own. I remember when I first saw this question I was like, I don't know.

[00:07:16] Why would you ever do that? Why would you ever wanna do that? That's a waste of my time. But if you ever come across it, now you know. You have a question?
>> Speaker 6: You do out-stack when the in-stack is full or just every time e push and we pop?

[00:07:35]
>> Bianca Gandolfo: So the out-stack is only going, you're only gonna transfer the in-stack. So as you're pushing, you're pushing into the in-stack. And then when you want to pop, you're going to transfer the in-stack into the out-stack, which reverses it. And the you start popping from there. And then you transfer again, once your stack is empty, the out-stack.

[00:08:04]
>> Speaker 6: So it doesn't matter the stock is full or nothing?
>> Bianca Gandolfo: One more time?
>> Speaker 6: [INAUDIBLE] Could not be full to 10, right?
>> Bianca Gandolfo: It could be full, they could both have stuff in it.
>> Speaker 6: At the beginning, it is possible to say a full extent, if it's not full using that stack?

[00:08:28]
>> Bianca Gandolfo: So what you're saying that if the in-stack is empty? Is that what you mean?
>> Speaker 6: No, I'm saying that you have 10 of space. And if you put any stack of five, so you pop and that reverse. And if you go in like that, the order is missed sometimes.

[00:08:49] We're gonna start with the full stack or with no full stack?
>> Bianca Gandolfo: So you're saying if we have a stack that has a certain capacity, we need that capacity. How do we account for that?
>> Speaker 6: Yeah.
>> Bianca Gandolfo: That's a good question. In JavaScript, we don't really have to think of those constraints because our array is just, they're not actually contiguous blocks of memory like you would think.

[00:09:13] And so, our arrays are just like, you can make them as big as you want. You know what I mean? So you don't have to declare the size of the array ahead of time. You could if you need to, but normally we don't have to think about that.

[00:09:28] It's kind of the nice things about JavaScript, yeah.