Java Stack

Discover how Stack implements Last In First Out (LIFO) principle - like a stack of plates where you always take from the top!

What is Stack?

Stack is a Last In First Out (LIFO) data structure in Java from the java.util package. Imagine a stack of plates in your kitchen - you always add new plates on top and remove plates from the top. The last plate you put in is the first one you take out!

Stack extends the Vector class and provides special methods for stack operations, making it perfect for scenarios like undo functionality, expression evaluation, and backtracking algorithms.

  • LIFO Principle: Last element added is the first one removed
  • Push Operation: Add elements to the top of the stack
  • Pop Operation: Remove and return the top element
  • Peek Operation: View the top element without removing it
  • Thread-Safe: Synchronized methods make it safe for multi-threading

💡 Real-World Analogy: Think of Stack like a stack of books, browser history (back button), or the "Undo" feature in text editors - all follow LIFO principle!

Creating and Using Stack

Here's how to create a Stack and perform basic operations:

Example: Stack Basic Operations

import java.util.Stack;

public class StackExample {
    public static void main(String[] args) {
        // Creating a Stack
        Stack books = new Stack<>();
        
        // Check if stack is empty
        System.out.println("Is stack empty? " + books.isEmpty());
        
        // Pushing elements (adding to top)
        books.push("Harry Potter");
        books.push("Lord of the Rings");
        books.push("The Hobbit");
        books.push("1984");
        
        System.out.println("Stack: " + books);
        
        // Peek - view top element without removing
        System.out.println("Top book: " + books.peek());
        System.out.println("Stack after peek: " + books);
        
        // Pop - remove and return top element
        String removedBook = books.pop();
        System.out.println("Removed: " + removedBook);
        System.out.println("Stack after pop: " + books);
        
        // Search - find position from top (1-based index)
        int position = books.search("Harry Potter");
        System.out.println("Position of 'Harry Potter': " + position);
        
        // Size of stack
        System.out.println("Stack size: " + books.size());
    }
}
Output: 
Is stack empty? true
Stack: [Harry Potter, Lord of the Rings, The Hobbit, 1984]
Top book: 1984
Stack after peek: [Harry Potter, Lord of the Rings, The Hobbit, 1984]
Removed: 1984
Stack after pop: [Harry Potter, Lord of the Rings, The Hobbit]
Position of 'Harry Potter': 3
Stack size: 3

Explanation:

  • push(element) - Adds element to the top of the stack
  • pop() - Removes and returns the top element (throws exception if empty)
  • peek() - Returns the top element without removing it
  • isEmpty() - Checks if the stack has any elements
  • search(element) - Returns 1-based position from top (returns -1 if not found)
  • size() - Returns the number of elements in the stack

Stack Methods Overview

1. Adding Elements

Push elements onto the top of the stack.

Methods: push(element) - Adds element and returns it

2. Removing Elements

Remove the top element from the stack.

Methods: pop() - Removes and returns top element, throws EmptyStackException if stack is empty

3. Viewing Elements

Look at the top element without removing it.

Methods: peek() - Returns top element without removal, throws EmptyStackException if empty

4. Utility Operations

Check stack status and search for elements.

Methods: empty(), isEmpty(), search(element), size()

Practical Example: Undo Functionality

Let's implement a simple text editor with undo feature using Stack:

Example: Text Editor Undo Feature

import java.util.Stack;

public class TextEditor {
    private Stack history;
    private String currentText;
    
    public TextEditor() {
        history = new Stack<>();
        currentText = "";
    }
    
    public void write(String text) {
        // Save current state before making changes
        history.push(currentText);
        currentText += text;
        System.out.println("Current text: " + currentText);
    }
    
    public void undo() {
        if (history.isEmpty()) {
            System.out.println("Nothing to undo!");
            return;
        }
        currentText = history.pop();
        System.out.println("After undo: " + currentText);
    }
    
    public static void main(String[] args) {
        TextEditor editor = new TextEditor();
        
        System.out.println("=== Text Editor Demo ===\n");
        
        editor.write("Hello");
        editor.write(" World");
        editor.write("!");
        
        System.out.println("\nPerforming undo operations...\n");
        
        editor.undo();  // Remove "!"
        editor.undo();  // Remove " World"
        editor.undo();  // Remove "Hello"
        editor.undo();  // Nothing to undo
    }
}
Output: 
=== Text Editor Demo ===

Current text: Hello
Current text: Hello World
Current text: Hello World!

Performing undo operations...

After undo: Hello World
After undo: Hello
After undo: 
Nothing to undo!

Explanation:

  • Each text operation saves the previous state to the stack
  • Undo pops the previous state from the stack and restores it
  • Stack naturally maintains the history in LIFO order
  • Perfect for implementing undo/redo functionality in applications

Checking Balanced Parentheses

A classic Stack application - checking if parentheses in an expression are balanced:

Example: Balanced Parentheses Checker

import java.util.Stack;

public class ParenthesesChecker {
    
    public static boolean isBalanced(String expression) {
        Stack stack = new Stack<>();
        
        for (char ch : expression.toCharArray()) {
            // Push opening brackets
            if (ch == '(' || ch == '{' || ch == '[') {
                stack.push(ch);
            }
            // Check closing brackets
            else if (ch == ')' || ch == '}' || ch == ']') {
                if (stack.isEmpty()) {
                    return false;
                }
                
                char top = stack.pop();
                
                if ((ch == ')' && top != '(') ||
                    (ch == '}' && top != '{') ||
                    (ch == ']' && top != '[')) {
                    return false;
                }
            }
        }
        
        return stack.isEmpty();
    }
    
    public static void main(String[] args) {
        String[] expressions = {
            "{[()]}",
            "{[(])}",
            "((()))",
            "((())",
            "{[}]"
        };
        
        System.out.println("Checking parentheses balance:\n");
        
        for (String exp : expressions) {
            boolean balanced = isBalanced(exp);
            System.out.println(exp + " → " + 
                (balanced ? "✓ Balanced" : "✗ Not Balanced"));
        }
    }
}
Output: 
Checking parentheses balance:

{[()]} → ✓ Balanced
{[(])} → ✗ Not Balanced
((()) → ✓ Balanced
((()) → ✗ Not Balanced
{[}] → ✗ Not Balanced

Explanation:

  • Push opening brackets onto the stack
  • When closing bracket found, check if it matches the top of stack
  • If stack is empty at the end, all brackets were properly matched
  • Used in compilers and code editors to validate syntax

Stack vs Other Collections

Understanding when to use Stack compared to other collections:

Comparison Table

Feature              Stack               ArrayList           LinkedList
───────────────────────────────────────────────────────────────────────────
Access Pattern       LIFO (Last In First Out)  Random access         Sequential
Primary Use          Backtracking, Undo        General list          Queue/Deque
Add/Remove           Top only                  Any position          Any position
Performance          O(1) push/pop             O(1) at end           O(1) at ends
Thread-Safe          Yes (synchronized)        No                    No
Typical Methods      push(), pop(), peek()     add(), get()          addFirst(), addLast()

🎯 When to Use Stack: Use Stack when you need LIFO behavior: undo/redo functionality, expression evaluation, backtracking algorithms, browser history, function call tracking (recursion).