We just got done doing some awesome things with the Queue ADT and its implementations. Now it's time to focus on the List and Stack ADTs a bit and use them together in an interesting way. In this project lecture, you will use the LinkedList that we implemented earlier in this section as the backing data structure for your new class, ListStack. In other words, in the private section of the ListStack class, you will have a LinkedList object. The LinkedList provides a set of operations through a well-defined interface. We know that since we implemented it, you will use it though to implement a stack. Thus, for the ListStack, you won't use linked chains directly, you won't use arrays directly, but instead you will use the LinkedList to provide all the functionality you need to implement the Stack  ADT. The implementation should actually be pretty simple if you plan it out well, and some methods might be implemented with very few lines of code.

So, create a project called ListStackProject, and make sure to copy over the List.h, LinkedList.h, and Stack.h files. Maybe even the main.cpp from our LinkedStack example, and use the LinkedList to implement the ListStack in a ListStack.h file. Also, as another hint, you may notice that the List doesn't have the equivalent of a peek method that allows you to look without removing. So, come up with a solution without changing the List or LinkedList implementations. It will definitely not be as efficient as if the List had a simple peek method available, but this is a good challenge to test your ability to work with what you have available. In some cases, you might not be able to modify the classes you're using to help you in fact. All right, so before you work on the project, you might want to see what it should look like when it prints out. So, debug start without debugging. And pretty much as expected, we will end up with all these printouts from the stack, and if you've copied over the main it should basically do what it did when we did other implementations of the stack, such as the LinkStack. It'll do exactly what that did. All right, hopefully that helps.

So, pause the video and give this one your best shot. Come back when you're done or if you need some help. How did that work out for you? Will you able to complete this challenge? Let's work on it together. So, as you can see, I've copied over the LinkedList.h, List.h, Stack.h and main.cpp files. So, I've also set main up here and I'm going to modify this to have a ListStack.h. I'm going to change this to ListStack. And we don't have that yet, of course, ListStack, and then also down here the type will be ListStack and then also here ListStack. So, we will create this .h file, add new item, and we're going to make it a .h file, of course, and then, we will call it ListStack. All right, so far so good. ifindef LIST_STACK_H.

All right, we also need some includes here. All right,  inherit  from stack here. And again, we're going to get a little bit of an error over in main, but it now at least recognizes the ListStack exists. The reason we're getting the errors because it thinks we haven't implemented the abstract method yet, which we will. All righty. So, let's do this. And again, there's many ways to do this, but this is the way I'm going to do it, so public and of course, the private section. And even though we're using a linked implementation, this looks like I'm using an array based implementation, but I'm not really. So, you'll see what I'm talking about. Just a minute. There you go. So, I'm using a LinkedList as the backing data structure and then an integer called top. All right, so ListStack constructor, all I'm going to do here is set that equal to top =  -1 because it's invalid. virtual ListStack destructor. We're going to call makeEmpty, and also set the top back to -1. And we need to push and, well, this is what happens when your finger's off all the keys, push, there we go, int newEntry. So, top is implemented first.

And now, we don't have access directly to the nodes, but we can tell the stack what to do. So, are the LinkedList rather what to do? So, the linkedListStack we're going to tell it to add the newEntry. And that will add it to the front of the LinkedList because we know how the implementation works. There, pop, pop write here, int data = 0 and then eventually returned the data. If not isEmpty, we'll do one thing and then if it isEmpty, we print out an error, 'you can't pop on an empty stack!.' Excellent. And what do we do in the not isEmpty section. So, if it's not empty, then we can grab the data, .remove at the top and then top--. Perfect. So, we're making the LinkedList actually do all the work. Now, we have peek, int peek, very similar in many ways again to the pop, except it doesn't actually destroy or modify anything about the underlying data structure. So, we'll say error, "you can't peek on an empty stack!"

Now, remember we don't have a peek on our List. So, that was one of the challenges of this particular project. Was you got to work with what you have. So, even though the list is being treated like a stack, if we remove the data from the List, it's gone right? So, we have to actually temporarily store it, linkedListStack that removed the top, and we don't even document top or anything like that because we're immediately after we grab that data, we're going to add it immediately back. All right, pretty cool, pretty cool. So, we had the data right back to the length list after we just pulled it out for a second to look at it to grab the data and then put it right back in. Now, would it be better if  linklist itself had a peek method? Yes, but I left that out on purpose earlier in the course, so that we can have this interesting challenge here. Now, pass the peek method, we know have kind of the smooth sailing methods, we have is empty, and all we got to do here is we could say if the top is negative one, but I'm going to actually depend on the stack. I'm going to call the stacks is empty.

So, we would sometimes call this a pass through method. It's really not doing much of anything, except for depending on an underlying data structure. So, void makeEmpty, same thing here, calling makeEmpty on our List, we're having it do the heavy lifting. Now, as you know, most of the work is actually being done by this List. What we're doing is we're adapting the list to behave like a stack, and if you're familiar with the term design patterns, this is actually the adapter or a type of the adapter design pattern. We have adapted a data structure that does all the work for us or in the majority of the work for us for our purposes to only behave like a stack. Even though we could add data to the middle of the List or the front and the end and anywhere in between, we aren't treating it like that. We're only adding and removing from the same location, the front of the list which is behaving like the top of the stack. Perfect. Let's go over to main and over in main here, I'm going to actually delete this little comment. I copied this code over, and this right here seems to be up set still, ListStack, abstract class type ListStack. Let's see, what did we not implement that it is up set about?

Let's see. Still got the problem because this is not actually matching the Stack  ADT. So, in this particular case, we have to actually modify the interface. So, let's see if that fixes it. There we go. It actually fixed it. We had to actually modify peek because peek in this case has to actually perform or remove. So, that isn't cool, but the better solution would be to modify LinkedList to have a peek method itself. But this is what we're left with. So, let's see what happens. And that's what we expect. So, we've got the data here, printed out twice just to verify that it still works both times, and awesome. So, it works as expected, and of course, we saw what we've actually done relatively little work ourselves. The majority of the work is already done by our LinkedList, and we just have to pass the responsibility for providing various functionality onto the LinkedList from our ListStack, and just make sure that we treat the data in a stack like fashion. Everything works awesome. In the next lecture, we're going to finish off this section with our wrap up. I'll see you there.