Okay. We're going to turn to some code now where I implemented a basic stack with all of its operations. Remember, this is abstract datatype, user-defined, and it's fully featured. So let's look at how I've done that. I described a lot of it in the last lecture. But here we'll see it in code. So I have a max length. My stack can have up to a 1,000 elements in it. I define empty when I want to know when this stack has any more elements because if it's empty and I try to perform a pop on it, I will get an error. I also need to know when it's fallen, they no longer can stick things in the stack. So those will be two constants that the stack will need. Here again is my typedef for the stack. It's basically implemented as a character array. So the kind development I'm storing in the stack has to be char. So it's here. Do you want a different kind of stack that you have to change what you would use? Again, we have a series of basic operations. The first operation is a reset, and most of these operations are going to operate on a pointer-to-stack and so we're going to have to be familiar with a pointer access. So in this case, we just set the stack and the top of the stack to empty, and that's a reset. In other words, we're ready to start with whatever is in the stack with the stack empty. Then we have the basic operation push, which we described before namely, we stick something, we increment the top of the stack, and then we stick something in what's now the new top. Again, if there was a different type of element, it wouldn't be char c. It would be whatever type that was. It could even be it's own user-defined type if we need something more complex. In each case, we would stick it into the stack. For something more complex, we would have to makes sure that we might have to use a routine instead of assignment that we are going to work on simple native types typically. Then pop C inverse operation to push. Again, we have star stack pointer-to-stack. A pop is we take something off the current top of the stack, return that value, and then decrement the stack top. So that's it's very important that we use postfix here. Post-fix is critical to having this operation act right. If we use prefix there, we would not be taking something off the top of the stack. We'd be taking something off the next to the top of the stack. Then if we just want to examine the top of the stack, we use this operation is just as look at the top of the stack, but it doesn't affect the stack. That's why we can use const there. The stack is not affected. So these are almost the same. It both get a char off to stack, but one pops it m and one just examines it. Then we have the two operations to check on whether something is empty. Empty is if the stack top is equality to empty, full is stack top equality to full. Let's now use our routine. We're going to use it to reverse the string. So "i am otto am i" that can be stored backwards in a character string of roughly less than 20 characters, and we reset to stack. We print the original. So this will be the original string. So what should show up? "i am auto am i" and then we go ahead and while the string is not the end of string character, namely the zero, and this is again recognize it as an idiom for working on strings. I'm going to print that character individually, and then I'm going to push the character onto the stack. So notice that because everything was pointed too, this has to be ampersand of stack. Remember all of our pointer operations again, you'll have to refer to it. You got to get used to it. This is some of the more advanced concepts. This is where a lot of students stumble. So you have to maybe if this is unfamiliar to you work fairly hard at this idea. Address of is what's going on there. Remember we also use that with scanf, and now we reverse it by looking at while is empty and the stack. We know the stack is less than 20. We're going to push pop the stack into string back and then we're going to see if indeed that lifo mechanism will reverse it. So I've already compile this program and there I am. Original is, "i am otto am i". Here are the individual letters as they are pushed onto the stack. I, whitespace, am, whitespace, otto, whitespace, am, whitespace I. Then the reverse when I've stored that back into a character array is i ma otto ma i, right? Is really first. So I dot. So you now see at full implementation of stack. You've seen an algorithm that provides reversal standard algorithm, and this is a serious non-trivial data structure widely in use in computer algorithms and in computer science in general.
