Stack Data Structure in Java

A stack is a data structure that follows the principle of last-in, first-out (LIFO). This means that the element that is added last to the stack is the first one to be removed. A stack can be implemented using an array or a linked list in Java.

In this blog post, we will see, In-build Stack Classes in Java, and their methods. And, how to create a stack class using an array and Linked List, and some basic operations on it. And, the end Some Important Leetcode Questions to Solve with their links and so on.

Some Important Methods in In-build Stack Class in Java:

1. push(E item): This method is used to add an element to the top of the stack.

2. pop(): This method is used to remove and return the top element from the stack.

3. peek(): This method is used to return the top element from the stack without removing it.

4. empty(): This method is used to check whether the stack is empty or not. It returns true if the stack is empty, and false otherwise.

5. search(Object o): This method is used to search for an element in the stack. It returns the distance of the element from the top of the stack if it is present, -1 otherwise.

Note: the Stack class inherits several methods from its superclass Vector.

Methods inherited from Class java.util.vector:

1. capacity(): This method is used to get the current capacity of the stack.

2. ensureCapacity(int minCapacity): This method is used to ensure that the stack has at least the specified minimum capacity.

3. get(int index): This method is used to get the element at the specified index in the stack.

4. indexOf(Object o, int index): This method is used to get the index of the first occurrence of the specified element in the stack, starting from the specified index.

5. lastIndexOf(Object o): This method is used to get the index of the last occurrence of the specified element in the stack.

6. remove(int index): This method is used to remove the element at the specified index from the stack.

7. remove(Object o): This method is used to remove the first occurrence of the specified element from the stack.

8. setSize(int newSize): This method is used to set the size of the stack to the specified value.

9. toArray(): This method is used to get an array containing all the elements in the stack, in the same order as the stack.

Other methods inherited from Parent Class [Vector]

add(),

addAll(),

removeElement(),

removeAllElements()

etc...

Oracle Doc Link

Implementation of a stack class using an array:

To create a stack class using an array, we need to declare an array of a fixed size and a variable to keep track of the top element.

Here we are going to implement the methods down below:

• push(): This method will add an element to the top of the stack if there is space available. It will also increment the top variable by one.

• pop(): This method will remove and return the top element of the stack if it is not empty. It will also decrement the top variable by one.

• peek(): This method will return the top element of the stack without removing it if it is not empty.

• isEmpty(): This method will return true if the stack is empty, i.e., if the top variable is -1.

• isFull(): This method will return true if the stack is full, i.e., if the top variable is equal to the size of the array minus one.

public class Stack {  
    // Declare an array and a top variable  
    private int[] arr;  
    private int top;  

    // Constructor to initialize the array and the top variable  
    public Stack(int size) {  
        arr = new int[size];  
        top = -1;  
    }  
    // Method to push an element to the stack  
    public void push(int x) {  
        // Check if there is space available  
        if (isFull()) {  
        System.out.println("Stack overflow");  
        } else {  
        // Increment the top and add the element  
        top++;  
        arr[top] = x;  
        }  
    }  
    // Method to pop an element from the stack  
    public int pop() {  
        // Check if the stack is empty  
        if (isEmpty()) {  
        System.out.println("Stack underflow");  
            return -1;  
        } else {  
            // Return and remove the top element  
            int x = arr[top];  
            top--;  
            return x;  
        }  
    }  
    // Method to peek at the top element of the stack  
    public int peek() {  
        // Check if the stack is empty  
        if (isEmpty()) {  
            System.out.println("Stack is empty");  
            return -1;  
        } else {  
            // Return the top element  
            return arr[top];  
        }  
    }  
    // Method to check if the stack is empty  
    public boolean isEmpty() {  
        return top == -1;  
    }  

    // Method to check if the stack is full  
    public boolean isFull() {  
        return top == arr.length - 1;  
    }
}

Using the Above Stack Class:

public class Main {  
    public static void main(String[] args) {  
        // Create a stack object with size 5  
        Stack s = new Stack(5);  

        // Push some elements to the stack  
        s.push(10);  
        s.push(20);  
        s.push(30);  
        s.push(40);  
        s.push(50);  

        // Pop some elements from the stack  
        System.out.println(s.pop()); // Prints 50  
        System.out.println(s.pop()); // Prints 40  

        // Peek at the top element of the stack  
        System.out.println(s.peek()); // Prints 30  

        // Check if the stack is empty or full  
        System.out.println(s.isEmpty()); // Prints false  
        System.out.println(s.isFull()); // Prints false  

        // Push another element to the stack  
        s.push(60); // Prints Stack overflow  
    }  
}

