For beginners, using ArrayList
A stack is one of the most simplest data structure to understand. If you had data structures in your academia, you already know what it means. It?s a simple Last In First Out (LIFO) queue. What that means is the last element to enter the stack will be first element to go out of the stack. Let?s try to understand the concept first with a few illustrations.
The concept
Suppose we have an empty container which looks like the container shown in the image below:
Empty stack
That?s pretty simple to understand. Now suppose again that we ?push? a string with value ?string1? to this empty stack. The stack now looks like this:
Stack with one element
That?s pretty simple to understand again. The value that we pushed into the stack went and settled down at the bottom of the stack. Now let?s push two more strings with values ?string2? and ?string3? into the stack. After this, the stack looks like the illustration below.
Stack with three elements
What happens if we pop an element from the stack? Well, the element at the top of the stack is removed from the stack and is returned. So after we pop an element from the imaginary stack, our stack looks like this:
Stack with two elements
What is LIFO?
We now need to understand which element came in first to the stack, and which will go out first, as this is a LIFO queue. Imagine the empty stack as a table, and the string values that we were pushing in as a bunch of plates. We started stacking these plates one on top of another. So the first plate we placed on the table is at the absolute bottom of the stack, and the last plate we placed is at the top of the stack. And when you want a plate to serve that awesome sandwich you made to a friend, you are going to take the plate at the top of the stack and not pull the plate from the bottom of the stack. This is what Last In First Out means. The last plate to come into the stack will be first plate to get out of the stack. I?ve tried to illustrate this concept with the image below.
Last In First Out (LIFO)
The process of adding a plate to the stack is called ?pushing? and taking a plate out of the stack is called ?popping? from the stack. So you push an element into the stack, and pop an element from the stack. Now that we know what a stack is and how it works, let?s see some code in Java to understand how we can implement this concept.
The Code
To keep this simple, I?m using an ArrayList in the stack implementation class, which remains private to the class. But when you?re writing a production ready code, you?d want to implement the Collection<E> interface and override all the methods there to provide all the functionality of a stack. Another, and as some would argue ? better, way of implementing a stack is by using a custom implemetation of a LinkedList class. Let me know if you?d want me to write a POC for that as well. But using an ArrayList internally is good enough to understand the concept.
To begin with, we need to create a stack implementation class which lets us push elements to it, pop elements from it, and stores all the elements that we push into it. I?m calling this class StackImpl, because why not? Since we?re writing this code in Java, we need to take care of the type of elements that we?re going to store in it. If we create a stack of strings, and in the future we want to store some integer values in a stack, we?ll have to write another stack implementation. That?s a lot of work. So avoid this duplication of code, we?ll make our stack implementation decide what type of data to store at runtime. This can be easily achieved by using Java?s generic class called T. If we use this in our implementation, we can use this stack class with almost any type of data we want to stack. We can declare our class with this generic class like this:
class StackImpl<T> {}
As I already mentioned, we?ll use an ArrayList internally of type T to maintain our data items. For a production ready code, I suggest you implement the Collection<E> interface or write it using a custom LinkedList implementation. But for now, let?s declare that ArrayList:
// Creating a private array list of the generic T class.private List<T> list = new ArrayList<T>();
Now we need a way to push items to our stack. Because we have the ArrayList to store our items, internally, we?re just adding items to this list. So our ?push? method looks like this:
void push(T value) { list.add(value);}
That was easy. We don?t have to take care of a lot of firefighting here because we?re using an ArrayList internally. Anyway, next, we need a method to pop items from the list. For that, we?ll write the following pop() method:
T pop() { return this.list.get(this.list.size() ? 1);}
But wait! Doing this will definitely return the last element of the stack, but it will not remove the element from the stack. So the next time we pop another item, we?ll actually get the same item. This will keep happening till infinity. So whenever we pop an item from the stack, we have to also remove that item from the ArrayList. So let?s change our pop() method to handle this:
T pop() { // Getting the last value from the list. T value = this.list.get(this.list.size() – 1); // Removing the last value from the list, // thereby popping the last value. this.list.remove(this.list.size() – 1); return value;}
Nice, that should do it. But wait, again! What if there?s nothing in the stack and we?re trying to pop something from it? Well, we?ve got to handle that as well. There are many ways in which you can handle this, depending on the context of the project. For this example, we?ll just throw an exception. But to do that, we first need to create an exception class. That?s pretty simple though, just create a new class, extend the Exception class, and add a constructor. I?m calling this the StackEmptyException class, because again, why not?
public class StackEmptyException extends Exception { public StackEmptyException(String message) { super(message); }}
We now have to change our pop() method again to throw this exception. So let?s do that now:
T pop() throws StackEmptyException { // Throwing an exception if the list is empty. if (this.list.isEmpty()) { throw new StackEmptyException(“The stack is empty. Push a value before popping it.”); } // Getting the last value from the list. T value = this.list.get(this.list.size() – 1); // Removing the last value from the list, thereby popping the last value. this.list.remove(this.list.size() – 1); return value;}
That?s more like it. And just for the fun of it, we?ll add a method which returns the size of our stack, which indicates the number of items we have in the stack. This is a pretty straight forward method as well:
public long size() { return this.list.size();}
And just for the fun of it again, we?ll write another method which will return all the elements in our stack as a list and empty the stack completely. This can come in handy when we want to use the same stack for some intermediate results in the middle of a processing but want to restore the stack with our actual values after the intermediate processing is done. We?ll call this method the ?getStackAndEmpty()? method:
List<T> getStackAndEmpty() { List<T> stack = new ArrayList<T>(this.list); this.list.removeAll(stack); return stack;}
And if we want to flush the stack, lose all the values in the stack and reinstantiate the stack, we can have a ?flush()? method as well:
void flush() { this.list = new ArrayList<>();}
This is a pretty simple method too, we?re just reassigning a new ArrayList to our private list variable. We?re now done with our custom stack implementation. The complete implementation of this class is like this:
class StackImpl<T> { // Creating a private array list of the generic T class. private List<T> list = new ArrayList<T>(); public long size() { return this.list.size(); } void push(T value) { list.add(value); } T pop() throws StackEmptyException { // Throwing an exception if the list is empty. if (this.list.isEmpty()) { throw new StackEmptyException(“The stack is empty. Push a value before popping it.”); } // Getting the last value from the list. T value = this.list.get(this.list.size() – 1); // Removing the last value from the list, thereby popping the last value. this.list.remove(this.list.size() – 1); return value; } List<T> getStackAndEmpty() { List<T> stack = new ArrayList<T>(this.list); this.list.removeAll(stack); return stack; } void flush() { this.list = new ArrayList<>(); }}
Next, we need to see this stack in action. For this, let?s create a stack of strings:
StackImpl<String> stack = new StackImpl<String>();
We?ll now push a couple of elements to the stack:
stack.push(“First”);stack.push(“Second”);
So we should now have two elements in the stack. We can use the pop() method to pop an item from the stack and check the value to see if we?re indeed following LIFO in our implementation:
String value = stack.pop();System.out.println(“Popped value: ” + value);
We should get the following output for this:
Popped value: Second
There you go, we popped the last item that went into the array. We can have a few more tests like this:
StackImpl<String> stack = new StackImpl<String>();stack.push(“First”);stack.push(“Second”);String value = stack.pop();System.out.println(“Popped value: ” + value);stack.push(“Third”);List<String> completeStack = stack.getStackAndEmpty();System.out.println(“Complete stack: ” + completeStack);stack.push(“First”);stack.push(“Second”);long stackSize = stack.size();System.out.println(“Stack size before flush: ” + stackSize);stack.flush();stackSize = stack.size();System.out.println(“Stack size after flush: ” + stackSize);String lastValue = stack.pop();
We can use the same StackImpl class to have an integer stack. And the code is pretty similar to the string stack:
StackImpl<Integer> stack = new StackImpl<Integer>();stack.push(100);stack.push(200);Integer value = stack.pop();System.out.println(“Popped value: ” + value);stack.push(300);List<Integer> completeStack = stack.getStackAndEmpty();System.out.println(“Complete stack: ” + completeStack);stack.push(100);stack.push(200);long stackSize = stack.size();System.out.println(“Stack size before flush: ” + stackSize);stack.flush();stackSize = stack.size();System.out.println(“Stack size after flush: ” + stackSize);Integer lastValue = stack.pop();
I?ve written this part of the code in my main class. The complete class looks like this:
public class App { public static void main(String args) { stringStackExample(); integerStackExample(); } private static void integerStackExample() { try { StackImpl<Integer> stack = new StackImpl<Integer>(); stack.push(100); stack.push(200); Integer value = stack.pop(); System.out.println(“Popped value: ” + value); stack.push(300); List<Integer> completeStack = stack.getStackAndEmpty(); System.out.println(“Complete stack: ” + completeStack); stack.push(100); stack.push(200); long stackSize = stack.size(); System.out.println(“Stack size before flush: ” + stackSize); stack.flush(); stackSize = stack.size(); System.out.println(“Stack size after flush: ” + stackSize); Integer lastValue = stack.pop(); } catch (StackEmptyException e) { System.out.println(“Error: ” + e.getMessage()); } } private static void stringStackExample() { try { StackImpl<String> stack = new StackImpl<String>(); stack.push(“First”); stack.push(“Second”); String value = stack.pop(); System.out.println(“Popped value: ” + value); stack.push(“Third”); List<String> completeStack = stack.getStackAndEmpty(); System.out.println(“Complete stack: ” + completeStack); stack.push(“First”); stack.push(“Second”); long stackSize = stack.size(); System.out.println(“Stack size before flush: ” + stackSize); stack.flush(); stackSize = stack.size(); System.out.println(“Stack size after flush: ” + stackSize); String lastValue = stack.pop(); } catch (StackEmptyException e) { System.out.println(“Error: ” + e.getMessage()); } }}
This should be pretty easy to understand, but I could be wrong. Please let me know if the example or the explanation wasn?t clear. I?ll try to explain it better. And again, this is by noway a production ready code. This is written only to understand the concept.
And if you want to straight away jump to the project, you can clone the Maven project POC from my Github repo.
Follow me on Twitter for more Data Science, Machine Learning, and general tech updates. Also, you can follow my personal blog.
