Java Program to Implement stack data structure

Introduction

A stack is a fundamental data structure in computer science, following a Last In First Out (LIFO) approach where the last element added is the first one to be removed. This structure is akin to a stack of plates where only the top plate is accessible for removal. Stacks are vital for applications like expression evaluation, backtracking algorithms, and maintaining function calls.

In this article, you will learn how to implement a stack data structure in Java through hands-on examples. Explore the creation, manipulation, and utilization of stacks for storing data, and observe its LIFO characteristic in practical scenarios.

Java Stack Implementation Using Array

Setting Up the Stack Class

1. Define a class named Stack.

2. Declare an array to hold the stack's data and an integer to track the top of the stack.

   java Copy

   public class Stack {
       private int arr[];
       private int top;
       private int capacity;
   
       public Stack(int size) {
           arr = new int[size];
           capacity = size;
           top = -1;
       }
   }
   

   This code snippet creates a stack where arr is the storage array, capacity stores the maximum stack size, and top indicates the current top of the stack, initialized to -1 representing an empty stack.

Adding Elements: Push Operation

1. Implement the push method to add elements to the stack.

2. Check if the stack is full before adding a new element to prevent overflow.

   java Copy

   public void push(int item) {
       if (isFull()) {
           System.out.println("Stack OverFlow");
           System.exit(1);
       }
       arr[++top] = item;
   }
   
   public boolean isFull() {
       return top == capacity - 1;
   }
   

   The push method increases the top and inserts the new item. Additionally, the isFull method prevents insertion into a full stack, ensuring data integrity.

Removing Elements: Pop Operation

1. Implement the pop method to remove the top element from the stack.

2. Ensure the stack is not empty to avoid underflow.

   java Copy

   public int pop() {
       if (isEmpty()) {
           System.out.println("Stack UnderFlow");
           System.exit(1);
       }
       return arr[top--];
   }
   
   public boolean isEmpty() {
       return top == -1;
   }
   

   The pop method decrements top and returns the removed element. The isEmpty check ensures there is an element to remove, thus preventing underflow.

Observing the Top Element: Peek Operation

1. Implement the peek method to get the top element without removing it.

   java Copy

   public int peek() {
       if (!isEmpty()) {
           return arr[top];
       }
       System.out.println("Stack is empty");
       System.exit(1);
       return -1;
   }
   

   This method accesses the top element if available and ensures the function does not try to peek into an empty stack.

Implementing Stack Using LinkedList

Set Up the LinkedList Node Class

1. Define a Node class for linked-list implementation.

   java Copy

   private static class Node {
       int value;
       Node next;
   
       Node(int value) {
           this.value = value;
       }
   }
   

   Each node holds a value and a reference to the next node in the list.

Operations for Stack Using LinkedList

1. Manage the linked list's head to act as the stack's top.

2. Modify the operations to adapt to the LinkedList approach.

   java Copy

   public class Stack {
       private Node top;
   
       public void push(int item) {
           Node node = new Node(item);
           node.next = top;
           top = node;
       }
   
       public int pop() {
           if (top == null) {
               System.out.println("Stack UnderFlow");
               System.exit(1);
           }
           int value = top.value;
           top = top.next;
           return value;
       }
   
       public int peek() {
           if (top != null) {
               return top.value;
           }
           System.out.println("Stack is empty");
           System.exit(1);
           return -1;
       }
   
       public boolean isEmpty() {
           return top == null;
       }
   }
   

   Unlike an array, Node objects dynamically grow the stack without a fixed limit. Operations like push and pop adjust top to show the current head of the stack.

Conclusion

Successfully implementing a stack in Java enhances understanding of this crucial data structure. Both the array and linked list methods provide robust means to manage data following LIFO principles. Experiment with both implementations to see how they differ in terms of performance and usage in different scenarios. By mastering these stack implementations, tailor efficient solutions for problems requiring backtrack or last-in-first-out operations.