Implementing a Stack

[00:00:00]
>> So, yeah, let's implement this. This is actually where it shouldn't be too hard to do that. So again, go back to our kata-machine, go back to day one. If you're using VS Code, then you make sure you have Git-ignored folders being displayed. All right, so let's go to Stack and let's implement a Stack.

[00:00:13]
I have everything generated to which we should be able to kind of do this all. And so I'm gonna do something a little bit different when we define the node. I'm gonna go type Node generic over T, oops, forgot to do that. So, we're gonna create our type definition of the node.

[00:00:26]
I always like to start here because what does our data actually look like? Well, of course, we're gonna have our value, which is the generic value over T. And then I'm gonna do previous instead of next. The reason why I do that is it just makes it a lot easier for me to visualize this, right?

[00:00:43]
I draw the arrows backwards, it helps me remember where I'm adding to. It just makes it a little bit easier. Again, we don't return this container to the outside world nobody else uses it. So, you can represent it the way that is most convenient for you. For me, previous always the bestest.

[00:00:59]
All right, so just like before, we need to define where our head is. So, I'll go private head: Node <T> and of course, it can be undefined, correct? So, if it can be undefined, put little question mark operator, awesome. And then now we can go to our constructor, set our head to undefined cuz I just really liked being explicit and let's go to length = 0.

[00:01:21]
So, we have our constructor done, again, one of the harder parts, make sure you have everything all set up, everything's good to go. And let's start with peek. Peek is kind of a very simple operation, what is at the head? Okay, so we can return this.head value. So, if we have a head, we return the value.

[00:01:41]
If we don't have a head, we return undefined peek, awesome. All right, let's start with push. So, typically in a queue, you do enqueue, dequeue, for a stack, you typically do push and pop. JavaScript shows shift, unshift for queue-like operations. Really unfortunate, I always like to pretend that when Brendan Eich was building a queue, and they said hey, how do we take this thing off?

[00:02:06]
He's, you shift it off, and they're, yeah. What happens if you wanna push it on? He goes [SOUND] unshift and then that's how he got it. He didn't know, and then that's how it ended up happening. That's how I like to do it my head. I don't know if anyone actually really believes me on that one, but I believe in myself on that one.

[00:02:26]
All right, so if this.head is undefined, well, all we need to do is just set our head to the node and we're good, right? Pretty straightforward, I'd say. So, let's go like this. This.head =, actually, let's just create the node outside here cuz remember, we're gonna need to use it in multiple places.

[00:02:47]
Value is the item, and of course, as Node, or else TypeScript is gonna be, that's not a node. So, there we go, we create that. Head is node and we return, simplest case right there. But of course, bookkeeping is always important when using a Stack so, this.length++. Let's make sure we alter our length, set our head if there's no head.

[00:03:06]
Now, if there's a head, what do we have to do? We've to do the exact same operations we did right here. We're gonna have to take this, let's just add an F right now, right? So, what we'd have to do is we'd have to take our head and we'd have to point to it with our new node.

[00:03:21]
Then we take our head and we point to the new node. Two step operation, should be pretty straightforward to do. So, let's take our head, or let's take our node, and let's point to it, right? Point to the head, there we go, first step done. F is now pointing to E, now let's make the head point to F.

[00:03:42]
So, this.head = node, there we go. That is the entirety of pushing in a Stack, I think it's pretty darn easy. Hopefully everyone feels good about that. Now, pop, well, it's pop. So, let's do this right here. So, the first thing we wanna do is, do we have anything to actually get out?

[00:04:02]
So, let's go this.length, let's do our bookkeeping of course. We don't wanna do our bookkeeping quite this way. We can't just simply decrement our length because we'll go into -1 territory if you keep on popping. So, we do have to be at least a little bit smart about this, right = Math.max(0, this.length- 1), right?

[00:04:22]
So, that way, we always stay at 0 or we count down. So, pretty useful, there we go. So, at this point we have to make a decision. If this.length = 0, well, we can go if this.head = undefined, right? We no longer need to have our head anymore.

[00:04:39]
We want it to be completely disconnected from our kind of container. Therefore, JavaScript will clean it up, everything's good. But of course, we need to save out that value, right, head = this.head, and return head.value, right? We can kinda do this but of course, again, TypeScript does not like this type of programming.

[00:05:00]
Even though we understand what is happening here, TypeScript hates it. So, this time instead of doing it that other way, I'm gonna do it like this. Cuz, I don't know, you can do it either way this works out, right? We know what we're getting ourselves into. All right, if that's not the case, well, then we need to actually detach the head.

[00:05:18]
So, let's go over that operation one more time. If we were to detach F, what do we do? Well, the first thing we wanna do, save out a pointer to F so we can now access it. Second, update head to repoint back to the previous one. Third, return the value that's contained within F.

[00:05:35]
So, let's do that right now. We're gonna jump in here, we saved out the value that is pointing to F, right? So, here's F, if you will in this category or in this case. Then we need to go this.head = this.head?.previous. Of course, TypeScript again still battling us, going hey, are you sure you wanna do this?

[00:05:52]
So, we can actually just use our actual head reference right here, right? That also works if you want to get rid of it. We're already pointing to it, awesome. And then lastly, we just simply need the return out a head.value. Again, this is JavaScript, there is details in which it's hiding from you in languages in which you need to manage your own memory.

[00:06:11]
Remember, we're still pointing to the list with head, we haven't cleaned up head. So, in more traditional languages, you would definitely have to free this item. If you're using Rust, you wouldn't program a linked list cuz it's too hard. If you're using C++, you'd have to free it.

[00:06:24]
All right, it's good joke. There's a joke somewhere in there, it's pretty good. And I believe this is pretty much everything we have to do to successfully have a beautiful Stack. So, let's see if this actually works out. Let's go npx jest Stack. [SOUND] Look at that. So, it did try to warn us obviously, it was very, very correct.

[00:06:46]
And now I see the errors of my way. What's the errors of your way? What happened here? It's 0 after you keep popping, right? So, if you keep popping, it's gonna keep returning undefined. And I must have came in here and caused the value, no, actually the value was or whatever the problems of value right here.

[00:07:03]
All right, don't see them. Yes. We'll go like this. There we go, that saved us. I won't cast as a node because we don't actually know if it's node cuz you can keep on popping on an empty list. There you go, that's a TypeScript error, my fault. [SOUND] This is surely disappointing cuz now I had my first non first try.

[00:07:24]
And look at that first try. We got it very first try, how fantastic is that? We can edit that and post, right? Definitely got this first try? Okay, good, just making sure. All right, there we go. So, that is all a Stack is,. It's pretty simple. The steps are actually more simple than a Queue, right?

[00:07:40]
Because you're really only focusing on a single pointer head. To me, it's just is the easiest data structure to implement, very, very small amount of link breaking. It's pretty simple, only difficult part, drawing backwards.