[MUSIC] A stack is a last-in, first-out data structure that is similar to a pile of papers or a stack of papers on a desk. So if you imagine a paper that has a number four placed on your desk, and then on top of the paper with number four you put a paper that has a number five. And on top of number five you put the number eight, and on top of number eight you put number three. As you look at the stack, the paper on top with the number three will be the first paper you grab. And then that way the last paper you put down is the first paper to come out. We're visually representing the idea of a stack by having the same syntax to queue of a list that has barriers on both sides. And then having the input and output arrows right here at the same spot. Similar to all data structures, we're going to look at the abstract data type first. There's four operations on a stack. A stack can create, which creates an empty stack. It can push, which adds data to the top of the stack. It can pop, which removes data from the top of the stack. Or it's empty, which returns whether or not the stack is empty or not. Notice that this ADT is identical to the QADT. We can consider an example with a stack. Let's consider a stack of integers. We're going to place 4 on top of the stack and then we'll place 2 on top of the stack. Next thing is we'll pop a number off the top of the stack, looking at what's on top of the stack, we move 2. So 2 comes out of the stack when we're using a stack data type. The C++ standard template library provides us a stack as part of the base library. std::stack initializes a stack. Here is n std::stack using of standard strings. The variable name is s. We're going to go ahead and push three things on this stack, so I'm going to go ahead and draw out my stack. I'm going to push Orange onto the stack. Then push Blue, and finally, push Illinois. I'm now going to go ahead and pop off the element by looking at the top element and then popping off. So, I'm going to take Illinois, and I'm going to go ahead and output this out. So, Illinois is the first thing that's popped off the stack. Since I popped it off, I can remove it altogether. Next thing, I'm going to add Illini. It goes in, goes to the front of the stack. And then the second pop, I can go ahead and look at that top element, it is Illini. So this code is identical to the code we saw for a queue, except for the fact that we use a stack here instead of a queue. The push and pop operations are the same. But the way they enter and exit from the data structure changed dramatically. Here we expect the result to be Illinois and Illini.Let's see what actually happens when we run this code. Here in the console I'm going to move into the stack directory, run make, and dot slash main. Our first pop indeed got Illinois. And our second pop got Illini. So we see we have code that we can play around with and see how a stack works. Let's examine how we might build a stack if we wanted to build one ourself. A stack can be built with any type of collection. And here, we're going to examine a stack with an array-based collection. Here with an array, as we insert elements in the stack, we likely will put the element at the very end of our capacity. So I'll put in the last available index, so as I insert 4, 2, 8, 7. Then I will store a counter on exactly which index I'm at. So here I've been inserting things at index 5, and the next index will be inserted in index 4. When I need to remove, I'll remove from index 5. If I run out of space, and I've reached index 0, I can simply expand the array out this way. And give myself more space to insert more elements. Let's look at an example. I'm going to label the indices of our array, And after labeling indices of the array, I'm going to keep track of the insert location. So I'm going to be inserting at index 4. So I'm going to go ahead and push 1 onto the stack. I'll update my insert location to 3. Push 2 onto the stack, up domain insert location to index 2, push 3 onto the stack and then pop out the element at the front of the stack, popping out 3, removing it from the array. Then I go ahead and push 4, which now gets inserted here. Push 5. Pop out top element in stack, we're going to pop out 5. Remove it from the stack. Here we're going to need to push 6, push 7, and we're about to push 8. But we're out of space. So since we're out of space, we know we're out of space because the next insert location is going to be effectively negative 1. We don't have an index at negative 1. So instead we're going to need to expand this array. What we'll simply do is double the size. So we'll create an array with ten indices. And copy over the data, 1, 2, 4 6, 7. The next location to insert it is going to be here at the new index 4. I mean go ahead and insert 8. Awesome, a linked list is even easier. The thing about linked list, when the stack is initially empty we're going to have a links list that simply points to null. When we add our first element, we simply update the front of the list. And add that element. When we add a second element, we just insert at the front of the list again. And now we have a list with two elements. So here Is a stack that has four elements on it already, maybe 4, 2, 8, 3. When we want to remove the front element from a list, we just remove this front element and update the head pointer. It's only three lines of code. Extremely simple. So the implementation of a stack in a list is quite easy and only requires operations that only take a few lines of code. These are also O(1) operations. We see here is as long as we are intelligent about the data structure we use and use optimal implementations such as doubling the size of the array when we're pushing and popping from the array, we can see that all of our operations on a stack is O(1). Unlike a queue on a stack, a singly-linked list is sufficient for a stack. Because we don't have to use tail pointer, all of our operations happen at the front of the list. A stack is a last-in first-out data structure that mimics a stack of papers on your desk. A stack might be implemented within an array or linked list and all of the operations in a stack runs in O(1) time. What this means is no matter if we need stack or a queue for our purpose, if we use either of those data structures we can ensure that all of those operations are going to take fixed constant amount of time, no matter if there is one element of data or 1 million elements of data. This is a powerful fact that will allow us to build better and stronger data structures. We'll keep diving into data structures more, so Ill see you then.
