Transcript from the "Review: Stacks & Queues" Lesson
>> Bianca Gandolfo: What is a stack, and what is a queue? They are both ordered collections of items. Ordered, not sorted, but there is an order to them. They are a limited access data structure. That means that you can only access certain elements given some rules. Versus a random access data structure like an array, you can access in the middle if you wanted to.
[00:00:24] For a stack or a queue there are certain rules, right? Either last in first out, or first in first out. They are known for fast insert and fast removal. Cool, so what are the differences? A stack is Last in/First Out. So the last one you put on top you also take that one off.
[00:00:44] A queue is First in/First Out. The first one in is the first one out. So it comes out in I would say correct order in terms of if we're taking turns. We all use the example, for some reason, standing in line at the deli. Literally every single thing you find on the Internet about a queue it talks about a deli.
[00:01:04] I don't think everyone's from New York.
>> class: [LAUGH]
>> Bianca Gandolfo: Just really bad at making examples. A stack, everyone talks about pancake stacks, or a stack of books, actually. A stack of books is the one. And some vocab, push and pop, we talk about stacks in those terms. Queue, dequeue, enqueue.
[00:01:22] Sometimes they'll be different names, but more or less the same. It's the same idea, just different names. Cool, so some uses for a stack. Backtracking, undo. We explored the call stack with recursion. Kind of explored how that works. Parsing expressions, depth first search. Queue we use for breadth first search.
[00:01:42] We looked at our pop-up messages. We have our event queue in the browser. Whenever you click on something, queues up. HTTP requests to a server are gonna be queued up and answered in order, maybe, maybe. In the order in which it arrives, but whenever it gets there, who knows?
[00:02:05] Cool. So how do we implement them? We implemented them using objects, but you can also implement them using linked lists or arrays. We also implemented a stack using a string if you guys remember that. We have different ways of implementation, so you need to be mindful of the pros and cons for each,
>> Bianca Gandolfo: That's all I ask. Let's take a look. So here is an implementation using an array. Someone was asking me about this the other day, so here we are. We have our elements, our storage is an array. When we pop it off, again, constant time. When we push, also constant time, great.
[00:02:49] Queue enqueue, so when we push, again, we have our constant time. However when we dequeue we're using the shift operator, or shift method, method, method. Sorry to sound like a Minnesotan. Method. Or no is that southern?
>> class: I was gonna say, we don't sound like that.
>> Bianca Gandolfo: [LAUGH] I gotta stop before I get pitchforks.
>> class: [LAUGH].
>> Bianca Gandolfo: So we have a problem here for our queue that our dequeue is probably linear time because of the shift method.
>> Bianca Gandolfo: Cool. There are some ways to account for this. If we create an array that's pretty big and we start queueing, in the middle of it, that's a way to save some time.
[00:03:38] However, linear time, if we just do it regular. So we can optimize it by using an object and keeping track of the head and tail. And this is what we did in our exercises on day one.
>> Bianca Gandolfo: Cool.
>> Bianca Gandolfo: All right, second queue. This is mostly an exercise in just doing the class patterns.
[00:04:07] So if you remember back to the class patterns, we can talk about that. Anything noteworthy about stack and queue?
>> Student: I think it was pretty straightforward. But I have to admit that when it came to the very first exercise on the first day, I blanked. I was like, I didn't even know what to do.
[00:04:29] What are the directions here?
>> Bianca Gandolfo: Yeah, and that's super common, right? If this connection between an abstract concept, and how does that turn into code? You have to exercise that muscle. And then, after you've done it, then you're like, that actually wasn't so bad. Very cool. Thank you for being honest.
>> Student: Yeah.
>> Bianca Gandolfo: Yeah.
>> Bianca Gandolfo: Cool, anyone else? Anyone else blank out at the beginning of the exercise when, yeah?
>> Student2: Sounds very simple, but when you go to writing it, it there's a block.
>> Bianca Gandolfo: Yeah, yeah, yeah, unless you're actually doing push and pop, right? In which case you get that for free.
>> Student2: Yeah.