WEBVTT 1 00:00:00.259 --> 00:00:01.092 Hi, and welcome back. 2 00:00:01.092 --> 00:00:02.743 In this video we're going to talk 3 00:00:02.743 --> 00:00:05.297 about queues and stacks again, 4 00:00:05.297 --> 00:00:07.997 and we're also going to introduce a new concept, 5 00:00:07.997 --> 00:00:09.586 that is very popular in programming 6 00:00:09.586 --> 00:00:13.273 but can sometimes cause a bit of confusion. 7 00:00:13.273 --> 00:00:15.094 Let's recap queues and stacks first. 8 00:00:15.094 --> 00:00:18.340 You remember this diagram from before, 9 00:00:18.340 --> 00:00:22.416 and how in a queue, you add new elements at the end, 10 00:00:22.416 --> 00:00:23.791 and when you remove an element, 11 00:00:23.791 --> 00:00:25.956 it always gets removed from the start. 12 00:00:25.956 --> 00:00:27.569 This is just a queue, like a queue 13 00:00:27.569 --> 00:00:30.165 for the supermarket, for example. 14 00:00:30.165 --> 00:00:32.226 And a queue in Python, we can implement 15 00:00:32.226 --> 00:00:36.000 using lists or using the Deque module 16 00:00:36.000 --> 00:00:39.016 or the Queue module, as we've seen before. 17 00:00:39.016 --> 00:00:43.986 Here's a simple sample implementing a queue using lists. 18 00:00:43.986 --> 00:00:45.686 Here we've got our class queue. 19 00:00:45.686 --> 00:00:47.492 When you create a new object, it sets 20 00:00:47.492 --> 00:00:50.002 self.items to be an empty list, 21 00:00:50.002 --> 00:00:52.745 and then you can push and pop. 22 00:00:52.745 --> 00:00:56.197 Push and pop are two names that are frequently used 23 00:00:56.197 --> 00:00:58.916 in the context of queues and stacks, 24 00:00:58.916 --> 00:01:03.681 just, I'm not really sure why these names are exactly used, 25 00:01:03.681 --> 00:01:06.154 but you can think of it, as, you know, adding a 26 00:01:06.154 --> 00:01:08.800 new element and removing an element. 27 00:01:08.800 --> 00:01:10.443 And, depending on whether you are working with a 28 00:01:10.443 --> 00:01:13.498 queue or a stack, the adding or the removal 29 00:01:13.498 --> 00:01:16.537 is going to happen in a different place. 30 00:01:16.537 --> 00:01:20.376 Here, when we push in a queue, we append an item, 31 00:01:20.376 --> 00:01:23.283 so we add the new item at the end of the queue, 32 00:01:23.283 --> 00:01:26.792 and when we pop, what we do, is we create a temporary 33 00:01:26.792 --> 00:01:29.745 variable called head and set it to be self items 34 00:01:29.745 --> 00:01:33.096 zero and then we set self.items to be 35 00:01:33.096 --> 00:01:36.346 self.items starting from the value one. 36 00:01:37.327 --> 00:01:39.010 And then we return to head. 37 00:01:39.010 --> 00:01:42.995 This is not a very reliable solution, by the way. 38 00:01:42.995 --> 00:01:45.928 What happens if you only have one item, say? 39 00:01:45.928 --> 00:01:49.353 But, I just wanted to illustrate how a queue might work 40 00:01:49.353 --> 00:01:51.361 if you were to implement it yourself. 41 00:01:51.361 --> 00:01:53.618 Just append at the end and remove from the start. 42 00:01:53.618 --> 00:01:54.867 And, this is sort of how you'd use it. 43 00:01:54.867 --> 00:01:56.522 You create a new queue object, 44 00:01:56.522 --> 00:01:57.960 and you can push values to it. 45 00:01:57.960 --> 00:02:00.637 Let's push five, seven, and 11, 46 00:02:00.637 --> 00:02:03.458 and then you can print the result of popping 47 00:02:03.458 --> 00:02:07.208 and that is gonna, sort of, print out five, at first, 48 00:02:07.208 --> 00:02:08.712 and then it's going to leave seven 49 00:02:08.712 --> 00:02:10.390 and 11 remaining in the queue. 50 00:02:10.390 --> 00:02:12.600 You can pop again, and that's gonna pop, 51 00:02:12.600 --> 00:02:15.829 sort of remove the next item from the list and print it out, 52 00:02:15.829 --> 00:02:19.020 and leave your list with only 11. 53 00:02:19.020 --> 00:02:21.736 With a stack, it's slightly different. 54 00:02:21.736 --> 00:02:24.389 This is a stack and you can remove elements from the top 55 00:02:24.389 --> 00:02:28.024 and when you add another one it goes back on the top. 56 00:02:28.024 --> 00:02:31.445 So, the oldest elements are always at the bottom, 57 00:02:31.445 --> 00:02:34.753 and newer elements are at the top. 58 00:02:34.753 --> 00:02:37.160 And again, implementing this in Python, 59 00:02:37.160 --> 00:02:39.468 you have here your class stack which again defines 60 00:02:39.468 --> 00:02:41.396 self.items to be an empty list. 61 00:02:41.396 --> 00:02:44.769 When you push, you push at the start of the list. 62 00:02:44.769 --> 00:02:46.162 So we are saying that self.items 63 00:02:46.162 --> 00:02:49.329 now is a list of only the new element, 64 00:02:50.214 --> 00:02:53.092 which is a parameter plus self.items. 65 00:02:53.092 --> 00:02:55.316 So that's going to join the two lists together. 66 00:02:55.316 --> 00:02:57.041 You can end up essentially adding an element 67 00:02:57.041 --> 00:03:01.087 at the start and pop is going to do self.items.pop 68 00:03:01.087 --> 00:03:04.092 and you can see lists allow us to pop 69 00:03:04.092 --> 00:03:06.454 and that just sort of removes the last element from the 70 00:03:06.454 --> 00:03:08.244 list and gives it back to you, 71 00:03:08.244 --> 00:03:12.795 so the stack pop and the list pop really do the same thing. 72 00:03:12.795 --> 00:03:15.853 And again, now you can push, but notice how when you 73 00:03:15.853 --> 00:03:18.117 push five, you get a list of only five, 74 00:03:18.117 --> 00:03:21.385 and when you push seven, the seven goes in front. 75 00:03:21.385 --> 00:03:23.523 And then you push 11, the 11 goes in front, 76 00:03:23.523 --> 00:03:26.896 and as you pop you start removing from the front as well. 77 00:03:26.896 --> 00:03:29.663 So you are adding and removing from the same place. 78 00:03:29.663 --> 00:03:31.381 We've already seen queues and stacks. 79 00:03:31.381 --> 00:03:32.828 I just wanted to give you a little bit of code 80 00:03:32.828 --> 00:03:35.566 about how they work because what we're going to 81 00:03:35.566 --> 00:03:39.833 talk about next is something that I find really interesting. 82 00:03:39.833 --> 00:03:44.500 And, that is, the concept of how many steps does it take 83 00:03:47.353 --> 00:03:52.188 to find an element in a queue or a stack or a list. 84 00:03:52.188 --> 00:03:54.428 Let me go through it and I'm sure you'll understand 85 00:03:54.428 --> 00:03:56.530 where I'm coming from. 86 00:03:56.530 --> 00:03:59.577 We can say that these queues and stacks and lists 87 00:03:59.577 --> 00:04:01.939 and many other data structures as well 88 00:04:01.939 --> 00:04:04.733 are what we call sequential. 89 00:04:04.733 --> 00:04:08.529 You start looking for elements at one end 90 00:04:08.529 --> 00:04:11.668 and you go through until the other end. 91 00:04:11.668 --> 00:04:13.223 So if you are with a queue, you start at the 92 00:04:13.223 --> 00:04:15.361 first element and you move on to the second one, 93 00:04:15.361 --> 00:04:17.434 the third one, and so forth until you reach 94 00:04:17.434 --> 00:04:19.267 the very last element. 95 00:04:20.226 --> 00:04:22.936 This means that if you are looking for an element 96 00:04:22.936 --> 00:04:24.812 in the middle, you have to go through 97 00:04:24.812 --> 00:04:26.826 all the elements along the way. 98 00:04:26.826 --> 00:04:29.201 So, it can be really useful to start looking 99 00:04:29.201 --> 00:04:32.484 at one end and then go through each element 100 00:04:32.484 --> 00:04:34.501 until you reach the last one. 101 00:04:34.501 --> 00:04:36.119 But it can also be quite slow. 102 00:04:36.119 --> 00:04:39.195 Let's say you wanted to only get the last element, 103 00:04:39.195 --> 00:04:41.470 you can't really do that with a queue unless you first 104 00:04:41.470 --> 00:04:45.362 pop all the elements that came before it. 105 00:04:45.362 --> 00:04:46.713 Here's another example, let's say you 106 00:04:46.713 --> 00:04:48.810 have a long list, a very long one, and you're 107 00:04:48.810 --> 00:04:51.445 looking for a specific element. 108 00:04:51.445 --> 00:04:53.643 For example, this list here. 109 00:04:53.643 --> 00:04:57.143 Let's say we're looking of the element 90. 110 00:04:58.905 --> 00:05:03.897 Well, as you can see, we had to do a bunch of jumps. 111 00:05:03.897 --> 00:05:07.130 We've gone from 13 to 56, 38, and so forth 112 00:05:07.130 --> 00:05:10.380 until we reached the element number 90. 113 00:05:11.611 --> 00:05:14.497 This is because a list is sequential. 114 00:05:14.497 --> 00:05:16.201 If you're looking for an element, the only 115 00:05:16.201 --> 00:05:19.117 thing you can do really is start at the beginning 116 00:05:19.117 --> 00:05:20.904 or maybe you can start at the end, 117 00:05:20.904 --> 00:05:23.019 if that's more suitable. 118 00:05:23.019 --> 00:05:25.339 But, either way you have to start at one end, 119 00:05:25.339 --> 00:05:26.624 and go through each element 120 00:05:26.624 --> 00:05:30.043 until you find the one you want. 121 00:05:30.043 --> 00:05:31.614 So this can be quite slow. 122 00:05:31.614 --> 00:05:34.587 It could be nicer if, you know, we could just 123 00:05:34.587 --> 00:05:36.758 know where the element is. 124 00:05:36.758 --> 00:05:40.149 But, of course with a list, you can't really do that. 125 00:05:40.149 --> 00:05:44.399 The number of steps we've had to do is quite a few. 126 00:05:45.970 --> 00:05:48.060 Our list here has 21 elements. 127 00:05:48.060 --> 00:05:49.773 You don't have to count them. 128 00:05:49.773 --> 00:05:51.258 Just believe me here. 129 00:05:51.258 --> 00:05:55.341 So, let's say that an arbitrary variable n is 21. 130 00:05:57.140 --> 00:06:01.650 If we wanted to find the very last element in this list, 131 00:06:01.650 --> 00:06:05.156 we could go from the start through each element 132 00:06:05.156 --> 00:06:07.036 until we reach the last one. 133 00:06:07.036 --> 00:06:10.537 So we have to perform 21 sort of jumps. 134 00:06:10.537 --> 00:06:12.254 We have to sort of jump into the first element, 135 00:06:12.254 --> 00:06:13.377 jump into the second element, 136 00:06:13.377 --> 00:06:17.210 and jump into the third element, and so forth. 137 00:06:18.474 --> 00:06:22.800 That means that for a list, which is a sequential structure, 138 00:06:22.800 --> 00:06:26.467 finding an element can take us up to n jumps 139 00:06:27.896 --> 00:06:32.024 where n is the number of elements in the list. 140 00:06:32.024 --> 00:06:34.724 Notice how this says up to n jumps because 141 00:06:34.724 --> 00:06:37.113 of course, we are finding the first element, 142 00:06:37.113 --> 00:06:38.874 that's only going to take you one jump. 143 00:06:38.874 --> 00:06:40.358 But if you're finding the last element, 144 00:06:40.358 --> 00:06:43.924 that's going to take you n jumps. 145 00:06:43.924 --> 00:06:47.837 And there is a specific term for this. 146 00:06:47.837 --> 00:06:51.889 When it takes you up to n jumps to find an element 147 00:06:51.889 --> 00:06:56.050 in a structure, this is called, this is what we say, 148 00:06:56.050 --> 00:06:59.967 is that this structure has a complexity of O n. 149 00:07:01.901 --> 00:07:02.734 Okay? 150 00:07:02.734 --> 00:07:04.601 That's just the terminology. 151 00:07:04.601 --> 00:07:07.318 O means complexity of and 152 00:07:07.318 --> 00:07:10.088 inside the brackets we put what the complexity is. 153 00:07:10.088 --> 00:07:12.572 And in this case, the complexity is n, because 154 00:07:12.572 --> 00:07:16.264 we need up to n jumps to find an element. 155 00:07:16.264 --> 00:07:17.228 Okay? 156 00:07:17.228 --> 00:07:19.909 This is called complexity. 157 00:07:19.909 --> 00:07:22.487 So, again, a complexity of O n just means that we 158 00:07:22.487 --> 00:07:27.487 need a number of jumps equal to the number of elements. 159 00:07:27.704 --> 00:07:29.430 Nothing terribly complicated there. 160 00:07:29.430 --> 00:07:32.942 When you're finding an element in a list, you need 161 00:07:32.942 --> 00:07:34.823 to jump n number of times. 162 00:07:34.823 --> 00:07:37.515 That's an O n complexity. 163 00:07:37.515 --> 00:07:39.553 And we're going to look at more into complexity 164 00:07:39.553 --> 00:07:42.213 in the next few videos as well as how we can 165 00:07:42.213 --> 00:07:44.719 sort of reduce that, hopefully. 166 00:07:44.719 --> 00:07:47.017 But of course, instead of n, 167 00:07:47.017 --> 00:07:49.275 you can have other things in there. 168 00:07:49.275 --> 00:07:52.346 For example, O of n squared, means 169 00:07:52.346 --> 00:07:53.995 that you need up to nine jumps 170 00:07:53.995 --> 00:07:57.224 to navigate a collection of three elements. 171 00:07:57.224 --> 00:07:59.797 Three squared is nine. 172 00:07:59.797 --> 00:08:02.880 So this is what O n squared means. 173 00:08:02.880 --> 00:08:04.708 Of course, you can see immediately 174 00:08:04.708 --> 00:08:08.307 that this is going to be slower than O n. 175 00:08:08.307 --> 00:08:11.222 With O n, and you have a list of three elements, 176 00:08:11.222 --> 00:08:13.463 you need to make three jumps. 177 00:08:13.463 --> 00:08:16.108 With O n squared, if you have a list of three elements, 178 00:08:16.108 --> 00:08:18.732 you have to make nine jumps. 179 00:08:18.732 --> 00:08:20.194 And, you can have the opposite, 180 00:08:20.194 --> 00:08:23.075 O of log two n, which means that we need to do 181 00:08:23.075 --> 00:08:25.153 up to three jumps to navigate a collection 182 00:08:25.153 --> 00:08:27.180 of seven elements, for example. 183 00:08:27.180 --> 00:08:29.263 Or indeed, nine elements. 184 00:08:30.382 --> 00:08:33.779 So, the thing inside the brackets is, 185 00:08:33.779 --> 00:08:35.371 you can think of it for now 186 00:08:35.371 --> 00:08:38.704 as the number of jumps in order to reach 187 00:08:39.722 --> 00:08:44.722 the last or the most far away element in a collection. 188 00:08:45.129 --> 00:08:48.681 In a list, the most far away element is the last element. 189 00:08:48.681 --> 00:08:51.903 And, you can need up to n jumps to get there, 190 00:08:51.903 --> 00:08:54.056 if you start at the beginning. 191 00:08:54.056 --> 00:08:57.260 And, there are other structures that are not lists 192 00:08:57.260 --> 00:09:01.162 where these other types of complexity applies. 193 00:09:01.162 --> 00:09:03.819 We're going to look at them throughout the section. 194 00:09:03.819 --> 00:09:05.721 And, don't worry if you're not sure what 195 00:09:05.721 --> 00:09:07.633 for example log two n means. 196 00:09:07.633 --> 00:09:09.293 I encourage you to look it up, 197 00:09:09.293 --> 00:09:11.888 but that is as complicated as it's going to get 198 00:09:11.888 --> 00:09:13.195 in this section. 199 00:09:13.195 --> 00:09:15.487 We're not going to go into complicated maths. 200 00:09:15.487 --> 00:09:17.118 You know, I'm not a big fan of maths. 201 00:09:17.118 --> 00:09:18.774 I'm not very good at it. 202 00:09:18.774 --> 00:09:21.275 So we're not going to get into complicated maths. 203 00:09:21.275 --> 00:09:26.275 Just, log two n is the most complicated we're going to see. 204 00:09:26.388 --> 00:09:29.199 So, don't worry too much if you're not too sure. 205 00:09:29.199 --> 00:09:31.873 It's all going to be fine. 206 00:09:31.873 --> 00:09:32.706 Okay? 207 00:09:32.706 --> 00:09:34.985 Hope you enjoyed this video. 208 00:09:34.985 --> 00:09:37.485 I'll see you on the next one.