We can also implement a stack using a linked list, which will allow us to have a dynamic size and avoid overflow or underflow errors.

Implementation of a stack class using a Linked List:

public class Stack {
    private Node top;
    private int size;

    private class Node {
        int data;
        Node next;
    }

    public Stack() {
        top = null;
        size = 0;
    }

    public boolean isEmpty() {
        return (top == null);
    }

    public void push(int data) {
        Node oldTop = top;
        top = new Node();
        top.data = data;
        top.next = oldTop;
        size++;
    }

    public int pop() {
        if (isEmpty()) throw new RuntimeException("Stack underflow");
        int data = top.data;
        top = top.next;
        size--;
        return data;
    }

    public int peek() {
        if (isEmpty()) throw new RuntimeException("Stack underflow");
        return top.data;
    }

    public int size() {
        return size;
    }
}

In-build Stack Data Structure in java:

import java.util.Stack;  
public class Main {  
    public static void main(String[] args) {  
        // Creating a stack  
        Stack<Integer> stack = new Stack<>(); // This creates an empty stack of integers.  

        // Push Elements into the Stack:  
        stack.push(1);  
        stack.push(2);  
        stack.push(3); // Peek Element  

        // Getting the Top Element of the Stack:  
        int topElement = stack.peek();  
        System.out.println(topElement); // 3  

        // Pop() method will remove the top element from the Stack:  
        int peekElement = stack.pop();  
        System.out.println(peekElement); // 3  
        System.out.println(stack.peek()); // Now the peek element will change to 2.  
    }  
}

Real-life Uses of Stack Data Structure:

A stack is a useful data structure for many applications, such as,

1. Undo/Redo functionality: Many software applications, such as text editors and image editors, use a stack to implement undo/redo functionality. The actions performed by the user are stored in a stack, and when the user wants to undo an action, the last action is popped from the stack and reversed.

2. Back/Forward buttons in web browsers: Web browsers use a stack to implement the back/forward buttons. When a user visits a new page, the current page is pushed onto a stack. When the user clicks the back button, the last page is popped from the stack and displayed.

3. Call Stack: The call stack is a stack data structure used by programming languages to keep track of function calls. When a function is called, its return address and local variables are pushed onto the call stack. When the function returns, its return address and local variables are popped from the call stack.

4. Expression Evaluation: Stacks can be used to evaluate mathematical expressions, such as infix and postfix expressions.

Some Important Algorithms that use Stack DS:

1. Depth-First Search (DFS): This is a graph traversal algorithm that uses a stack to keep track of the vertices to be visited.

2. Infix to Postfix Conversion: This algorithm uses a stack to convert an infix expression (e.g. A + B * C) to a postfix expression (e.g. ABC*+).

3. Postfix Evaluation: This algorithm uses a stack to evaluate a postfix expression (e.g. ABC*+).

4. Balanced Parentheses: This algorithm uses a stack to check if an expression has balanced parentheses (e.g. ((A + B) * C)).

5. Tower of Hanoi: This is a classic puzzle that can be solved using a stack data structure.

Some Important Stack Questions to Clear the fundamentals:

1. Valid Parentheses: This problem asks you to determine if a given string containing just the characters ‘(’, ‘)’, ‘{’, ‘}’, ‘[’ and ‘]’ is valid.

2. Min Stack: This problem asks you to design a stack that supports push, pop, top, and retrieving the minimum element in constant time

3. Evaluate Reverse Polish Notation: This problem asks you to evaluate the value of an arithmetic expression in Reverse Polish Notation

4. Implement Stack using Queues: This problem asks you to implement a stack using two queues

5. Implement Queue using Stacks: This problem asks you to implement a queue using two stacks

   Medium Article Leetcode

Important Leetcode Questions on Monotonic Stack:

1. 503: Next Greater Element II

2. 739: Daily Temperatures

3. 1762: Buildings with an ocean view

4. 456: Find 132 Pattern

5. 42: Trapping rain water

6. 84: Largest rectangle in histogram

7. 1944: Number of visible people in the queue

   Leetcode Article by darkalarm