Stack

[00:00:00]
>> So let's talk about, let's go over, let's see how this thing works. And of course, we're gonna be using none other than our beautiful linked lists right here. So I'm gonna create another one of these, zoom in. For those that don't remember, a linked list is a node like algorithm which is gonna have a value, which is gonna be a T.

[00:00:19]
And it's gonna have a next and sometimes they will also have a previous if it's a doubly linked list and of course these are of type node T. All right, so now that we kind of back into it, so if you can think about it here, I'm gonna redraw our nice little list here A, B, C, D.

[00:00:41]
A stack is a lot like, so this is a queue really, this is actually how you do a queue, right? You have your head, you have your tail. Now a stack is gonna be backwards to a queue. So what we're gonna do is we're gonna actually have A points to B points to C which points to D.

[00:01:02]
And what we're gonna have is this is gonna be our head. So it's as if we pushed in A, we pushed in B, we pushed in C, we pushed in D. Now the reason why you have to draw it backwards cuz I always draw it backwards cuz it's so much easier to draw backwards is you really kind of, you can think about this like a stack of plates.

[00:01:21]
If you have an error in your code, you get a stack trace. You wanna guess what a stack trace is, it's the stack of functions that you've called up until this point. So a stack is something in which looks like a queue or acts like a queue. It's a singly linked list in which you only add and remove from the head.

[00:01:39]
That is why the arrows are backwards, or at least that's how I always visualize it in my head. You don't have to draw it backwards, just for me it's a lot easier. So if we were to add to a stack, we would do the exact same thing. We would take heads next, or we'd take E and we point to head, then we'd update head to point to E, right?

[00:02:00]
So instead of doing it the queue way, which is slightly different, we point E to head, we update head to point to E. Pretty simple, right? We do those operations backwards, you lose all of your data, you'll never find it again. And if you're in a real language, you will also leak it and then you now have more memory floating around.

[00:02:18]
The reverse operation of a stack of course is removing it. So what would you do? If your head was pointed right here, you'd update your head, or first, you'd save off this, then you'd update your head to point to next or previous depending on how you wanna create it.

[00:02:33]
And then you could return out E. E would no longer be pointing here. We break it off from the graph. We just do the opposite, inverse. So it's a lot like a queue. In fact, it's almost, it's so much like a queue it's very, very easy to get them confused.

[00:02:46]
And or accidentally program them one or the other way and even more so when drawing them, get your errors backwards, right? So a stack is also very, very simple, very, very easy to use and you see them all over the place. The big thing that you'll definitely see them with is coming up here when we start doing recursion, it's really good to think of calling functions like a stack.

[00:03:06]
Once you start looking at the world like a stack as you call functions, it becomes easier, and we'll go over this in more detail when we get there. But it just helps give you a mental model of what's going on actually within the computer cuz when you do call a function it is actually on something like a stack.

[00:03:23]
In fact, the memory that it uses is called the stack for a reason, because it is only going up and down. There we go. So, let's go through this. And so a push operation we did that, a peak operation exact same thing as a queue, right? Take the head, if there is a value, we return the value else we don't return anything.

[00:03:42]
And again constraints, they're awesome, right, by only allowing pushing and popping from one side we can make them a really fast operation. Cuz what is the operation again? For updating pointers. Constant, it doesn't matter how many items are in the list, it does not matter how big the value is.

[00:03:59]
The fact is, we are just simply setting things to null or setting them to point to different values. We'd kind of consider those constant time operations. Again, I know property access on an object in JavaScript may or may not be constant time blah blah blah blah. We just don't think of it like that.

[00:04:16]
All right, though I did have an interview once at Uber, in which the person made me not only go over all the running time. They're like, well, you didn't know that, accessing properties and JavaScript is log N, like okay. Then if that's the case, then everything just put a log N on the end of everything.

[00:04:31]
He's like, well then, what's the running time, well, it's log. And it was just like the longest most drawn out, make everything, add the word log N to everything. It was very annoying. So typically, we just don't do that. All right