DOUG LLOYD: All right, so by this point you're probably pretty familiar with arrays and linked lists which is the two primary data structures we've talked about for keeping sets of data of similar data types organized. Now we're going to talk about a couple of variations on arrays and linked lists. In this video we're going to talk about stacks. Specifically we're going to talk about a data structure called a stack. Recall from previous discussions about pointers and memory, that the stack is also the name for a segment of memory where statically declared memory-- memory that you name, variables that you name, et cetera and function frames which we also call stack frames exist. So this is a stack data structure not a stack segment of memory. OK. 

But what is a stack? So it's pretty much just a special kind of structure that maintains data in an organized way. And there's two very common ways to implement stacks using two data structures that we're already familiar with, arrays and linked lists. What makes a stack special is the way in which we put information into the stack, and the way we remove information from the stack. In particular with stacks the rule is only the most recently added element can be removed. 

So think about it as if it's a stack. We're piling information on top of itself, and only the thing at the top of the pile can be removed. We can't remove the thing underneath because everything else would collapse and fall over. So we really are building a stack that we then have to remove piece by piece. Because of this we commonly refer to a stack as a LIFO structure, last in, first out. LIFO, last in, first out. 

So because of this restriction on how information can be added to and removed from a stack, there's really only two things we can do with a stack. We can push, which is the term we use for adding a new element to the top of the stack, or if the stack doesn't exist and we're creating it from scratch, creating the stack in the first place would be pushing. And then pop, that's the sort of CS term we use to remove the most recently added element from the top of the stack. 

So we're going to look at both implementations, both array based and linked list based. And we're going to start with array based. So here's the basic idea of what the array based stack data structure would look like. We have a typed definition here. Inside of that we have two members or fields of the structure. We have an array. And again I'm using the arbitrary data type value. 

So this could be any data type, int char or some other data type you previously created. So we have an array of size capacity. Capacity being a pound defined constant, perhaps somewhere else in our file. So notice already with this particular implementation we are bounding ourselves as was typically the case with arrays, which we cannot dynamically resize, where there's a certain number of elements maximum that we can put in our stack. In this case it's capacity elements. 

We also keep track of the top of the stack. What element is the most recently added to the stack? And so we keep track of that in a variable called top. And all of this gets wrapped up together into a new data type called a stack. And once we're created this new data type we can treat it like any other data type. We can declare stack s, just like we could do int x, or char y. And when we say stack s, well what happens is we get a set of memory set aside for us. 

In this case capacity I've apparently decided is 10 because I've got a single variable of type stack which contains two fields recall. An array, in this case is going to be an array of integers as is the case in most of my examples. And another integer variable capable of storing the top, the most recently added element to the stack. So one single stack of what we just defined looks like this. It's a box containing an array of 10 what will be integers in this case and another integer variable there in green to indicate the top of the stack. 

To set the top of the stack we just say s.top. That's how we access a field of a structure recall. s.top equals 0 effectively does this to our stack. So again we have two operations that we can perform now. We can push and we can pop. Let's start with push. Again, pushing is adding a new element to the top of the stack. 

So what do we need to do in this array based implementation? Well in general the push function is going to need to accept a pointer to the stack. Now take a second and think about it. Why would we want to accept a pointer to the stack? Recall from previous videos on variable scope and pointers, what would happen if we just sent stack, s rather in as a parameter? What would actually be passed in there? Remember we're creating a copy when we pass it to a function unless we use pointers. And so this function push needs to accept a pointer to the stack so that we're actually changing the stack we intend to change. 

The other thing push probably wants to accept is a data element of type value. In this case, again, an integer that we're going to add to the top of stack. So we've got our two parameters. What are we going to now do inside of push? Well, simply, we're just going to add that element to the top of the stack and then change where the top of the stack is, that s dot top value. So this is what a function declaration for push might look like in an array-based implementation. 

Again this isn't a hard and fast rule that you could change this and have it vary in different ways. Perhaps s is declared globally. And so you don't even need to pass it is as a parameter. This is again just a general case for push. And there are different ways to implement it. But in this case our push is going to take two arguments, a pointer to a stack and a data element of type value, integer in this case. 

So we declared s, we said s.top equals 0. Now let's push the number 28 onto the stack. Well what does that mean? Well currently the top of the stack is 0. And so what's basically going to happen is we're going to stick the number 28 into array location 0. Pretty straightforward, right, that was the top and now we're good to go. And then we need to change what the top of the stack will be. So that the next time we push an element in, we're going to store it in array location, probably not 0. We don't want to overwrite what we just put there. And so we'll just move the top to 1. That probably makes sense. 

Now if we want to put another element onto the stack, say we want to push 33, well now we're just going to take 33 and put it at array location number 1, and then change the top of our stack to be array location number two. So if the next time we want to push an element onto the stack, it'll be put in array location 2. And let's do that one more time. We'll push 19 off of the stacks. We'll put 19 in array location 2 and change the top of our stack to be array location 3 so if the next time we need to make a push we're good to go. 

OK, so that's pushing in a nutshell. What about popping? So popping is the sort of counterpart to pushing. It's how we remove data from the stack. And in general pop needs to do the following. It needs to accept a pointer to the stack, again in the general case. In some other case you might have declared the stack globally, in which case you don't need to pass it in because it already has access to it as a global variable. But then what else do we need to do? Well we were incrementing the top of the stack in push, so we're probably going to want to decrement the top of the stack in pop, right? And then of course we're also going to want to return the value that we remove. If we're adding elements, we want to get elements out later on, we probably actually want to store them so we don't just delete them from the stack and then do nothing with them. Generally if we're pushing and popping here we want to store this information in a meaningful way and so it doesn't make sense to just discard it. So this function should probably return a value to us. 

