Stack & Queue

[00:00:00]
>> Bianca Gandolfo: So we have this prompt, which is a random like, using one array and implementing three stacks, two stacks or in stacks, mini stacks. But only using one array as your core data structure. So, you already, you implemented a stack data structure earlier in this workshop. And so what you would do is you would adapt that class, right?

[00:00:24]
So you would make a constructor and everything and instead of only representing one array or one stack you would represent multiple, so there's a few different ways you could do this. You could, if you are implementing three stacks and you have and array of a certain length. Lets say certain length 30, you can say the first ten are for the first stack, and the second, and the third and then as that stack grows, then you can double it, double the size.

[00:00:55]
So that is one way of going about it, and that's the naive way and it takes up a lot of space. But it's not more, it's not like a slow solution. The better solution is instead is holding pointers to the, the first three nodes in the array. The first three indices in the array would be node one, or stack ones first element, and then the second would be stack two's first element, and then stack three.

[00:01:36]
And then one, two, three, the fourth one would be the second one for stack one, and so you would kinda do this interleaving approach. And so you'll see the interleaving as a theme for ordered data structures. That means that you are taking maybe two different lists and putting them one by one.

[00:02:00]
There's also merging, so you can merge. You can merge a list, which usually, you're comparing something. So if you have two lists and you're gonna merge them, it's usually like, you have a list of integers and you're merging it in order, or like they're sorted, you wanna put them in sorted order, that kind of thing.

[00:02:22]
It's different than kind of this interleaving, which doesn't do a comparison necessarily. Doesn't matter the order, just that it's in the original order. The next one is getMin() or getMax(). This one is a fun one, it requires that you, if you want to do it in constant time, it requires that you have an auxiliary data structure, like a stack.

[00:02:49]
Or you can just simply keep track of it, track of the min inside of the node. But basically every time you push a value into your stack, you want to push a value into your min stack that will always be the minimum. So you might have multiple minimums In that min stack.

[00:03:13]
And so it's not space efficient, but it will return the min. So every time you pop off a min stack or peak the min stack, it's always gonna be a constant time solution. So queue using two stacks is similar. Where you need to queue and unqueue and shift them over.

[00:03:37]
Once you are inqueuing, inqueueing, inqueueing, right so you have three items in your queue. When you need to dequeue you need to take the thing off the bottom and it gets stuck. So what you do is you
>> Bianca Gandolfo: You pop, so it's a stack. So you have to pop, pop it and then push it to the other stack.

[00:04:04]
So, and then you pop it and you pop it. Once you want to dequeue, you need to pop, pop, pop all the things in your stack, and then it flips it upside down into your other stack, and then you can pop it off in the right order, so that's how that works.

[00:04:32]
>> Bianca Gandolfo: So sorting a stack with the min values in order on top.
>> Bianca Gandolfo: Basically, so this is a simplification of the Tower of Hanoi problem, which is like that kid's game where you have the disks, they're fat and then they get skinnier. You have three. And then you have two.

[00:04:53]
And they're mixed up and you wanna get it to where they look like a perfect pyramid. You know what I'm talking about? So that's the tower for Hanoi problem. And this one is a simplified version of that. With just two.
>> Speaker 2: For the last one, creating the queue with two stacks.

[00:05:16]
I didn't really quite understand where the complexity comes in, cuz couldn't you just really shove into, both of them into a queue, I don't understand what that.
>> Bianca Gandolfo: So you can't use a queue, you can only use a stack.
>> Speaker 2: Okay.
>> Bianca Gandolfo: It's like a brain teaser thing, it's not very useful in real life.

[00:05:36]
It's a very, very common interview question. You'll see them on all the interview websites. I've never personally gotten it, but it's just one of those questions to kind of know. It's a tricky one, right? Because it's really a logic question, but yeah, but you can't use a queue, you can only use a stack.

[00:05:56]
>> Speaker 2: Can you make it act like it's a queue?
>> Bianca Gandolfo: Yep, yep. So you would create a queue data structure just like we made our queue with our constructor and everything. And then in queue could only push or pop, and then dequeue can only push or pop. And then your storage would be stack one and stack two instead of storage, you would have like stack one, stack two.

[00:06:19]
And so, you would go back before between those. And then so then we have like a string of bracket validator type question that you see a lot. This will basically, you're gonna have two stacks. So you push all the opening brackets, maybe you just need one, you push all the opening brackets.

[00:06:41]
Once you find a closing bracket, you wanna make sure that it matches the opening one. Opens you push and then closing ones, if it matches you pop, if it doesn't match then it's not valid.
>> Bianca Gandolfo: That probably only means anything if you've seen this question before. But that's sort of the gist.