[MUSIC] In this video we're going to talk about two relatively simple but important data structures in Computer Science. Stacks and Queues. Both of these data structures are used to hold information in between computations. They do so in such a way that restricts how you can add and remove elements from them. Okay, this allows you to provide a simplified interface that makes it very clear how you intend to pass data from one position in the program to another, all right? With that, let's take a look at how they work. All right, let's first talk about Stacks. All right?0 And to explain Stacks, I'm going to talk about Building blocks. So, here's my floor and I have some blocks. I'm going to stack them up. All right? So, first I put a block on the floor, that's my first block. Then, I stack another block on top of it, that's my second block. Then, I stack another block here and finally I stack a block right there. So now I have my stack of four blocks, all right? And the question is what order do I put them in? Well obviously you put the one in the bottom first and then you build up okay? Now what stack, what order do you take these blocks away? Well [LAUGH] if you're my son, you pull out this block here in the bottom all right? But [LAUGH] more you know, people that are not trying to knock the stack of blocks over, right, this would be the first one you would take off. And then you would take this one off, then you would take this one, and so on, and then this block would be the fourth. Okay. So blocks, you stack them in a certain order, and you unstack them in the opposite order. Okay? So a stack is what's called a LIFO structure. Okay? Last in, first-out. Okay? The last block I stacked up, is the first block I take off. And, as computer scientists, we usually draw it like this. And we say, "Okay I put things in the top, I take things out from the top". So this is a push operation, this is a pop operation okay, and pop only, always gets the most recent element that was pushed. So when you push it goes down to the bottom so I put something down on the bottom then you push again it goes here and you push again and then when you pop you take this last item out. Okay? So, Stacks are this last-in, first-out kind of structure, kind of like building blocks. Okay. So, let's talk about Queues now. So, what is a Queue? Well, let's think about, I go to some sort of store. Here's the checkout counter, here's my little cash register. Okay, all right. So I show up in line, I am the first person to show up in line is here. Okay, this person is first. Okay, then another person shows up in line. This person is second and then another person shows up in line, this person is third, all right? What order do they leave the line? Well this person gets to go first, check out first, then this person, so we got one, two, three. Okay? So, in contrast to a stack, a queue is actually a FIFO structure, okay, first in, first out. Okay. And we usually draw this a queue as this, where we go in here and out here. Okay, and just for you know, similarity I'm going to call this push and this pop. Okay, now when I stick something into the queue, right? The first thing I stick in, then I stick something else. then I stick something else. When I pop, I get this first and then I get this and then I get this. Okay? So a Stack, the last thing you put in is the first thing you get out. In a Queue, the first thing you put in is the first thing you get out. Okay lets take a look at stacks and queues in action. I have a very simple program here that basically pushes a couple elements on. Pops one, pushes another and then pops three off. Okay, so I'm going to start by making my container via queue. Okay. And my queue implements the push method and the pop method. Okay, so I'm going to push three things here. Push the elements one, two three. Okay, and then I'm going to pop one element, I'm going to push four, and I'm going to do three pops, all right? Now I want you to think about what going to happen here, hall right? What order are things going to print in, right? Remember, a queue is a FIFO structure, or first in, first out, okay? So, let's see if it works the way you think it does. Okay, it prints 1, 2, 3, 4. Why? Because I put 1 in first, then 2, then 3, then 4, and these pops occur in this order, so it gets it back 1, 2, 3, 4. All right? Okay, now, let's replace the queue with a stack. Right? Now I'm going to behave differently. Right? I'm going to push one, two, three. Then I'm going to pop. Then I'm going to push four. Then I'm going to pop, pop, pop. I want you to think for a second, about what you think's going to happen here. Remember that a stack, is a LIFO structure, or last-in, first-out. So let's see what happens. Three, four, two, one. Okay. Well, I pushed one, two, three. Then I did a pop. That pop, gets the most recent element: the three. So it prints three. Then I push four. The next pop, gets the most recent element: which is four. Okay, and then pop, pop. Which gets the elements before that, which are left: two and one, in that order. Okay? So you can see that by using a Stack versus a Queue, I dramatically change the behavior, all right? The question is, do I want the thing that I most recently pushed, or do I want things to come back out in the order that I put them in? So, here is the simple Queue class that we're going to use in this course. Okay, and you can see I've defined it as q with a capital Q, obviously, and we have an init method that just initializes the Q, and you can see, internally I'm going to represent the queue as a phyton list. All right? Now we've got some methods that you might not have seen before, lets talk about this first one here, underbar underbar len underbar underbar. Well, this allows me to get the length of the queue, all right? And when you actually called len in python, that's the method that it calls, so lets initialize a queue here, All right? And I should be able to now print the length of the queue. And I would expect that to be zero since I haven't put anything into the queue. Okay, and it is zero, all right. Now that we're talking about this, you can see that I have an enqueue and a dequeue method, all right. These two methods are the workhorse methods here that allow me to actually implement the behavior of a queue. So I should be able to add some things. Let's enqueue [SOUND] number 37 and let's equeue [SOUND] number 14 [SOUND] all right? And let's print the length again. [SOUND] Okay, now the length is two because I've added two things, all right? So when I call len in Python, what it's actually doing is it's taking the object and calling its under bar, under bar len under bar, under bar method. And another method you might not have seen before: under bar itter under bar under bar. And the idea here is to allow us to iterate over this queue. And if you look at the implementation, it's actually a generator. All right. But let's actually use it. Okay. How do I iterate? Well raise the four loop. So I say four item in queue. Print, item. All right. And that's actually going to use that, itter method, to get an iterator. And since we built a generator, it'll allow us to go across, the, the queue and I get 37, and then 14. All right, I get em back in the order that they were put in, and that makes sense for a queue, okay. And I have an underbar, underbar stir, underbar underbar method. Okay that's just going to return a string representation, and I'm choosing to just use the Python list representation, there. So, if I do print queue, it'll call that stir method and print it out like it was a list. Okay. I can end queue and dequeue things, and then, I can also clear things, okay? So, this is my queue abstraction. Now, if you look at the implementation of these methods, I'm really just using list methods. And, they're all very simple methods, right. All of them are basically one line, except for the itterator. And so the question you might have is why not just a Python list? Well, it's actually very useful important to use a queue class, okay? I'm creating an abstraction here and I'm saying this is a queue, and I'm restricting the ways in which you can access that queue. I'm saying if you want to add something to the queue, you can't just insert it in the middle of the list, you can't you know put it anywhere you want. You have to call end queue. Which we'll put it at the end of the list. And then when I want an item back, I can't just look anywhere I want inside the queue. I can't take the last thing off. I can only call dequeue, which will take the thing at the beginning of the list and give it back to you. So it, it enforces this first in and first out behavior. And this is critically important. All right, so that's how Stacks and Queues work. All you really need to remember here: stacking blocks and standing in line at the store. All right? Those are really the models here. I have a Stack, all right, where the last thing I put in is the first thing I take out, and I have a Queue where the first thing I put in is the first thing I take out. And both of these are extremely valuable data structures that occur again and again and again in computer science. All right and by restricting the ways in which you can access these things, it helps you to make better and more reliable programs, all right?