So this is what a declaration for pop might look like there at the top left. This function returns data of type value. Again we've been using integers throughout. And it accepts a pointer to a stack as its sole argument or sole parameter. So what is pop going to do? Let's say we want to now pop an element off of s. So remember I said that stacks are last in, first out, LIFO data structures. Which element is going to be removed from the stack? Did you guess 19? Because you'd be right. 19 was the last element we added to the stack when we were pushing elements on, and so it's going to the first element that gets removed. It's as if we said 28, and then we put 33 on top of it, and we put 19 on top of that. The only element we can take off is 19. 

Now in the diagram here what I've done is sort of deleted 19 from the array. That's not actually what we're going to do. We're just going to kind of pretend it isn't there. It's still there in that memory location, but we're just going to ignore it by changing the top of our stack from being 3 to 2. So if we were to now push another element onto the stack, it would over write 19. 

But let's not go through the trouble of deleting 19 from the stack. We can just pretend it isn't there. For purposes of the stack it's gone if we change the top to be 2 instead of 3. All right, so that was pretty much it. That's all we need to do to pop an element off. Let's do it again. So I've highlighted it in red here to indicate we're making another call. We're going to do the same thing. 

So what's going to happen? Well, we're going to store 33 in x and we're going to change the top of the stack to 1. So that if we were now to push an element into the stack which we're going to do right now, what's going to happen is we're going overwrite array location number 1. So that 33 that was sort of left behind that we just pretended isn't there anymore, we're just going to clobber it and put 40 there instead. And then of course, since we made a push, we're going to increment the top of the stack from 1 to 2 so that if we now add another element it'll go into array location number two. 

Now linked lists are another way to implement stacks. And if this definition on the screen here looks familiar to you, it's because it looks almost exactly the same, in fact, it pretty much is exactly the same as a singly linked list, if you recall from our discussion of singly linked lists in another video. The only restriction here is for us as programmers, we're not allowed to insert or delete randomly from the singly linked list which we could previously do. We can only now insert and delete from the front or the top of the linked list. That's really the only difference though. This is otherwise a singly linked list. It's only the restriction replacing on ourselves as programmers that changes it into a stack. 

The rule here is to always maintain a pointer to the head of a linked list. This is of course a generally important rule first. For singly linked list anyway you only need a pointer to the head in order to have that chain be able to refer to every other element in the linked list. But it's particularly important with a stack. And so generally you're going to actually want this pointer to be a global variable. It's probably going to be even easier that way. So what are the analogs of push and pop? Right. So pushing again is adding a new element to the stack. In a linked list that means we're going to have to create a new node that we're going to add into the linked list, and then follow the careful steps that we've outlined previously in singly linked lists to add it to the chain without breaking the chain and losing or orphaning any elements of the linked list. And that's basically what that little blob of text there summarizes. And let's take a look at it as a diagram. 

So here's our linked list. It concurrently contains four elements. And more perfectly here's our stack containing four elements. And let's say we now want to push a new item onto this stack. And we want to push a new item whose data value is 12. Well what are we going to do? Well first we're going to malloc space, dynamically allocate space for a new node. And of course immediately after we make a call to malloc we always make sure to check for null, because if we got null back there was some sort of problem. We don't want to dereference that null pointer or you will suffer a seg fault. That's not good. So we've malloced of the node. We'll assume we've had success here. We're going to put 12 into the data field of that node. Now do you recall which of our pointers moves next so we don't break the chain? We have a couple of options here but the only one that's going to be safe is to set news next pointer to point to the old head of the list or what will soon be the old head of the list. And now that all of our elements are chained together, we can just move list to point to the same place that new does. And we have now effectively pushed a new element onto the front of the stack. 

To pop we just want to delete that first element. And so basically what we have to do here, well we have to find the second element. Eventually that will become the new head after we delete the first one. So we just need to start from the beginning, move one forward. Once we've got a hold on one forward of where we currently are we can delete the first one safely and then we can just move the head to point to what was the second term and then now is the first after that node has been deleted. 

So again, taking a look at it as a diagram we want to now pop an element off of this stack. So what do we do? Well we're first going to create a new pointer that's going to point to the same spot as the head. We're going to move it one position forward by saying trav equals trav next for example, which would advance the trav pointer one position forward. Now that we've got a hold on the first element through the pointer called list, and the second element through a pointer called trav, we can safely delete that first element from the stack without losing the rest of the chain because we have a way to refer to the second element forward by way of the pointer called trav. 

So now we can free that node. We can free list. And then all we need to do now is move list to point to the same place that trav does, and we're sort of back where we started before we pushed 12 on in the first place, right. This is exactly where we were. We had this four element stack. We added a fifth. We pushed a fifth element on, and then we popped that most recently added element back off. 

That's really pretty much all there is to stacks. You can implement them as arrays. You can implement them as linked lists. There are, of course, other ways to implement them as well. Basically the reason we would use stacks is to maintain data in such a way that the most recently added element is the first thing we're going to want to get back. I'm Doug Lloyd, this is cs50.