In the previous lectures, we discussed the List ADT. The implementations, both array-based and linked, allow us to add, change, or remove elements from anywhere on the list. However, in some cases we want to have a different, more restricted behavior from a data structure. Whereas the List ADT is one of the least restrictive ADTs, the stack ADT is one of the most restrictive. Just like a stack of books in an office or cafeteria plates in a food court, the stack ADT can be visualized as elements sitting on top of one another. The element at the very top of the stack is not surprisingly called the top. Implementations of the stack ADT should only allow the user to insert or remove elements from the top of the stack. In other words, the top is the only place that is directly accessible in a stack. If you want elements lower than the top, you have to remove the top first, and then subsequent elements become the new top, which you'd also have to remove to get to lower elements. Inserting elements at the top of the stack is called pushing the elements onto the stack. Each new element pushed onto the stack becomes the new top of the stack. Removing elements from the top of the stack is called popping elements from the top of the stack. You can also examine the top of the stack without removing it, which is done with an operation typically called peek, or getTop, or sometimes even just top. If you've been through the entire course so far, you probably remember that we've actually encountered the stack before. Do you remember where? That's right, the call stack was discussed earlier in the course when we talked about functions. Given the restrictions of the stack, let's come up with the code for the abstract class Stack. Then we'll be able to implement its methods to create data structures that we can use. First, let's create the ArrayStack project in Visual Studio. All right, so we have ArrayStackApp, I'm going to create this. And then, kind of like we did before, we're just going to have a Stack.h and a main.cpp. So, I'm going to add a new item. This is just going to be the Stack.h. Right here, Stack.h, and we're going to have a CPP file- main.cpp. This one I'll give a skeleton. And come back to this in just a little bit. So, for the Stack.h, we're going to give it an include guard to start off with. Let's do #ifndef STACK_H, and then #define STACK_H, and then #endif. Class Stack, and we just have public on this because this is an interface, it's going to have all pure virtual methods. virtual void push (), a newEntry onto the stack, pop(), an entry off of the stack, peek(), this one's const because it doesn't modify the stack. Same thing for isEmpty() and then we're going to have, or we'll just use void on this one, I guess, makeEmpty() This one can't be const because it modifies the stack. It's basically just going to keep popping until it's empty. All right. So, with the stack we actually have far less to implement than we did with the list, largely because the stack has so many restrictions on its interface. So, the next obvious question is- how can we implement it? Good question. An array-based implementation is what we'll do in this lecture. Our other options would include a linked-chain based implementation working directly with the nodes, like we did with the list or we could even use the LinkedList implementation itself that we made before as the underlying data structure, and simply restrict how people interact with it from the outside. So, we do have options, but for now let's work with an array-based implementation- the ArrayStack. So, let's create ArrayStack.h. All right, so here we go. ArrayStack.h. And this one, of course, #ifndef ARRAY_STACK_H. ARRAY_STACK_H. And then, #endif. And of course, we will include Stack.h  so we can access the interface. We're going to include iostream. All right, so class ArrayStack inherits publicly from the Stack class. We have a public section, and we're also going to have a private section. So, for this one, the private section, which is not specified by the stack ADT of course, because that gives ideas about the implementation. We're going to have an array just like we did with the ArrayList. A MAX_SIZE should be familiar. And here, int top, that's going to keep track of the top of the stack. What we're going to do now is we're going to implement the different portions of this implementation of this particular ArrayStack implementation. The first is going to be the constructor, of course, and we can initialize again the constant by using the initializer syntax.

