Implementing Stacks with Arrays: Array-Backed Stack Data Structures

(upbeat chiming) Sarah: All right, so let's implement a simple stack class. I've created a project. The code in academy.learnprogramming.stacks, and I've added the usual Employee class to the project. It's a copy and paste job, so nothing new here. So we're gonna start out by implementing the stack using an array, so our stack implementation is going to be backed by an array. Arrays are great for random access, as we've learned. Do we need random access for a stack? We'll no, we don't, because we are only ever gonna be working with the top item on the stack. We are never gonna say give us the 10th item in the stack, that doesn't make sense. Stacks say that you can only ever work with the top item, because it's last in, first out. The other thing about arrays is of course they are a fixed size. They're not dynamic, and so by using an array to back a stack, we're gonna have to provide an initial size for the array and if we try to push something onto the stack when the array is full, then that's obviously not going to work. Now, for the same reasons, using a list wouldn't be that great, and when I say list I mean the ArrayList or the Vector class, because they are, as we know, backed by an array, so they'll have the same problems that arrays do. The ideal data structure to back a stack is a linked list, and we'll get back to that later. Despite the problems of using an array, they are commonly used to back stack implementations, so we're gonna start with that, so you can see how it's done. Okay, so let's get going on our implementation of a stack. So I'm gonna add a class called ArrayStack to make it clear that this implementation is backed by an array. So I'll say New Java Class, ArrayStack. We're going to need a field for the array that's going to be used to back the stack, and also we're going to need to track the index of the top position on the stack, and you'll see why we need that when we implement the push and pop methods. So we'll say private Employee, and we want an array, stack, and private int top, and so we have our backing array and we have a field that's going to track where the top of the stack is. So we need to add a constructor, because we're gonna let the caller tell us how large they want the stack to be, so in other words, the capacity of the stack, so we'll say public, ArrayStack and we'll accept an int capacity, and then inside the constructor, we'll create our array, so we'll say stack equals new Employee and it'll have a length or capacity. So remember that the capacity will be the maximum number of items that we can store on the stack, because it's the maximum number of items that we can store in the array. We are not going to explicitly initialise the top field, it's gonna be initialised to zero by default. So when top is zero, the stack is empty. Okay, so now let's implement the push method. So we'll say public void push, we don't get anything back when we push an employee, but of course we need to accept the employee instance that we are going to push onto the stack, and the first thing we need to check is whether the stack is full, so we'll say if, top equals stack.length then the stack is full. The top will always be the index where we would push the next element, and so as I just mentioned, top will be initialised to zero and so the first element that we push will be pushed into position zero, and then top would be incremented to one, and so the next element would be pushed into position one. So if the top equal stack.length, that means that the next available position is equal to the length of the array and that's actually out of bounds, and so if top equals stack.length, we know the array is full, so what we are gonna do is resize the array. So I'll put here, need to resize the backing array, so we're gonna say Employee new array equals new employee and we don't just want to increase it by one, the length, because that means if we push another element, we're gonna be back into resizing the array again, so one common way to resize the array is the double the length, and that's what we're gonna do. So we're gonna say two times stack.length, and now we're gonna have to copy all of the elements that currently exist in the stack into this new array. So we'll say System.arraycopy and we wanna copy from the stack, we wanna start from the first element, we wanna copy into the new array, and we want to copy starting at the first element and we want to copy stack.length elements. And then finally, we are going to assign a new array to the stack field, and so our backing array has been resized. So now that we've done that, we can say stack top plus plus, equals the employee. And that's the push method. So we come in, we check to see whether the stack is full, if it is, we resize it by doubling the number of elements it can hold, so we double the capacity essentially, and then once we are positive that stack top is not going to give us an array out of bounds exception, we assign the employee into top and then of course we increment top. Now, because of that, because we may have to resize the array, this operation push, the time complexity is o of n. This statement here is o of one, I mean, this, to do this operation, the number of steps doesn't depend on how many items are on the stack, but because in the worst case, we have to resize the stack, and because doing so means we have to copy all of the existing elements, the worst case for push is o of n, so the worst case for pushing onto a stack is linear time. All right, so let's go ahead and implement pop. So we'll say public Employee, because remember, when we pop something off the stack, we are gonna take the top item, pop, and we want to check whether the stack is empty now, because if the stack is empty, there's nothing to pop, so let's add an isEmpty method. I'll do that after the pop method, so I'll say public boolean isEmpty, and the stack is empty if top is equal to zero, because remember, top always holds the next available position in the stack, and so we are gonna return top equals zero, and so when top equals zero, our stack is empty. So if we want to take something off the stack, we'll first check to see if the stack is empty, so we'll say if isEmpty. Now, if it is, we could return null, but instead we're actually gonna throw an exception. We are gonna say throw new and as you can see, there's an EmptyStackException in the Java.Util class, so we're just gonna use that, and so that would tell the caller and the caller would have to handle this if you're trying to pop something off an empty stack. If the stack isn't empty, we are gonna say Employee, employee equals stack and what we are gonna do is we are gonna use the prefix operator to decrement top. And so remember, top always contains the index of the next available position in the array, and so there is nothing at top, there is nothing stored at top. The top item on the stack is actually stored at top minus one, and so what we want to do is decrement top, and use the result as the index into stack. And so let's say top is five. That means that the employee at the top of the stack is at position four, so we want to come in here and we are gonna change top to four, and then we're going to take the employee at position four, that's the employee at the top of the stack, and assign it into employee, and top is now four, and that's what we want, because we've popped the employee at position four, position four is now the next available position on the stack. So what we're going to do is we're going to set that position to null, because we have popped the employee at position top and so we now want to null that out, and finally, we return the employee. And that's our pop method. Now, we could worry about resizing the array in this method, like let's say we started with a capacity of 10 and then we resized the array to 20, let's say a push made us resize the array to 20, and then let's say eventually we resized the array to 40, and then we popped 30 items off the stack. Well, now our size 40 array only has 10 items in it, so there's a lot of wasted space. So if we wanted to be really diligent, we could do a check here and if we see there's lots of empty space, and the way we'd do the check is to compare the top value against the length of the array, and if we see that there is a tonne of empty space, we could consider resizing the array. But we don't have to. So if we don't worry about resizing the array, the pop operation will always be done in constant time, because it doesn't depend on the number of items. There's nothing in here that depends on the number of items on the stack, but if we do want to be diligent and we do want to worry about resizing the array if there's a lot of empty space, then the pop operation will become a linear operation. It'll have a time complexity of o of n. Now, resizing the array in the pop method does come with a risk because if we then push more items, we could end up having to resize the array again by making it larger, and because of that, you'll see implementations of stack that worry about resizing the array in the pop method and you'll see implementations that don't. Now, if you expect to push a tonne of items onto the stack and then you're gonna be popping items off over time, and never pushing items again, then resizing in the pop method could make sense if memory is an issue. But if you're gonna be pushing items and then popping some and then pushing more, popping some, et cetera, if you're gonna resize the array on a pop, you could run into the risk of resizing the array down and then having to resize it up again. So if memory isn't an issue, it's probably best to just leave the array at the size it is when you're popping items off. Okay, so that's push and pop. There is one more operation, stack operation we need to worry about and that's peek, and you will recall that when we peek at a stack, we access the top item but we do not pop it, and so we get the top item on the stack but that item remains on the stack. So we'll say public Employee, peek, we don't have to pass anything, and we're gonna do the same thing with the exception. If the stack is empty, if you're trying to peek at a stack that doesn't have anything yet, we're gonna throw an exception. If that's not the case, we're just going to return stack top minus one. We don't want to decrement top here. We don't want to use this operator because this actually changes the value of top, and remember, we are not changing the stack in any way, and so we want the value of the top to remain the same, so we're just gonna subtract one, and then return what's there because remember, top always points to the next available position in the stack, and so the top item is actually located at the index top minus one. Now, if we want a size method, a method that tells us how many items are on the stack, well, that's easy enough. That's just gonna be the value of top, because when there's one item on the stack, top equals one, right? Because that one item will be located at position zero, and so top will be one because it's pointing at the next available position. If there are five items on the stack, top will be five because the top item on the stack will be located at position four, and top will be five because that's the next available position, and so the size method is fairly simple. Public int size and we just return top. And finally, I'm gonna add a method for printing the stack, so that when we go back to our main method and we start pushing and popping items, we can print the stack out. So I'll say public void printStack. Now, our stack is an array, so this should be fairly straightforward. I'll say for int i equals top minus one. Remember that the top item is located at position top minus one. I is greater than or equal to zero, i minus minus, we'll say System.out.println stack i. So we are printing our stack from top to bottom. And that's it. That's it for our simple stack implementation, so let's pop over to our main method now and let's play with our stack. So I'll say ArrayStack, stack equals new ArrayStack, and I'm just gonna start out with a capacity of 10. We're only gonna push four employees, so five actually, and then I'll say stack.push, and we'll push Jane, Jones, one two three, you've seen these before, stack.push, new Employee John Doe, and four five six seven. Stack.push new Employee Mary, Smith, 22. Stack.push new Employee Mike Wilson, and three two four five, and finally let's push Bill right away, Bill End. New Employee Bill and End, 78 for an ID. And now let's print our stack. So let's run. And here's our stack and remember, we are printing from the top down, so we're gonna see these in reverse order, so we have Bill, Mike, Mary, Jane, and John. So let's peek at the top item on the stack, so I'll say System.out.println stack.peek. And this should give us Bill, because Bill's sitting at the top of the stack. So I'm gonna comment that out, so we won't see them all printed out and let's run. And we see Bill. Now, Bill is still at the top of the stack. Peek does not remove any items, so Bill is still sitting at the top of the stack and I guess we could see that if I copy this line and we print the stack again. So let's run again. And we'll see we're seeing Bill twice now. This printout is coming from the peek and then this section here is printing the stack, so we've peeked at Bill, Bill is still on the stack, and then finally let's pop some items. I'm gonna comment out that printStack and let's System.out.println a popped plus stack.pop. And then we'll call peek again. So we should see Bill printed out for being popped and then at that point, Mike should be at the top of the stack. So when we peek, we should get Mike. So let's run. Okay, so this Bill is from here, when we peek at Bill, and then we popped employee Bill End, and then when we peek, Mike is at the top of the stack because Bill is gone. Now, if you go back to our ArrayStack class. So I'll just close this down. So I said that for push, worse case is o of n, because we may have to resize the array. For pop, it's o of one if you're not worrying about resizing the array and it's o of n if you are. And for peek, it's always o of one, because peek, you never do any resizing, so a peek operation with a stack that's backed by an array is always constant time. If you know the maximum number of data items you're gonna have upfront, then you'll be able to set the appropriate capacity for the array and you won't have to worry about the array being resized, so that would mean all of your stack operations can be done in constant time, which should be fantastic. Now, of course if you don't know how large your data set is gonna be, then an array may not be the best implementation in that case, you might want to have a stack backed by a linked list. So in summary, if you don't expect the array to have to be resized frequently, then using an array to implement a stack is a good choice, but if you don't know how many items will ultimately be pushed onto the stack and so it's possible the array may have to be resized frequently, or if you're gonna have to worry about resizing the array on a pop, let's say memory is really tight for some reason, so you don't want a lot of wasted space in the backing array, then an array might not be a good choice. All right, so that's a simple stack implementation using an array to back the stack. We are going to move on and in the next video, we're going to look at the class available in the JDK for stacks. I'll see you there.