From the course: Nail Your Java Interview

Leveraging stacks as a data structure - Java Tutorial

From the course: Nail Your Java Interview

Start my 1-month free trial

Leveraging stacks as a data structure

“

- A stack is an ordered list of objects that are inserted and removed following a last in first out policy, a LIFO policy. The first item inserted into the stack will be the last item removed from the stack. And the last item inserted onto the stack will be the first item removed from the stack. For stacks we insert items using a push method, essentially pushing items on the top of the stack. We delete items using a pop method, which pops items off the top of the stack. If you think of a deck of cards, if we put one card down then card two down then card three down card three is last inserted or pushed on top of the stack. Naturally the last card inserted will be drawn first since it's on top. The third card will be removed from the deck first. Since card one was pushed on top of the stack first, it will be removed last because it's at the bottom of the stack. Here, removing it the stack is empty once again. Let's take a look at how something like this might work in Java. First, we import Java.util.stack so we can use Java's built in implementation of the stack data structure. Then we create a stack using the stack constructor. We also create three strings that represent cards one, two, and three. This is a loose interpretation of a card and it would certainly be better if we had a card class to represent each card with their value and type. However, for this example, let's keep it simple and represent each card with a string. We can insert these cards onto the deck using the push method. Stacks can also be implemented with the arrays or linked lists, but the main difference is the rules of how we insert and remove data are much more strict. We can only push and pop data from the top of the stack or the back of a list rather than both the bottom and the top. Looking at some of the other stack methods, we can use the peak method to see what's on top of the stack without removing anything. We can also find out the size of a stack using the size method. To remove items from a stack we use the pop method, however, you have to be careful. If you try to pop a stack that is empty, you will get errors. To avoid these errors, we should make sure the stack actually has items. To do this we can use the is Empty method on the stack and check if the stack is empty before removing the item. We'll do this with an if statement. We'll say, if the deck of cards is not empty, then we'll remove an item. Once we've removed it, we'll print it out to the console. If we want to iterate through the stack, removing each item, we can change our if to a while loop and the stack would be cleared. We'd remove each item and tell the stack was empty. Let's run our program and see how this stack handles our data. First, we print out the deck of cards we see our Jack of diamonds, our eight of hearts or three of clubs. The three of clubs is on the top of the stack and the size of our stack is three. When we remove items we've removed from the top so first we remove the three of clubs then the eight of hearts, and last the Jack of diamonds. This is how we use stacks to work with our data. But why would you use a stack in your program? Stacks are great when you need to reverse things. For example, let's say you push a string onto a stack, one character at a time, and then you make a string from the members popped off the stack. The resulting string is reversed. Stacks are also good for keeping track of state and the runtime stack is a great example of this. The runtime stack keeps track of what variables you currently have access to and what sub-routine or function you're in. Whenever you get an error, an error message coming from the runtime stack usually appears. And you can retrace your steps from where the error occurred.

Contents