Introduction to Stacks in Java
Beginner’s guide to implementing the stack data structure in Java
Many of you have seen stone stacks like the one above. If you want to take a stone without breaking the art, you should take the uppermost smallest stone, and to add a stone, you are able to place it only on the top of the existing stone stack. This is true for not only stone stacks but also for the stacks that we encounter in our day-to-day life such as stacks of books and piles of plates.
The nature of stacks that we see in real life is often required to implement for different use cases in the field of software development. As a result, stacks have become one of the most used data structures used. In fact, some programming languages have even introduced built-in classes and methods for implementing a stack data structure in computer programs.
Introduction
A stack is a basic data structure that can be logically thought of as a linear structure where insertion and deletion of items take place at one end called the top of the stack. Therefore, it is also called a LIFO ( Last In First Out ) data structure. There are 2 main operations associated with a stack.
- Push - Inserting data onto the top of the stack
- Pop - Removing the topmost data item on the stack
In addition, there are some other methods that can be used with a stack.
- IsEmpty - Checking if the stack is empty
- IsFull - Checking if the stack is completely filled
- GetSize - Getting the number of data elements in the stack
Uses of Stacks
It was also stated at the beginning of this article that stacks, as a data structure, are widely used in programming. The following are some of the interesting use cases of stacks. As you can see, many real-world applications that are close to us utilize stacks for its functionality.
- In practice, many calculators employ the Shunting Yard algorithm to evaluate mathematical expressions as per the rules of BODMAS. The algorithm makes use of stacks to push and pop math operators based on precedence and position.
- Most programming languages and compilers use stacks to support method calls, express parsing, and syntax validation.
- Both the back button and the forward button in a browser are also a nice example of utilizing stacks in the real world. When the user is about to visit a new web page, the current page is pushed into the stack for the back button. The data on the top of the stack .i.e. the last visited page is popped out from the stack and loaded in the browser when the user presses the back button.
Implementing Stacks in Java
Having a fair understanding of the stack data structure, let’s now get ready to see stacks in action. You can implement a stack using other data structures such as linked lists and arrays. However, In this article, for the sake of simplicity, we use an array to demonstrate how stacks work. No waiting or procrastination, fire up your favorite IDE and start following along😊.
Note: Java collections framework already provides us with a Stack class with methods to push a value to a stack, pop a value from a stack and search a stack. However, here we are going to implement a stack from first principles so that we can better understand how stacks work.
Initializing a stack
In the above code snippet, we have initialized an empty array, called arr, to behave like a stack. In the constructor method, we take a size argument, by which we define the size i.e. the number of maximum elements allowed in the stack. Since our stack doesn’t contain any data for now, top have been set to -1.
Helping functions
Before looking at how to setup push and pop methods, let’s define some other methods which are going to help to make pushing and popping convenient and error-free.
currentSize returns how many elements are currently in the stack. Since we have initialized top to -1, when we insert a new element into the stack, the top becomes 0 as the zeroth element of the array is at the top of the stack now. Therefore, whenever we are going to find the current size of the stack, we need to add 1 to the top to get the correct size.
isEmpty and isFull methods check if the stack is empty and full respectively. Understanding it is straightforward when you got the explanation for currentSize😁.
Pushing into stack
When an integer is going to be pushed into the stack, the push method first checks if the stack is completed. if yes, the method terminates and the inserting halts. otherwise, the value is inserted into arr and the value of top is incremented by 1, both at the same time, because of ++ ( pre-increment operator ).
Popping from stack
When a value is going to be popped out, pop method first checks if the stack is empty. If the stack is not empty, then the value at the top position is returned and the value of top is also decreased by one at the same time, so that the popped value is considered as removed from the stack.
All in one
In this article, we discussed the stack data structure and how to implement one from scratch in Java. If you have any questions or found an error, please don’t hesitate to comment below.
Thank you all for reading❤️
