[MUSIC] Okay, now we're going to turn to an iconic data structure, the abstract data type, stack. And think about how when you were in high school when you go to the cafeteria, there would be a stack of trays. They would be on a spring, you would take the top tray off and then if you were good about it, you would put the top tray back. And that's called last in first out, because whatever was last on would be the first one taken off. So we call that LIFO and this is what we call a canonical non-trivial data structure. It appears a lot in both computer algorithms and even in computer architecture, so it's very very useful. Along with a data structure, there is a set of verbs, the actions you can do to the data structure. So the actions that we are used to with a stack are push and pop. Those are the chief two actions, they're inverses. Then there's a way of looking at the top, seeing if the stack is empty. Seeing if the stack is full and then resetting the stack. So those will be the operations that we're going to build to have a full data structure. And we can see, here are some stacks, there's a stack of books. Again, you're not going to take a book out of the middle. You take it off the top, you put it back in the top. Here's a stack of Legos, you're not going to connect in the middle. You're going to put one on the top as you grow them or you take one off the top as needed. And here, conceptually, is a stack and you can see, here's element 2 being pushed onto the stack and then the stack is 2 + 1. Here's an element 3 being pushed on the stack, and then it grows to 3, 2, 1, 4, 5, 6. And here's your pops, and notice, as you push them, 2, 3, 4, 5, you pop them in reverse order, 6, 5, 4, 3, 2. And we'll see in a second that if you want to invert some list string, whatever. A stack is a convenient abstract data type where you push things on and then you pop them off and you get them in reverse order. How you're going to implement that in the C language? Well, we're going to go back to our struct. We're going to say typedef struct stack. We're going to build it as an array of something called MAX_LEN. We're going to have an element, in this case, we're going to stick chars in. Now, in general, in a stack, you will have some arbitrary type of element that you'll put in the stack. So, you'll need to have a stack of different kinds of elements. For each kind of element, you'll necessarily have a different stack. And some very advanced implementations of this, there is a way to deal with the generic element but we're not going to talk about that. And then the top of the stack, whatever is currently the top of the stack, will be a pointer top, that'll be a index top. And that's our data structure stack, and you can see the underlying representation is an array. More advanced classes will be able to say there's other ways to implement in a stack. Let's see how we perform a push, so putting something on the stack is going to be one of our arguments. It'll be a char and, to access the stack, we're going to do it through a pointer, because the stack is going to be changed. And the stack is in effect an array, so, We could have this as a stack stk as well. So here we have stack point at top auto increment. That means there's an element that the top, the current top, add one to the current top. So the new top index is one more and then stick in that current top, stack that top, the character we want C, and that's it. Okay, so these are some of the basic ideas, this is a non-trivial abstract data type. We're going to see some more advanced data types as well. And in the next segment, I'm going to develop all the code. We'll see it as a code base that will implement the full representation of stack, with all the different operations, push, pop, reset, Etc. [MUSIC]
