Stacks & Queues Review

[00:00:00]
>> Bianca Gandolfo: What about stock inserting it at the end. Seth?
>> Speaker 2: It was constant to me.
>> Bianca Gandolfo: Yup, and inserting at the beginning, Aisha?
>> Speaker 2: I'm going to guess constant?
>> Bianca Gandolfo: Actually no, not available.
>> Speaker 2: Okay.
>> Bianca Gandolfo: Right, we don't insert at the beginning for a stack, right? So a stack is we push the node to the back and we pop it off at the top.

[00:00:25]
That is the interface of a stack. If you're not doing that, then it's not a stack anymore. It's some sort of evolved data structure, or it's a queue, cool. So insert, generally, for a stack is, do you have an idea?
>> [INAUDIBLE]
>> Bianca Gandolfo: Constant, mm-hm. What about removing from the end?

[00:00:48]
>> Speaker 2: Constant.
>> Bianca Gandolfo: Mm-hm, what about removing from the beginning?
>> Bianca Gandolfo: Yeah. [LAUGH]
>> Speaker 3: You have to go through Egypt right or it's either that or not available. So it's linear not available.
>> Bianca Gandolfo: Yeah, not available, yeah, cool. What about finding a value, Joe?
>> Joe: I'm not sure.
>> Bianca Gandolfo: Yeah, so if we are looping through this data structure, you know.

[00:01:19]
Again, we're going to have a linear time complexity. We have to look at every single single one, and then accessing value is a little tricky. It kind of depends on the underlying data structure for this stack. We can make a stack with a link list or we can it make it with an array.

[00:01:40]
So if we're interested in being able to access values inside of our stack, which maybe we, do maybe we don't. You want to have the underlying data structure be an array. If you don't care so much, then a link list is okay. Cool, all right, queue. What's the difference between a stack and queue?

[00:02:05]
Do you remember?
>> Speaker 5: So when you entered into a queue or especially if you remove from the queue, you have to shift everyone else.
>> Bianca Gandolfo: We add to the queue, we put it at the beginning.
>> Speaker 5: So, okay, I'm stumbling, I'm sorry so.
>> Speaker 2: No, sorry.
>> Bianca Gandolfo: I think, I got it backwards, but because really, it really doesn't matter that much cuz it should be underlying a link list.

[00:02:41]
Yeah, but you're right. You're right. I'm messing up. Let's start over.
>> Speaker 5: Okay.
>> Bianca Gandolfo: [LAUGH] What's a queue?
>> Speaker 5: In my mind, I think of this whole, someone waiting in line or you can step in line to get a hamburger or something like that.
>> Bianca Gandolfo: Yeah, you're right.

[00:02:59]
>> Speaker 5: It's that analogy of, and I think it's that.
>> Bianca Gandolfo: I don't use those because they make it more complicated for me.
>> Speaker 5: Okay.
>> Bianca Gandolfo: Yeah, yeah, so for the queue the oldest one is the first one to exit, and the newest one goes on the end. Did I make sense?

[00:03:22]
So what is the-
>> Speaker 6: So there's only one end, then, for a queue, or-
>> Bianca Gandolfo: Yes, well-
>> Speaker 6: Because there's only one place that you could put it from. You can't put it from the middle or anything like that?
>> Bianca Gandolfo: So, the sort of like generalized interface of the queue is that things exit from the front and they enter through the back.

[00:03:46]
What else you want to do with your queue is really up to you, and again it really depends on the underlying data structure you used to build the queue. I recommend using a link list, and we'll see why in a second. But you could make it with an array if you wanted.

[00:04:04]
>> Speaker 6: So in this diagram, like the others, the end is actually on the left side.
>> Bianca Gandolfo: Yeah, exactly.
>> Bianca Gandolfo: For sure. Cool, so, inserting at the end.
>> Bianca Gandolfo: Is going to be, I think, I wrote this backwards, actually. So, inserting at the end is going to be, what?

[00:04:30]
>> Speaker 7: Constant, right? Because it just goes on like.
>> Bianca Gandolfo: So, yes, you insert at the end which is constant, you're right. You're right. Inserting at the beginning.
>> Speaker 8: You don't do that, right?
>> Bianca Gandolfo: Yeah. Do we? Hold on. Do we not do that? Yes, can we confirm that we don't do that?

[00:04:50]
Are we all clear? Am I confusing anybody? Okay, cool. So insert, generally, it's going to be.
>> Speaker 9: Linear or not available. One of the two [LAUGH]
>> Bianca Gandolfo: [LAUGH] We will generally be able to insert, it's just like.
>> [INAUDIBLE]
>> Bianca Gandolfo: It's going to be constant because we insert at the end.

