Stack

A stack is a linear data structure that follows the Last-In-First-Out (LIFO) principle. Only the most recently added element can be accessed or removed.

Key Characteristics

• LIFO behavior: The last element pushed onto the stack is the first one popped off.
• Single access point: All operations occur at the top of the stack.
• Fixed or dynamic capacity: Depending on implementation, stacks may have a predefined limit or grow as needed.

Common Operations

• push(item): Adds an item to the top.
• pop(): Removes and returns the top item.
• top() or peek(): Returns the top item without removal.
• isEmpty(): Checks if the stack contains no elements.
• size(): Returns the number of elements currently in the stack.

Array-Based Implementation Example

public class SimpleStack<E> {
    private Object[] buffer;
    private int index;
    private final int limit;

    public SimpleStack(int maxSize) {
        this.limit = maxSize;
        this.buffer = new Object[maxSize];
        this.index = -1;
    }

    public void push(E value) {
        if (index + 1 >= limit) {
            throw new RuntimeException("Stack overflow");
        }
        buffer[++index] = value;
    }

    @SuppressWarnings("unchecked")
    public E pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack underflow");
        }
        return (E) buffer[index--];
    }

    @SuppressWarnings("unchecked")
    public E top() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return (E) buffer[index];
    }

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

    public int count() {
        return index + 1;
    }
}

This generic implementation uses an array with bounds checking. The index tracks the current top position, starting at -1 for an empty stack.

Practical Uses

• Managing function call frames and local variables during execution.
• Evaluating postfix (Reverse Polish) expressions.
• Supporting undo mechanisms in applications.
• Implementing depth-first traversal in graphs and trees.
• Backtracking algorithms like maze solvers or constraint satisfaction problems.

---

Heap

The term "heap" refers to two distinct concepts: a specialized tree-based data structure and a region of memory used for dynamic allocation.

Heap as a Data Structure

A heap is a complete binary tree that satisfies the heap property:

• In a min-heap, each parent node is less than or equal to its children.
• In a max-heap, each parent node is greater than or equal to its children.

Because it’s a complete binary tree, heaps are efficiently represented using arrays, where for any element at index i:

• Left child is at 2*i + 1
• Right child is at 2*i + 2
• Parent is at (i - 1) / 2

Core Operations

• insert(value): Adds a new element and restores heap order via bubble-up.
• extractMin() / extractMax(): Removes and returns the root, then restores order via sink-down.
• peek(): Returns the root without removal.
• decreaseKey() / increaseKey(): Adjusts a node’s value and reorders the heap.

Applications

• Priority queues (e.g., task scheduling).
• Heap sort algorithm.
• Efficiently retrieving top-k elements.

Java’s PriorityQueue implements a min-heap by default:

import java.util.PriorityQueue;

public class MinHeapDemo {
    public static void main(String[] args) {
        PriorityQueue<Integer> pq = new PriorityQueue<>();
        pq.offer(30);
        pq.offer(10);
        pq.offer(20);

        while (!pq.isEmpty()) {
            System.out.println(pq.poll()); // Outputs: 10, 20, 30
        }
    }
}

Heap in Memory Management

In runtime environments like the JVM, the heap is a shared memory area used for dynamic object allocation.

Characteristics

• Dynamically sized: Objects are allocated here when their lifetime isn’t known at compile time.
• Managed by garbage collector: In managed languages (e.g., Java), unused objects are automatically reclaimed.
• Slower access: Compared to stack allocation, heap operations involve more overhead due to bookkeeping and potential fragmentation.
• Shared across threads: All threads in a process share the same heap space.

Unlike the stack—which stores method frames and local primitives—the heap holds all instantiated objects and arrays in Java. Its size can be tuned via JVM flags like -Xmx and -Xms.

Memory leaks can occur if objects remain reachable unintentionally, preventing garbage collection. Tools like profilers help diagnose such issues by analyzing heap dumps.