Introduction to Stacks in Java

Beginner’s guide to implementing the stack data structure in Java

Pavindu Lakshan
May 4, 2020 · 5 min read
Image for post
Image for post
Photo by Bekir Dönmez on Unsplash

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.

Image for post
Image for post
A stack of books — Photo by Jan Mellström on Unsplash

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.

  1. Push - Inserting data onto the top of the stack
  2. 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
Image for post
Image for post

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.

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 values into the 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 values from the 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.

Stack.java

Javarevisited

Medium’s largest Java publication, followed by 9200+ programmers. Follow to join our community.

Medium is an open platform where 170 million readers come to find insightful and dynamic thinking. Here, expert and undiscovered voices alike dive into the heart of any topic and bring new ideas to the surface. Learn more

Follow the writers, publications, and topics that matter to you, and you’ll see them on your homepage and in your inbox. Explore

If you have a story to tell, knowledge to share, or a perspective to offer — welcome home. It’s easy and free to post your thinking on any topic. Write on Medium

Get the Medium app

A button that says 'Download on the App Store', and if clicked it will lead you to the iOS App store
A button that says 'Get it on, Google Play', and if clicked it will lead you to the Google Play store