Stack

Stack in Java

A stack is a linear data structure that follows the Last In First Out (LIFO) principle, where the last element added to the stack is the first one to be removed. In Java, the Stack class is part of the Java Collections Framework and provides the functionality to work with a stack.

Key Operations

The primary operations performed on a stack are:

• Push: Adds an element to the top of the stack.
• Pop: Removes and returns the element at the top of the stack.
• Peek: Returns the element at the top of the stack without removing it.
• Empty: Checks if the stack is empty.
• Search: Searches for an element and returns its distance from the top of the stack.

Using the Stack Class in Java

The Stack class is part of the java.util package. Here’s how to use it:

Importing the Stack Class

To use the Stack class, you need to import it from the java.util package:

import java.util.Stack;

Creating a Stack

You can create a stack by instantiating the Stack class:

Stack<Integer> stack = new Stack<>();

Basic Stack Operations

Here are examples of the basic stack operations:

• Push

  stack.push(10);
  stack.push(20);
  stack.push(30);
  // Stack now contains [10, 20, 30]

• Pop

  int poppedElement = stack.pop();
  System.out.println("Popped element: " + poppedElement);
  // Output: Popped element: 30
  // Stack now contains [10, 20]

• Peek

  int topElement = stack.peek();
  System.out.println("Top element: " + topElement);
  // Output: Top element: 20

• Empty

  boolean isEmpty = stack.empty();
  System.out.println("Is stack empty? " + isEmpty);
  // Output: Is stack empty? false

• Search

  int position = stack.search(10);
  System.out.println("Position of 10: " + position);
  // Output: Position of 10: 2

Example Program

Here is a complete example demonstrating the use of the Stack class in Java:

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // Create a stack
        Stack<Integer> stack = new Stack<>();

        // Push elements onto the stack
        stack.push(10);
        stack.push(20);
        stack.push(30);

        // Display the stack
        System.out.println("Stack: " + stack);

        // Pop an element from the stack
        int poppedElement = stack.pop();
        System.out.println("Popped element: " + poppedElement);

        // Display the stack after pop
        System.out.println("Stack after pop: " + stack);

        // Peek at the top element
        int topElement = stack.peek();
        System.out.println("Top element: " + topElement);

        // Check if the stack is empty
        boolean isEmpty = stack.empty();
        System.out.println("Is stack empty? " + isEmpty);

        // Search for an element in the stack
        int position = stack.search(10);
        System.out.println("Position of 10: " + position);
    }
}

When to Use a Stack

Stacks are useful in various scenarios, including:

• Expression Evaluation: Used in evaluating expressions (e.g., postfix, prefix).
• Syntax Parsing: Used in parsing expressions, syntax trees, and programming languages.
• Backtracking: Used in algorithms that involve backtracking, such as solving puzzles or navigating mazes.
• Function Call Management: Used by compilers to keep track of function calls and return addresses.

Limitations of Stack

While the Stack class in Java is easy to use, it has some limitations:

• Synchronized Methods: The methods of the Stack class are synchronized, which can lead to overhead in a multi-threaded environment.
• Legacy Collection: The Stack class is part of the original Java 1.0 collections framework. For newer implementations, consider using Deque interface and its implementations, such as ArrayDeque.

By understanding and effectively using stacks, you can solve various computational problems efficiently and manage data in a LIFO manner.