Introduction to Stack Data Structure in Java

Published by Vignesh M on

Stack is an abstract data type. Stack can be implemented using Linked List or Array. It follows LIFO principle (Last In First Out) and supports push(), pop() and peek() operations.

Stack operations

For this explanation, let’s consider that we implement the stack using LinkedList.

push()

In stack, the push operation will always insert a new item as the top node of the LinkedList. The complexity is O(1) and it is very fast.

pop()

The pop operation always removes the item from the top most node of the LinkedList. This operation is also O(1) complexity.

peek()

The peek operation is same as pop, except that it doesn’t removes the item. The peek returns the value of the top most node which the stack is currently pointing to and the complexity is O(1).

Stack Applications

1. Stack is used most importantly in Call Stack

  • Stack is used in many programming languages to store information about methods, functions of a computer program.
  • The local variables of a function are stored in Stack.
  • After the function call returns, the local variables are freed up from the stack memory.
  • Stack memory is part of RAM and is limited in size. It is very fast for accessing the value.

2. In Graph algorithms, for example in depth-first search

Stack implementation using LinkedList

First let’s define the Stack Node which have two attributes – data and a reference to next node.

Then, the implementation of Stack to support push, pop, peek, size and isEmpty operations. All the operations are very fast and is O(1) complexity.

Finally, test the Stack implementation.

Summary
  • Stack is an abstract data type and can be implemented using LinkedList or Array in Java.
  • It is used in many programming languages to keep information of the active subroutines, function and method calls.
  • There is always a trade-off between memory and run-time when choosing a data structure for Stack implementation. So, use LinkedList when memory is not a concern. Otherwise all the operations are very fast.
  • Use Array to implement Stack when memory is of important concern. But the operations are not so efficient because we have to resize the Array internally.

 

 


    Vignesh M

    Java developer , AWS Certified Solutions Architect Associate and Cloud technology enthusiast. Currently working for Hexaware technologies. He believes that knowledge increases by sharing not by saving.

    Leave a Reply

    Your email address will not be published. Required fields are marked *

    This site uses Akismet to reduce spam. Learn how your comment data is processed.