WEBVTT 00:01.090 --> 00:07.420 In this episode we will learn how to implement one of the most simple yet powerful data obstructions 00:07.660 --> 00:11.890 stack Study Finds to Operation PUSH AND POP. 00:12.280 --> 00:15.130 So let's say this is our stock. 00:15.220 --> 00:20.640 We will have different states every number represent a change in the state. 00:20.890 --> 00:26.000 So the push Operation pushes a value on our stock. 00:26.530 --> 00:34.530 So in this case we push to the top of one three to four and so on. 00:34.530 --> 00:36.790 Numbers doesn't have to be in order. 00:36.910 --> 00:38.860 Those values are whatever we want. 00:38.920 --> 00:45.330 Now the pope operation does the side takes value from the stock. 00:45.850 --> 00:49.480 So it is the state of our stock. 00:49.580 --> 00:51.170 Five four three two one. 00:51.350 --> 00:56.180 And we want to get the last element we need to pop all the previous elements. 00:57.020 --> 01:03.610 And until we get into the element we want this structure doesn't seem to be very useful in the beginning 01:04.100 --> 01:13.860 but every compiler you use every programming language every operating system uses these internally so 01:13.860 --> 01:22.080 let's start by creating our data structure what is going to be call stack if you remember the previews 01:22.170 --> 01:29.250 episode when we learn how to implement linguist we could use one of those as the underlying data structures 01:29.630 --> 01:37.650 but for simplicity we will use the slides which are built in the goal language so let's call these items 01:38.210 --> 01:43.340 and there's gonna be an array of integers if you will like to change data type. 01:43.650 --> 01:50.030 We should do it here like strings or load 64 or whatever. 01:50.190 --> 01:51.900 For this example we will use it. 01:52.740 --> 02:02.730 So as we said before this tax implements two operations the first one is pop or push which receives 02:02.730 --> 02:11.490 some item and doesn't return anything and the other operation is pop which doesn't receives any argument 02:11.520 --> 02:16.100 but returns an item let's just return 0 4 now. 02:16.170 --> 02:16.480 Okay. 02:17.100 --> 02:26.770 So following the image the first thing we need to do is initiate our stock and then let's push some 02:26.770 --> 02:28.120 items. 02:28.120 --> 02:28.540 Right. 02:29.530 --> 02:31.510 So we'll replace some items. 02:31.510 --> 02:33.410 Let's now pop them and print them. 02:33.890 --> 02:38.890 So dream line pop doesn't receives any argument. 02:38.890 --> 02:41.410 We don't use. 02:41.660 --> 02:45.950 So we push for items and we're popping for items as well. 02:45.950 --> 02:50.710 So let's execute these and see what happens we does receive zeros. 02:50.720 --> 02:55.530 And this is because the functions it's always returning 0. 02:55.570 --> 02:59.650 So the first thing we need to do is to push some items into the stack. 02:59.650 --> 03:07.270 So we'll do it by these items is gonna be equal to I to append items and the item. 03:07.310 --> 03:07.810 Right. 03:09.480 --> 03:11.090 And this is my error. 03:11.240 --> 03:13.520 OK because item is part of the stack. 03:13.800 --> 03:21.570 So what we have here is that every time we go push with an item stack dot items which is this one is 03:21.570 --> 03:30.150 gonna be equals to itself but with a new item append that this is what append does appends a new item 03:30.570 --> 03:32.810 which is the same that we saw in the image. 03:33.000 --> 03:34.850 Okay so push is done. 03:35.520 --> 03:37.500 Let's execute this. 03:37.620 --> 03:44.290 We still have zeros of course because we haven't changed the implementation which is the function that 03:44.290 --> 03:45.940 returns the actual value. 03:46.270 --> 03:53.080 So you remember that we saw that you can do these were in this case X this is gonna be equal to one 03:53.170 --> 03:54.780 and Y is gonna be equal to. 03:54.970 --> 04:03.370 So we're going to do something very similar we'll do item and items are gone and B equals two items. 04:03.370 --> 04:08.960 So now we're in the last element because pops takes the last element from our stack. 04:09.160 --> 04:15.250 So to get the last one we need to know the size of the items is going to be right. 04:15.540 --> 04:18.790 Stack of items is going to return the size. 04:18.800 --> 04:26.450 In this case one two three four because the size is for even if Ds are 14 the size going to be four 04:26.960 --> 04:34.920 it the fourth element but if you remember arrays are index it started by C. 04:34.950 --> 04:42.570 So what we need to do is zero one two three to four do that we remove one element. 04:42.760 --> 04:43.280 Okay. 04:43.580 --> 04:56.210 Now items is going to be equals two items starting from zero ending in its size miners once again. 04:56.510 --> 05:04.950 So why would return this item would correspond to this element which is the last one in the new items. 05:04.950 --> 05:06.200 There's going to be equal. 05:06.980 --> 05:11.480 All the elements starting from the first one ending in the last one. 05:11.510 --> 05:21.260 And finally we assign the new items to the one from the stack Okay so let's execute these now and let's 05:21.260 --> 05:21.890 see what we'll get. 05:22.070 --> 05:22.390 Okay. 05:22.670 --> 05:33.020 So we've got four three two one which is we push one push to push three push for the top four times 05:33.350 --> 05:35.060 which is gonna be backwards. 05:35.150 --> 05:37.790 You're gonna get four three two one. 05:37.880 --> 05:40.570 Now what happens if we put another element. 05:40.640 --> 05:41.670 What do you think will happen. 05:42.230 --> 05:43.060 Let's figure that out. 05:43.550 --> 05:51.140 We have an error and the error says slides bounce out of range which means that we're trying to reach 05:51.230 --> 05:55.920 an element which is not part of our slide. 05:56.160 --> 06:04.740 So we need to other conditions here which is one of the if items is equal to zero which means our items 06:04.770 --> 06:06.090 are empty. 06:06.210 --> 06:10.190 Let's return minus 1 Okay. 06:10.640 --> 06:16.450 So if we saw minus one this means that we're popping up over a stack which is empty. 06:16.580 --> 06:17.930 Let's execute this 06:21.630 --> 06:21.930 yeah. 06:21.970 --> 06:23.190 Sorry we move this. 06:23.980 --> 06:31.120 Let's add some extra cops and we got the four numbers that we pushed previously. 06:31.120 --> 06:32.750 Plus two extra minus one. 06:33.280 --> 06:41.170 Now we can do a small improvement in our code because if you take a look we're calling line item line 06:41.320 --> 06:44.320 item and line item three times. 06:44.320 --> 06:53.080 So we can simplify these by saying let's replace these by left and the left is going to be the size 06:53.170 --> 06:56.100 of our items. 06:56.300 --> 06:59.570 This is creating the variable. 06:59.570 --> 07:03.380 Let's make sure this is still working and it is. 07:03.380 --> 07:13.520 So to recap we've seen this stock data obstruction that it defines to Operation Push and Pull pull is 07:13.520 --> 07:23.950 very simple because we rely on the built in slices that the language brings is kind of more complex 07:23.950 --> 07:32.980 of what we need is First we calculate the size of the current pack if the stack is empty we return to 07:33.050 --> 07:34.760 Santina which is a minus one. 07:34.880 --> 07:41.840 We can do whatever we want here that we need to make sure that this is happening and then we see the 07:41.840 --> 07:48.900 double assignment which is one variable here and one variable here the first one is an element it's 07:49.000 --> 07:54.660 an element from the array and the second one is a slice which is a sub array. 07:55.010 --> 07:59.930 Both points to the last element when we got the new slice. 07:59.960 --> 08:03.550 We assign it to our own and we return the item. 08:03.560 --> 08:05.000 So this is pretty much it. 08:05.030 --> 08:12.620 As I told you you might never use this data structure your production code but it's very good to know 08:12.650 --> 08:17.720 how to do it because it will give us some practice around what we've already learned. 08:17.870 --> 08:19.670 So this is it by.