WEBVTT 00:00.120 --> 00:06.540 Hello again! In this video, we are going to look at the stack data structure. This works rather like 00:06.540 --> 00:10.290 a pile of plates, so let's remind ourselves what that looks like. 00:11.760 --> 00:17.130 We're going to specify that we can only add or remove one plate at a time from this pile. 00:17.940 --> 00:21.540 If we want to remove a plate, we have to take this one off the top. 00:22.540 --> 00:25.450 And then the one below that now becomes the top of the pile. 00:26.050 --> 00:28.720 And if we take that one off, the one below becomes the top and so on. 00:30.230 --> 00:34.490 If we add some more plates, we have to add them one at a time, at the top. 00:35.150 --> 00:40.580 So we add a new plate here. And that now becomes the top of the pile. And we can add another plate on 00:40.580 --> 00:41.540 top of that, and so on. 00:42.920 --> 00:48.530 So the plate at the top is always the last one which was added to the pile, and the plate at the bottom 00:48.530 --> 00:50.960 is always the first one which was added to the pile. 00:51.980 --> 00:56.620 When we take a plate from the top of the pile, it will always be the last one which was added. 00:59.190 --> 01:04.890 In the stack data structure, the elements are stored in the order in which they were added to the stack. 01:05.760 --> 01:12.480 When we add a new element to this attack, it is inserted at the top. And we can only access the top 01:12.480 --> 01:13.440 element of the stack. 01:15.800 --> 01:21.860 To process the stack, we need to get the top element and remove it. So the element which was 01:21.860 --> 01:26.150 below that now becomes the top element. Then we can access that. And so on. 01:27.390 --> 01:30.360 The elements are removed in the reverse order they were added. 01:30.750 --> 01:36.090 So the last element which was added is always the first one to be removed. And this is known as a 01:36.090 --> 01:39.690 "LIFO" structure. Short for "Last In, First Out". 01:42.990 --> 01:47.190 So it works something like this. So imagine we have a data structure with three elements. 01:49.170 --> 01:53.670 We added 1, then 2 and then 5. So 5 is currently the top element. 01:54.390 --> 01:57.750 If we add another element, it's going to go above 5. 01:58.800 --> 01:59.400 Like that. 02:01.590 --> 02:03.990 So we now have 3 as the top element. 02:05.790 --> 02:11.070 If we come along and remove the top element, then this 3 will be removed. 02:11.400 --> 02:13.080 And then 5 is going to be the top again. 02:13.950 --> 02:15.180 So it will look like that. 02:19.030 --> 02:21.670 C++ has a stack class in the library. 02:22.120 --> 02:26.770 It is implemented using a deque, for the same reason that the queue uses a deque. 02:27.790 --> 02:30.460 The interface is very similar to priority queue. 02:31.060 --> 02:38.830 We can use push() and pop() to add and remove elements, at the top of the stack only. top() will return the element 02:38.830 --> 02:40.750 from the top of the stack, but leave it there. 02:41.650 --> 02:44.290 So this is like top() in the priority queue. 02:44.650 --> 02:50.700 We can inspect the value, but not modify it, because it is returned as a reference to const. And there 02:50.710 --> 02:53.260 are also empty() and size() member functions. 02:55.680 --> 02:57.060 So let's try this out. 02:57.510 --> 03:02.790 We include the header, and then we can create a stack object. 03:04.240 --> 03:06.700 We call push() to insert some elements. 03:07.150 --> 03:09.280 So 1 is the first element, then 2. 03:09.670 --> 03:12.250 So 2 will go above 1. And then 5. 03:12.310 --> 03:17.170 So 5 will go above 2. And 5 is currently the top of the stack. 03:18.070 --> 03:21.520 We have this function for printing out some information about the stack. 03:23.110 --> 03:27.080 Then, when we add a new element, this will go on the top of the stack. 03:27.100 --> 03:30.790 So if we call top(), we will now get 3 as the top of the stack. 03:32.230 --> 03:35.530 And for removing an element, this will take the top element off. 03:35.950 --> 03:41.260 So this will remove the element with value 3, and we go back to having 5 at the top. 03:44.090 --> 03:47.270 So there we are, we start off with our three elements with five at the top. 03:48.510 --> 03:54.720 Then we add 3, and that goes to the top. And then we remove this top element, and we go back to 03:54.720 --> 03:55.920 the stack that we had before. 03:59.590 --> 04:02.260 Stacks are actually very useful in computing. 04:03.100 --> 04:07.180 They're used by the C++ runtime for managing local variables, 04:07.270 --> 04:12.760 as we all know. Compilers also use them for breaking down expressions into sub-expressions. 04:13.540 --> 04:17.200 You can use them for checking for unbalanced parentheses in source code. 04:17.860 --> 04:22.120 Every time you encounter an open bracket, you push it onto your stack. 04:22.840 --> 04:26.200 And when you meet a closing bracket, then you pop it off the stack. 04:26.920 --> 04:31.780 And if you get some stack error, or you get to the end of the file and you have some elements left, 04:32.170 --> 04:34.450 then you know that the brackets are not balanced correctly. 04:36.240 --> 04:42.100 You can also use it for implementing undo functionality. So every time the user edits the text, or your 04:42.100 --> 04:47.730 program changes something, you can push the old state onto the stack. And then you can just pop it off 04:47.730 --> 04:48.720 to get back to where it was. 04:49.590 --> 04:54.810 And also for browser history, when you're on the web. Every time you go to a new URL, you can 04:54.810 --> 04:55.740 push it onto a stack. 04:56.720 --> 04:58.310 OK, so that is it for this video. 04:58.760 --> 05:02.090 I will see you next time, but until then, keep coding!