[00:05:10]
>> Speaker 9: So we only insert, well as far as like China, because when I think insert you answered and you could answer it in the middle. If you can,-
>> Bianca Gandolfo: I see what you're saying.
>> Speaker 9: Yeah.
>> Bianca Gandolfo: Yeah, in that case-
>> Speaker 9: So then it should be not available then, if the way insert in general, the way I think I guess maybe that's my-

[00:05:27]
>> Bianca Gandolfo: Yeah.
>> Speaker 9: Cuz if you have inserted the end and insert, there are two different.
>> Bianca Gandolfo: Yeah, I see what you're saying. I think, insert in general is still a constant time. If we're using a link list as the underlying data structure, which I recommend. What about removing from the end?

[00:05:47]
Okay, this is a real test if I confuse people.
>> Speaker 9: End of this diagrams on the left kind of do that.
>> Bianca Gandolfo: Yes, perfect, so not available. So what about removing from the beginning?
>> Speaker 7: Linear.
>> Bianca Gandolfo: It could be linear if?
>> Speaker 7: If you're starting at a certain point.

[00:06:07]
[LAUGH]
>> Bianca Gandolfo: It's linear if the underlying data structure is an array.
>> Speaker 7: Okay.
>> Bianca Gandolfo: Yeah, what if the underlying data structure is a link list?
>> Speaker 9: Constant.
>> Bianca Gandolfo: Constant. If we have reference to?
>> Speaker 10: To the nodes.
>> Bianca Gandolfo: Yeah, to like the node that we are interested in.

[00:06:29]
Cool, what about finding?
>> Speaker 9: It would still be linear. You have to touch it, until you touch it.
>> Bianca Gandolfo: Yep, cool. And accessing value? Do you know, Joe?
>> Speaker 9: Constant?
>> Bianca Gandolfo: Could be constant if the underline date of structure is what?
>> Bianca Gandolfo: An array.
>> Speaker 9: An array.
>> Bianca Gandolfo: [LAUGH] And it would be linear if the underlying data structure is what?

[00:07:01]
>> Speaker 10: Linear? A linked list?
>> Bianca Gandolfo: Yes, awesome, cool.
>> Speaker 11: Could it be constant if you have linked list that has references that you can use for accessing the values for the nodes.
>> Bianca Gandolfo: What would that look like?
>> Speaker 11: I don't know.
>> Bianca Gandolfo: Yeah, I mean, you could have an array that holds a reference to every node in your link list, or an object and do a quick lookup that way.

[00:07:28]
If you find yourself in an interview and you're like, how do I optimize this more, just think like can I put this in a hash table, which is an object. Just an object, plain JavaScript object and have like constant time access. It's always like something you can it's like always I would say.

[00:07:50]
And I'm going to regret saying it I'm going to say like 80% of the time, there is something that you can do to optimize using a look up like an object. Mm-hm.
>> Speaker 12: This is a question from Chad.
>> Bianca Gandolfo: Sure.
>> Speaker 12: About reading versus accessing. Could you explain the difference?

[00:08:14]
>> Bianca Gandolfo: Reading and accessing are the same. Yeah, but find is like, searching through to see if something exists, yeah. So like, pretty much find, if you're getting the gist of this is always going to be linear, right? Like there's a always a chance that in your data structure, it's going to be at the very end, right?

[00:08:41]
Worse case scenario. We're always thinking worse case here because we're pessimist. So worse case scenario the thing you're looking for it at the very end, the lease accessible point of your data structure whatever it may be. We have to look through everything. So find is always going to be linear and access is going to change depending on your interface.

[00:09:01]
Awesome, all right. There we go. Any questions about this? Ask me a dumb question. Like what's the dumbest question you can think of?
>> Speaker 12: Give me an example of a linked list in actual code?
>> Bianca Gandolfo: Yeah, that's a smart question, I like that.
>> Speaker 12: [LAUGH]
>> Bianca Gandolfo: So linked lists are actually underlying data structure for a lot of things like array's and things like that.

[00:09:29]
In real life, like underneath is underlying data structure. That would be an example. My example that's not real, but is like a real life mapping is like a Twitter feed. It could be a linked list, right? Especially, if you wanted to be able to delete from the middle, delete nodes from the middle, then I would create a Twitter sheet as a linked list.

[00:09:58]
>> Speaker 12: React hooks are actually linked lists.
>> Bianca Gandolfo: Are they? Haven't I need to read about hooks. I'm excited about them. Anyone else know some examples of a linked list? You probably use them and you don't really know that you are. Anything that has like a next pointer is a linked list, essentially.