Stacks & Queues

[00:00:00]
>> Bianca Gandolfo: Gonna get right into it with Stack and Queue. So you've probably heard of a stack and a queue before but if not I'm gonna go over it a little bit. So the properties of a Stack and Queue are pretty similar. They are an ordered data structure that have opinions about the order in which things can be inserted and things can be removed.

[00:00:27]
So for a stack, the example everyone uses is like a stack of plates. You stack them on top of one another and then you take the last one out. So for a Stack, the most recently added item is also the most recently exited item. Queue is the opposite, the queue is what you would think of as like waiting in line for something.

[00:00:52]
So you would stack it up and then you would take from the bottom. So you always take the oldest item out of the queue. And so these are fundamental data structures that underlie pretty much everything that we do. We're parsing, strings, your linter, like I was saying that the call stack, and the message queue, which is in your JavaScript runtime.

[00:01:24]
That's what executes your code when you load your browser or you run it in node. So this is our Stack and Queue, and if you're interested we have some data visualizations here that you can play with, they're secretly linked. So you can push, you can see that we're pushing and we can pop values.

[00:01:50]
So that's too small. So as you can see we're for a stack, we add, add, add and then when we remove it, we remove it from the end.
>> Bianca Gandolfo: And you might notice that this diagram looks like an array. We can implement a stack using an array. And probably you've been using stacks and you didn't know.

[00:02:17]
If you've ever had an array where you're interacting with it, where you're only pushing and popping, then you're using a stack. And when you're in an interview, you can say that it's an array, but you can also say, I could use a stack for this, but really you're just gonna use an array.

[00:02:37]
>> Bianca Gandolfo: And then similarly we have our queue visualization.
>> Bianca Gandolfo: We enqueue.
>> Bianca Gandolfo: Couple here. Right, so the pushing part is the same. But then it's the dequeuing that's different so that the dequeue would be the first one etc., like this. And so this visualization shows this array as sort of like this continuous block of memory, right?

[00:03:15]
So in memory we have our data next to each other. In some languages you need to pre-allocate memory. In JavaScript we have something called a dynamic array. And so we don't need to think about how long an array is gonna be before we make it. So a lot of these diagrams that's how they're working.

[00:03:35]
But luckily in JavaScript, we don't need to worry too much about that. So one thing that could happen when you are using an array is to underline data structure and then you're pushing and then unshifting. All right, unshifting is when you move from the beginning is that if you want your array indices is to be correct, so.

[00:04:03]
>> Bianca Gandolfo: Let's requeue.
>> Bianca Gandolfo: Let's clear it. We'll enqueue a couple things.
>> Bianca Gandolfo: So, when we remove the first one, and we want to ensure that our array indices are correct. We would have to shift the 2 to the 0, the 3 to the 1, right? If we were going to map these to a particular indices.

[00:04:38]
So, when you're using an array it's not optimized for unshifting. I'm pretty sure that in modern browsers, it's optimized now if you unshift. It's not very expensive, like you don't need to actually move things over. So just keep that in mind. If you talk about that in an interview and you use something like unshift and they ask you about time complexity of unshift.

[00:05:03]
Then you could say it like typically, it's a linear operation. Which means that for every item in this list, you're gonna need to do it. You're gonna need to do some work. That's the same of the length of the number of items. So that's n. So if in this example, n is 2.

[00:05:27]
We have a length of 2. So if we need to just shift it over, we would need to two operations. We shift over 2 and we shift over 3, right? If it was ten, it would be ten. If it was 20, it would be 20, right? So it grows when we call in a linear fashion.

[00:05:43]
So, when it's ten it's not a 100, right. That would be what we call quadratic cuz we're multiplying them. So linear, we don't really multiply except for really by one as we grow our input size. And that's how we think about time complexity. We're not gonna talk about as in depth in this class because I talked about it a lot in the previous class, you can go and check out those videos.

[00:06:06]
If you want more in-depth explanation in like kind of starting from the beginning, building up. We're just gonna talk about it kind of as we're going through. So, where were we? Linear as our input grows, the number of operations just grows with that input. And typically, unshifting, we would consider that linear, right?

[00:06:33]
Shifting it over each one. However, that's not always the case, depending on the implementation. And as you can see, this implementation keeps track of a head and a tail. So when you dequeue everything, you empty it and you enqueue it again. It's using basic math to figure out where to put these values, versus it specifically mapping to an index.

[00:07:04]
Why do we use them? They're super fast at what they do. So, it's supposed to be constant time for all of those operations. That's when people say, but what about the unshift thing? You could say, well, often it's optimized in modern browsers. Otherwise, you can implement it with a linked list.

[00:07:23]
I just wanted to show you what a stack might look like in actual code. And this is just sort of like pseudo code, where we have a stack, we're representing in this case as an array. We're gonna push something. That's what it looks like after that. When you pop it, it's gonna return five and then our array looks like that.

[00:07:46]
Or our stack looks like that. So that's kind of the interface you can expect, typical operations, and then we have our queue. Similarly, we add it to the end, but when we dequeue, we're gonna return the 1. And so another example of using a stack is a back button or an undo button.

[00:08:04]
So that's going to pop off the most recent changes. And that is a common interview question, it's like implement a back button or an undo button. So, something to think about.