Now what we're going to do here is we're going to use -1 indicates no elements in the stack. Now there's other ways we can do this, but this is what I'm choosing to do for this implementation. All right. So, we're good with that. Now we have to do push. So, void push, pushing a newEntry. We could also copy over or just get ready the rest of the methods. I think I'm going to just copy them over and give them bodies, so I'm going to copy that, and then go over here, get rid of the virtual and that extra space. And then I'm going to just return some dummy data just so it will compile. Okay, make sure we leave the const, return false. All right. And again, that's called stubbing out the method, just to get it to compile. We come back and actually fill in the details later. So, right here for push, as long as the top is less than the MAX_SIZE -1, we do top++, okay. And we're going -1 because we're actually starting at -1 to indicate that the ArrayStack is empty, because that's not a valid top. So, after we incrementally increment it first, so the first time around, for example, it'll go from -1 to 0, that will be a valid index on the array. And again, there's more than one way to do this. We're going to put an "Error: Stack is full! Cannot push!" Okay, and again, you could, and if you're doing an industrial level industrial strength code, you should probably do exception handling instead. But we're doing this just to keep it easy. And if you haven't gone over the exception section, you can still understand this without too much trouble. All right. So, if it's not empty, we set the data = mArray[top], so this is pop again. And then, that's pretty much what we expect. We just grab the data to return, and then reduce the top. Now the array still exists and that data will still exist at the top of the array, just like it did with the list. But we're treating it like it's not actual valid data. It's just sitting there in the array doing nothing, it's never going to be accessed again. If that cell gets accessed again, it'll be different data. All right. So, "Error! You cannot pop on an empty stack!" There we go. peek(), also not too bad. So, for peek(), we're going to set int data = 0, and then return data at some point. Now again you have to pay close attention to the actual printing here because the data may not be valid. But at this case, we're just peeking, we're not moving the top or changing the top. So, we are just grabbing the data at the top mArray[top]. And then printing out "The stack is empty." Like that. Could say error the stack is empty if you wanted. Now, is empty is pretty easy since we know that we've decided that -1 means the top is or rather the stack is empty. We're just going to return top == -1. And again, this is the comparison equality operator rather than an assignment operator, you'll get a completely different behavior that you wouldn't expect maybe. So, be careful with that. To make empty it's very simple, we just set the top = -1. And yes, there will still be data in the array but we are not deleting the data, we are just treating it like it doesn't exist or like it's invalid. So, before you actually fill the array up, it had garbage data in there and we don't treat that like it's valid and it's the same thing here. Now, let's go to main before we can test it here. We're going to include "ArrayStack.h" using namespace std. Oops, already had that. So, we will delete one of these. That's okay. ArrayStack, we will just call it stack and then for i = 0, i < , we'll say, 17. So, they'll fill it with all 16 items, stack.push.

And then we'll do while not stack.isEmpty as long as the stack is not empty. Just print out stack.pop. Pretty cool. And now, let's run it of course. Build it, make sure it's not broken. And we're going to run it. Good. So, when it got to the 17th item it actually prints out this, I can't push onto the full stack. And then it goes into the while loop and starts printing all the way from 15 down to zero. You'll notice they are in the opposite order of the order we added them in. And that's what we expect because a stack, again, is a last in, first out data structure. Excellent work. Before we move on, I have a challenge for you. As I'm sure you noticed and as mentioned, the elements as popped from the stack are in the opposite order to what they were added as. What I'd like you to do is use the current code but enhance it, and do some more printing to verify the solution. You're not going to modify the stack itself but you're going to modify this file with main in it, you need to use a second stack and use it in a way that will allow you to print the elements that were added to the first stack in the original order. But you use it to restore the stack to what it originally was, the original stack.

This is a tiny bit tricky but I'm pretty sure you'll be able to figure it out. But it's no problem if you don't, we all get stumped sometimes, but I have confidence in you. 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 go for you? Were you able to complete this challenge? Let's work on it together. Well, we have to create a second stack. We know that and what we're going to do in this while loop instead of printing it out because we do want to print it out but we destroyed the stack along the way. So, what you're going to do as you stack2 to push what the original stack is popping. Now that will be in the opposite order of what the stack, original stack has, so i.e. the original order that we entered it and then to put it back, all we have to do is put it back in the original stack. So, you basically just take the original stack and then pop the stuff off of a  stack2 into the original stack. So, if we want to print out, for example, the same order. Just to print it out instead of restoring it to the original stack, we could just do this. stack2.pop, we could do that. Now, if we want to actually restore the original stack, we could take that data and we're going to print it out of course at some point here.

This is going to be in the original order that we entered it. And then stack is going to push what stack2 has or put data because we already popped it. All right. And of course, let's run it. Let's see what goes on here. All right. So, that didn't work real well, did it? So, the reasoning is we need to put stack2 not isEmpty, not stack. All right. Here we go. There we go. So, kind of same situation here, this is from the original and then we print out the original order. Now, obviously this is the order that it was actually entered in to start with. Pretty cool. And the original stack has restored the second stack that we used intermediately is now empty. And we've printed out the data in that order. If we wanted to print it out in the original order, we'd have to pop it again from the original stack. All right, nice work. In the next lecture, we'll look at the link-based implementation of the stack ADT. I'll see you there.