Mastering the Stack Data Structure: A Comprehensive Java Implementation Guide

Introduction:

Stacks are a fundamental data structure in computer science and are widely used in various programming scenarios. In this article, we’ll explore the concept of stacks, discuss their typical use cases, and implement a basic stack in Java using core data structure principles.

Before diving in, make sure to subscribe to my Telegram channel for more content: https://t.me/+cbu174jYR0s4OWFi

What is a Stack?

A stack is a linear data structure that follows the LIFO (Last-In-First-Out) principle. This means that the last element added to the stack will be the first one to be removed. You can visualize it as a stack of plates — when you add a new plate, it goes on top, and when you take one out, you remove the one from the top.

Key Operations of a Stack:

• Push: Adds an element to the top of the stack.
• Pop: Removes and returns the top element from the stack.
• Peek: Returns the top element without removing it.
• isEmpty: Checks if the stack is empty.
• Size: Returns the number of elements in the stack.

Common Use Cases for Stacks

• Function Call Management: Used in recursive algorithms and maintaining the state of function calls.
• Expression Evaluation and Parsing: Useful for evaluating postfix, infix, and prefix expressions.
• Undo Mechanisms: Helps track the state of an application for implementing undo operations.
• Browser History Navigation: Manages the sequence of visited pages.

Stack Algorithm and Implementation in Java using an Array

Let’s now see how to implement a stack using Java. We’ll create a basic stack class that uses an array to store elements and supports all the primary stack operations.

/**
 * A simple implementation of a stack data structure using an array.
 * The stack follows the Last-In-First-Out (LIFO) principle.
 */
public class Stack {
    private int maxSize;      // Maximum size of the stack
    private int top;          // Index of the top element
    private int[] stackArray; // Array to store stack elements

    /**
     * Constructs a stack with a specified maximum size.
     *
     * @param size the maximum number of elements the stack can hold
     */
    public Stack(int size) {
        this.maxSize = size;
        this.stackArray = new int[maxSize];
        this.top = -1; // Initially, the stack is empty
    }

    /**
     * Pushes an element onto the top of the stack.
     *
     * @param value the value to be pushed onto the stack
     */
    public void push(int value) {
        if (isFull()) {
            System.out.println("Stack is full. Cannot push " + value);
        } else {
            stackArray[++top] = value;
            System.out.println("Pushed " + value);
        }
    }

    /**
     * Pops the top element from the stack and returns it.
     *
     * @return the top element of the stack, or -1 if the stack is empty
     */
    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty. Cannot pop.");
            return -1;
        } else {
            return stackArray[top--];
        }
    }

    /**
     * Peeks at the top element of the stack without removing it.
     *
     * @return the top element of the stack, or -1 if the stack is empty
     */
    public int peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty. Cannot peek.");
            return -1;
        } else {
            return stackArray[top];
        }
    }

    /**
     * Checks whether the stack is empty.
     *
     * @return true if the stack is empty, false otherwise
     */
    public boolean isEmpty() {
        return top == -1;
    }

    /**
     * Checks whether the stack is full.
     *
     * @return true if the stack is full, false otherwise
     */
    public boolean isFull() {
        return top == maxSize - 1;
    }

    /**
     * Returns the current number of elements in the stack.
     *
     * @return the number of elements in the stack
     */
    public int size() {
        return top + 1;
    }

    /**
     * Main method for testing the Stack implementation.
     *
     * @param args the command-line arguments (not used)
     */
    public static void main(String[] args) {
        Stack stack = new Stack(5); // Create a stack of size 5

        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        stack.push(50);

        System.out.println("Top element: " + stack.peek()); // Should print 50
        System.out.println("Popped element: " + stack.pop()); // Should print 50
        System.out.println("Is stack empty? " + stack.isEmpty()); // Should print false
    }
}

Breakdown of the Implementation

1. Constructor: Initializes the stack with a maximum size and sets the top index to -1.
2. Push: Adds an element to the stack if there is space available.
3. Pop: Removes and returns the top element if the stack is not empty.
4. Peek: Returns the top element without removing it, useful for checking the top element.
5. isEmpty: Returns true if the stack is empty; otherwise, false.
6. isFull: Returns true if the stack has reached its maximum capacity.
7. Size: Returns the current number of elements in the stack.

Testing the Stack

The main method provides a basic test case to see the stack operations in action. Feel free to modify and extend it to test additional scenarios.

Stack Algorithm and Implementation in Java using linked list structure with nodes

Implementing a stack using a linked list structure with nodes allows for dynamic memory allocation and eliminates the need to define a maximum size for the stack. Here’s how you can implement a stack using nodes in Java, including Javadoc comments for clarity.

/**
 * A class representing a node in the stack.
 *
 * @param <T> the type of data stored in the node
 */
class Node<T> {
    T data;       // Data stored in the node
    Node<T> next; // Reference to the next node in the stack

    /**
     * Constructor to create a new node with given data.
     *
     * @param data the data to be stored in the node
     */
    public Node(T data) {
        this.data = data;
        this.next = null; // Initially, the next node is null
    }
}

/**
 * A stack implementation using a linked list.
 * This stack follows the Last-In-First-Out (LIFO) principle.
 *
 * @param <T> the type of elements stored in the stack
 */
