Stack data structure

A stack is a linear data structure that operates on a Last-In, First-Out (LIFO) principle. This means the last element added to the stack is the first one to be removed. It is analogous to a stack of plates where you add new plates on top and take them off from the top as well. Stacks are used in various applications like parsing expressions, managing function calls, and implementing undo operations.

Key Characteristics of a Stack

• LIFO Principle: The last element added is the first to be removed.
• Push and Pop Operations: Push adds an element to the top, and pop removes the top element.
• Peek Operation: Returns the top element without removing it.
• Empty Check: Determines if the stack is empty.

Applications of Stack

• Function Call Management: Stores function calls to manage nested function calls.
• Expression Parsing: Converts infix expressions to postfix or prefix and evaluates them.
• Undo Mechanism: Tracks states to enable undo functionality in applications.

Stack Implementation in Java

Java provides several ways to implement a stack, including using arrays, linked lists, and the Java Collections Framework.

Array-Based Stack

An array-based stack uses a fixed-size array to hold elements. Although it’s easy to implement, it doesn’t dynamically resize and hence might lead to stack overflow or underflow.

class ArrayStack {
    private int top;
    private int[] stack;
    private int capacity;

    public ArrayStack(int capacity) {
        this.capacity = capacity;
        stack = new int[capacity];
        top = -1;
    }

    public boolean isEmpty() {
        return top == -1;
    }

    public boolean isFull() {
        return top == capacity - 1;
    }

    public void push(int value) {
        if (isFull()) {
            System.out.println("Stack Overflow");
            return;
        }
        stack[++top] = value;
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack Underflow");
            return Integer.MIN_VALUE;
        }
        return stack[top--];
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty");
            return Integer.MIN_VALUE;
        }
        return stack[top];
    }
}

Linked List-Based Stack

A linked list-based stack uses a linked list to store elements, providing dynamic resizing. Each node contains data and a reference to the next node.

class LinkedListStack {
    class Node {
        int data;
        Node next;

        Node(int data) {
            this.data = data;
            next = null;
        }
    }

    private Node top;

    public LinkedListStack() {
        top = null;
    }

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

    public void push(int value) {
        Node newNode = new Node(value);
        newNode.next = top;
        top = newNode;
    }

    public int pop() {
        if (isEmpty()) {
            System.out.println("Stack Underflow");
            return Integer.MIN_VALUE;
        }
        int value = top.data;
        top = top.next;
        return value;
    }

    public int peek() {
        if (isEmpty()) {
            System.out.println("Stack is empty");
            return Integer.MIN_VALUE;
        }
        return top.data;
    }
}

Stack Using Java Collections Framework

Java’s Stack class, which extends Vector, is a built-in class that provides stack operations with dynamic resizing. It also provides several utility methods to make stack operations easier.

import java.util.Stack;

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

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

        System.out.println("Top element: " + stack.peek());
        System.out.println("Stack size: " + stack.size());

        System.out.println("Popping element: " + stack.pop());
        System.out.println("After pop, top element: " + stack.peek());
    }
}

Advanced Stack Implementations

Thread-Safe Stack

In multi-threaded environments, stacks need to be thread-safe to prevent data corruption. Java’s ConcurrentLinkedDeque provides a thread-safe stack-like structure

import java.util.concurrent.ConcurrentLinkedDeque;

public class ConcurrentStackExample {
    public static void main(String[] args) {
        ConcurrentLinkedDeque<Integer> stack = new ConcurrentLinkedDeque<>();

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

        System.out.println("Top element: " + stack.peek());
        System.out.println("Stack size: " + stack.size());

        System.out.println("Popping element: " + stack.pop());
        System.out.println("After pop, top element: " + stack.peek());
    }
}

Double-Ended Stack (Deque)

Deque (double-ended queue) supports both stack and queue operations, allowing elements to be added or removed from both ends.

import java.util.ArrayDeque;
import java.util.Deque;

public class DequeStackExample {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();

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

        System.out.println("Top element: " + stack.peek());
        System.out.println("Stack size: " + stack.size());

        System.out.println("Popping element: " + stack.pop());
        System.out.println("After pop, top element: " + stack.peek());
    }
}

Performance Analysis

• Array-Based Stack: Push and pop operations have O(1) time complexity, but resizing is expensive.
• Linked List-Based Stack: Push and pop operations have O(1) time complexity, and no resizing is needed.
• Java Stack Class: Provides dynamic resizing but has performance overhead due to synchronization.