Java Data Structures and Algorithms for Beginners

Stack Data Structure

Definition and Concepts

A stack is a linear data structure that operates on the Last In, First Out (LIFO) principle. This means that the last element added to the stack is the first one removed. You can visualize a stack as a stack of plates, where you add a plate to the top and remove the topmost plate first. The primary operations of a stack include push, which adds an element to the top, and pop, which removes the top element. Additional operations include peek, which views the top element without removing it, and isEmpty, which checks if the stack is empty. Stacks are simple to implement and are highly efficient for problems requiring reversal or backtracking.

Why Use It?

A stack is useful when you need to process data in a Last In, First Out order. It provides an efficient way to manage data where the most recently added element is the first to be accessed or removed. Stacks are memory-efficient because they restrict operations to one end, known as the top, which simplifies data management and reduces operational complexity.

Where to Use? (Real-Life Examples)

• Undo Functionality in Software: Text editors and graphic design tools use stacks to store user actions, such as typing or drawing, allowing the most recent action to be undone.
• Browser History Navigation: Web browsers employ stacks to manage back and forward navigation, where the most recently visited page is removed when you click the "back" button.
• Function Call Management: Programming languages utilize stacks to handle function calls, storing return addresses and local variables for each function.
• Expression Evaluation: Stacks are used to evaluate mathematical expressions, such as 3 + 4 * 2, by managing operator precedence and parentheses.

Explain Operations

• Push: This operation adds an element to the top of the stack. It has a time complexity of O(1).
• Pop: This operation removes and returns the top element from the stack. If the stack is empty, it may throw an exception or return null. It has a time complexity of O(1).
• Peek: This operation returns the top element without removing it. It has a time complexity of O(1).
• isEmpty: This operation checks whether the stack is empty. It has a time complexity of O(1).
• Size: This operation returns the number of elements currently in the stack. It has a time complexity of O(1).

Java Implementation

The following Java code implements a stack using an array.

public class Stack {
    private int maxSize; // Represents the maximum size of the stack
    private int[] stackArray; // Array to store the stack elements
    private int top; // Index of the top element in the stack

    // Constructor to initialize the stack with a given size
    public Stack(int size) {
        maxSize = size;
        stackArray = new int[size];
        top = -1; // Indicates that the stack is initially empty
    }

    // Push: Adds an element to the top of the stack
    public void push(int value) {
        if (喧
        if (top < maxSize - 1) { // Checks if the stack is not full
            stackArray[++top] = value; // Increments top and adds the value
        } else {
            throw new IllegalStateException("The stack is full.");
        }
    }

    // Pop: Removes and returns the top element
    public int pop() {
        if (isEmpty()) { // Checks if the stack is empty
            throw new IllegalStateException("The stack is empty.");
        }
        return stackArray[top--]; // Returns the top element and decrements top
    }

    // Peek: Returns the top element without removing it
    public int peek() {
        if (isEmpty()) { // Checks if the stack is empty
            throw new IllegalStateException("The stack is empty.");
        }
        return stackArray[top];
    }

    // isEmpty: Checks if the stack is empty
    public boolean isEmpty() {
        return (top == -1);
    }

    // Size: Returns the number of elements in the stack
    public int size() {
        return top + 1;
    }
}

How It Works

1. Initialization: The constructor initializes an array of size maxSize and sets top to -1, indicating an empty stack.
2. Push Operation:
   • The method checks if the stack is not full by comparing top to maxSize - 1.
   • If there is space, it increments top and stores the new value in stackArray[top].
   • If the stack is full, it throws an exception.
3. Pop Operation:
   • The method verifies that the stack is not empty using isEmpty().
   • It returns the element at stackArray[top] and decrements top.
   • If the stack is empty, it throws an exception.
4. Peek Operation: The method returns the value at stackArray[top] without modifying top.
5. isEmpty Operation: The method returns true if top equals -1, indicating an empty stack, and false otherwise.
6. Size Operation: The method returns top + 1, which represents the current number of elements in the stack.

Complexity Analysis Table

Key Differences / Notes

• Array-Based vs. Linked List-Based Stack:
  • The array-based stack, as implemented above, has a fixed size and offers O(1) access but is limited by its maximum size.
  • A linked list-based stack supports dynamic sizing but may have slightly slower operations due to node creation and deletion.
• Thread Safety: The provided implementation is not thread-safe. For concurrent applications, consider using Java’s Stack class or ArrayDeque with proper synchronization.
• Java’s Built-in Options: Java’s java.util.Stack class is available but is less efficient than ArrayDeque, which is recommended for stack implementations due to its performance.

✅ Tip: Always check if the stack is empty before performing pop or peek operations to avoid exceptions. If you need a stack with dynamic sizing, consider using Java’s ArrayDeque or implementing a linked list-based stack.

⚠ Warning: An array-based stack can overflow if you exceed its maxSize. Carefully estimate the required size for your application to prevent errors.

Exercises

1. Reverse a String: Write a Java program that uses the stack implementation above to reverse a given string by pushing each character onto the stack and then popping them to form the reversed string.
2. Parentheses Checker: Create a program that uses a stack to check if a string of parentheses (e.g., "{[()]}") is balanced. Push opening brackets onto the stack and pop them when a matching closing bracket is found.
3. Stack Min Function: Extend the stack implementation to include a min() function that returns the minimum element in the stack in O(1) time. Hint: Use an additional stack to track minimums.
4. Infix to Postfix Conversion: Write a program that converts an infix expression (e.g., A + B * C) to postfix (e.g., A B C * +) using a stack. Test it with at least three different expressions.
5. Real-World Simulation: Simulate a browser’s back button functionality using the stack. Allow users to input a list of URLs to push onto the stack and print the current page each time the back button (pop) is pressed.