public class LinkedListStack<T> {
    private Node<T> top; // Pointer to the top node of the stack

    /**
     * Constructs an empty stack.
     */
    public LinkedListStack() {
        this.top = null; // Initially, the stack is empty
    }

    /**
     * Pushes an element onto the top of the stack.
     *
     * @param value the value to be pushed onto the stack
     */
    public void push(T value) {
        Node<T> newNode = new Node<>(value); // Create a new node
        newNode.next = top;                  // Link the new node to the current top
        top = newNode;                       // Update the top to the new node
        System.out.println("Pushed " + value);
    }

    /**
     * Pops the top element from the stack and returns it.
     *
     * @return the top element of the stack, or null if the stack is empty
     */
    public T pop() {
        if (isEmpty()) {
            System.out.println("Stack is empty. Cannot pop.");
            return null;
        } else {
            T poppedValue = top.data; // Get the top value
            top = top.next;            // Update the top to the next node
            return poppedValue;        // Return the popped value
        }
    }

    /**
     * Peeks at the top element of the stack without removing it.
     *
     * @return the top element of the stack, or null if the stack is empty
     */
    public T peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty. Cannot peek.");
            return null;
        } else {
            return top.data; // Return the top value without removing it
        }
    }

    /**
     * Checks whether the stack is empty.
     *
     * @return true if the stack is empty, false otherwise
     */
    public boolean isEmpty() {
        return top == null; // If top is null, the stack is empty
    }

    /**
     * Returns the current number of elements in the stack.
     *
     * @return the number of elements in the stack
     */
    public int size() {
        int size = 0;
        Node<T> current = top; // Start from the top of the stack

        while (current != null) {
            size++;                    // Increment the size for each node
            current = current.next;    // Move to the next node
        }

        return size; // Return the total size
    }

    /**
     * Main method for testing the LinkedListStack implementation.
     *
     * @param args the command-line arguments (not used)
     */
    public static void main(String[] args) {
        LinkedListStack<Integer> stack = new LinkedListStack<>(); // Create a new stack

        stack.push(10);
        stack.push(20);
        stack.push(30);
        stack.push(40);
        stack.push(50);

        System.out.println("Top element: " + stack.peek()); // Should print 50
        System.out.println("Popped element: " + stack.pop()); // Should print 50
        System.out.println("Is stack empty? " + stack.isEmpty()); // Should print false
    }
}

Explanation:

1. Generic Node Class:

• The Node class is generic, allowing it to hold data of any type T.
• The data field stores the actual value, and the next field points to the next node in the stack.

2. Generic LinkedListStack Class:

• The LinkedListStack class is also generic, enabling it to handle any type of elements.
• Constructor: Initializes an empty stack with top set to null.
• Push Method: Creates a new node and links it to the current top of the stack, then updates the top pointer.
• Pop Method: Removes the top node and returns its data, handling the empty stack case.
• Peek Method: Returns the data of the top node without removing it.
• isEmpty Method: Checks if the stack is empty.
• Size Method: Counts the number of elements in the stack.

Advantages of Generics:

• Type Safety: The stack can only store elements of the specified type, reducing the risk of ClassCastException.
• Flexibility: You can create stacks for different types (e.g., Integer, String, custom objects) without changing the stack's code.

Conclusion

Both implementations of the stack data structure (array-based and linked list-based) serve the same fundamental purpose but are suited for different use cases depending on the requirements of the application.

Array-Based Stack

1. Advantages:

• Simplicity: The implementation is straightforward, making it easy to understand and use.
• Performance: Accessing elements by index in an array is O(1), leading to efficient push and pop operations if the array is not full.
• Memory Overhead: No additional memory overhead for node pointers; the stack elements are stored contiguously in memory.

2. Disadvantages:

• Fixed Size: The stack has a predetermined capacity, which can lead to stack overflow if the limit is exceeded.
• Wasted Space: If the maximum size is not fully utilized, memory can be wasted.
• Resizing Complexity: If dynamic resizing is implemented (e.g., doubling the array size), it can introduce complexity and performance overhead during resizing operations.

3. Use Cases:

• Suitable for scenarios where the maximum stack size is known beforehand and won’t exceed that limit (e.g., parsing expressions, managing function calls).

Linked List-Based Stack

1. Advantages:

• Dynamic Size: The stack can grow and shrink as needed, eliminating the risk of overflow (as long as memory is available).
• No Wasted Space: Memory is allocated only as needed, which can be more efficient when the number of elements varies significantly.
• Flexibility: Can easily handle large data without worrying about predefined limits.

2. Disadvantages:

• Memory Overhead: Each node requires additional memory for a pointer/reference to the next node, which can lead to higher memory usage compared to an array for small stacks.
• Performance: Traversing the stack to count elements or access elements requires O(n) time, while array-based stacks allow O(1) access.

3. Use Cases:

• Ideal for applications where the number of elements is highly variable and unpredictable (e.g., depth-first search in graphs, managing recursive function calls when the depth is unknown).

Feel free to leave comments and suggestions if you have any questions or thoughts!

For more details, join my Telegram channel: https://t.me/+cbu174jYR0s4OWFi