Stack Data Structure in Java, easy in 5 minutes

The post shows you all about the stack data structure in Java. The stack is a classic data structure in programming. It’s really powerful and is implemented widely in many cases. Let’s learn and grow together.

Stack Data Structure in Java

Stack Data Structure Specification

In programming terms, putting an item on top of the stack which is called “push” and removing an item is called “pop”. A stack is an object or an abstract data structure(ADT) that allows the following operations:

  • Push: Add an element to the top of a stack
  • Pop: Remove an element from the top of a stack
  • IsEmpty: Check if a stack is empty
  • IsFull: Check if a stack is full
  • Peek: Get the value of the top element without removing it

It follows the Last In First Out(LIFO) principle that means the element stored last then it was removed first, see the below image.

Stack data structure, Last In First Out(LIFO),
A Stack data structure, Last In First Out(LIFO)

How a stack data structure works

Mainly the following three basic operations are performed in the stack:

  • A pointer called TOP is used to keep track of the top element in the stack. When initializing the stack, we set its value to -1 so that we can check if the stack is empty by comparing TOP == -1.
  • On pushing an element, we increase the value of TOP and place the new element in the position pointed to by TOP. Before pushing again, we check if stack is already full
  • On popping an element, we return the element pointed to by TOP and reduce its value. Before popping again, we check if stack is already empty

Stack Operations, How stack data structure works

Time Complexities of operations on stack

push(), pop(), isEmpty() and peek() all take O(1) time. We do not run any loop in any of these operations.

Applications of stack

To reverse a word: Put all the letters in a stack and pop them out. Because of LIFO order of stack, you will get the letters in reverse order.
In compilers: Compilers use a stack to calculate the value of expressions like 1+3/5*(6-9) by converting the expression to prefix or postfix form.
Redo-undo: features at many places like editors, photoshop. Forward and backward feature in web browsers.
In Graph Algorithms: like Topological Sorting and Strongly Connected Components

Implementing Stack Data Structure in Java

a) Implementing Stack using Arrays.

Here is the output of the stack program.

Stack Data Structure in Java, Implementing Stack using Arrays

Pros: Easy to implement. Memory is saved as pointers are not involved.
Cons: It is not dynamic. It doesn’t grow and shrink depending on needs at runtime.

b) Implementing Stack using LinkedList.

Here is the output of the stack program.

Stack Data Structure in Java, Implementing Stack using LinkedList

Pros: The linked list implementation of a stack can grow and shrink according to the needs at runtime.
Cons: Requires extra memory due to involvement of pointers.

That’s all about the Stack data structure in Java.

References

Stack data structure in Java
Data Structures and Algorithms Tutorial in Java

Please share it if you found this useful
Hide Buttons