Fundamentals of Stack Data Structures

A stack is an abstract data type that follows the Last-In-First-Out (LIFO) principle. Elements are added and removed exclusively from one end, known as the top. This mechanism mimics physical stacks, such as a pile of plates, where the last item placed on top is the first one retrieved.

Core Operations

The primary operations supported by a standard stack include:

• Push: Insert an element onto the top.
• Pop: Remove and return the top element.
• Peek: Access the top element without removing it.
• Is Empty: Determine if the stack contains no items.
• Size: Retrieve the current count of elements.

In modern Java development, while legacy classes exist, developers often utilize interfaces like {@code Deque}. However, understanding the underlying mechanics through custom implementation remains crucial.

public class BasicTest {
    public static void main(String[] args) {
        // Utilizing built-in collection frameworks
        java.util.Stack<Integer> systemStack = new java.util.Stack<>();
        
        systemStack.push(10);
        systemStack.push(20);
        
        System.out.println("Popped value: " + systemStack.pop());
        System.out.println("Top value: " + systemStack.peek());
        System.out.println("Is empty? " + systemStack.isEmpty());
        System.out.println("Current size: " + systemStack.size());
    }
}

Building a Custom Stack

To understand internal memory management, we can implement a stack using an array. This approach mirrors how dynamic arrays function internally.

public class DynamicArrayStack {
    private int[] buffer;
    private int topIndex;

    public DynamicArrayStack() {
        this.buffer = new int[16];
        this.topIndex = 0;
    }

    /**
     * Inserts a value into the stack.
     * If capacity is reached, the underlying buffer expands.
     */
    public void push(int val) {
        if (isFull()) {
            expandCapacity();
        }
        buffer[topIndex++] = val;
    }

    private boolean isFull() {
        return topIndex == buffer.length;
    }

    private void expandCapacity() {
        buffer = java.util.Arrays.copyOf(buffer, buffer.length * 2);
    }

    /**
     * Removes the most recently added element.
     */
    public int pop() {
        if (isEmpty()) {
            throw new RuntimeException("Stack Underflow");
        }
        int value = buffer[--topIndex];
        return value;
    }

    public int peek() {
        if (isEmpty()) {
            throw new RuntimeException("Stack is empty");
        }
        return buffer[topIndex - 1];
    }

    public boolean isEmpty() {
        return topIndex == 0;
    }

    public static void main(String[] args) {
        DynamicArrayStack customStack = new DynamicArrayStack();
        customStack.push(1);
        customStack.push(2);
        customStack.push(3);

        System.out.print(customStack.pop() + " "); 
        System.out.print(customStack.pop() + " "); 
        System.out.print(customStack.peek() + " ");
    }
}

Applications and Variations

Beyond simple arrays, stacks can be constructed using linked structures. A singly-linked list allows O(1) push and pop operations only if the head is utilized as the stack top. Head insertion ensures constant time complexity, whereas tail insertion would degrade performance to O(n).

Simulating Recursion Iteratively
Recursion inherently uses the call stack. To avoid potential stack overflow issues or overhead, algorithms involving recursion can sometimes be refactored using an explicit stack object. For instance, reversing a list traversal:

// Recursive approach (Conceptual)
// void printReverse(Node head) {
//     if(head != null) {
//         printReverse(head.next);
//         System.out.print(head.val + " ");
//     }
// }

// Iterative approach using explicit Stack
private void printReverseIterative(Node head) {
    if (head == null) return;
    
    // Push nodes onto stack
    java.util.Deque<Node> nodeStack = new java.util.ArrayDeque<>();
    Node current = head;
    
    while (current != null) {
        nodeStack.push(current);
        current = current.next;
    }
    
    // Pop and process
    while (!nodeStack.isEmpty()) {
        System.out.print(nodeStack.pop().val + " ");
    }
}

class Node {
    int val;
    Node next;
    Node(int v) { val = v; }
}

Understanding Queue Data Structures

Unlike stacks, queues operate on a First-In-First-Out (FIFO) basis. New elements enter at the rear (back), and existing elements are removed from the front. This structure resembles a line of people waiting for service.

Standard Queue Interface

In Java, the {@code Queue} interface defines standard operations, typically implemented via {@code LinkedList} or {@code PriorityQueue}. Note that the {@code add()} method throws an exception on capacity limits, while {@code offer()} returns false.

public class StandardQueueExample {
    public static void main(String[] args) {
        java.util.Queue<Integer> queue = new java.util.LinkedList<>();
        
        queue.offer(1);
        queue.offer(2);
        queue.offer(3);
        
        // Retrieves the head
        System.out.println(queue.peek()); 
        
        // Removes and retrieves the head
        System.out.println(queue.poll());
    }
}

Custom Queue Implementations

Doubly Linked List Approach
Using a linked structure avoids fixed capacity constraints. Maintaining both head and tail pointers allows for efficient O(1) insertions at the end and deletions from the beginning.

public class LinkedQueue {
    private static class ListNode {
        int data;
        ListNode prev, next;
        ListNode(int val) { this.data = val; }
    }

    private ListNode head;
    private ListNode tail;
    private int size;

    public LinkedQueue() {
        head = null;
        tail = null;
        size = 0;
    }

    public void enqueue(int val) {
        ListNode newNode = new ListNode(val);
        if (head == null) {
            head = tail = newNode;
        } else {
            tail.next = newNode;
            newNode.prev = tail;
            tail = tail.next;
        }
        size++;
    }

    public int dequeue() {
        if (head == null) throw new RuntimeException("Queue Underflow");
        
        int val = head.data;
        head = head.next;
        if (head != null) {
            head.prev = null;
        } else {
            tail = null;
        }
        size--;
        return val;
    }

    public int peek() {
        if (head == null) throw new RuntimeException("Queue is empty");
        return head.data;
    }

    public boolean isEmpty() {
        return size == 0;
    }
}

Circular Array Queue

Standard array-based queues suffer from space inefficiency; as elements are dequeued, the beginning becomes unused. A circular queue wraps indices around the array boundaries to reuse available slots. To distinguish between full and empty states when head equals tail, one common strategy is to allocate one extra slot (buffer size + 1) and treat the queue as full when the next insertion position overlaps the head.

public class CircularBufferQueue {
    private int readPos;  // Front
    private int writePos; // Rear
    private int[] ringBuffer;

    public CircularBufferQueue(int capacity) {
        // Allocate extra slot to distinguish full from empty state
        this.ringBuffer = new int[capacity + 1]; 
        this.readPos = 0;
        this.writePos = 0;
    }

    public boolean enqueue(int value) {
        if (isFull()) return false;
        ringBuffer[writePos] = value;
        writePos = (writePos + 1) % ringBuffer.length;
        return true;
    }

    public boolean dequeue() {
        if (isEmpty()) return false;
        readPos = (readPos + 1) % ringBuffer.length;
        return true;
    }

    public int getFront() {
        if (isEmpty()) return -1;
        return ringBuffer[readPos];
    }

    public int getRear() {
        if (isEmpty()) return -1;
        // Calculate previous index manually due to wrapping
        int index = (writePos - 1 + ringBuffer.length) % ringBuffer.length;
        return ringBuffer[index];
    }

    private boolean isEmpty() {
        return readPos == writePos;
    }

    private boolean isFull() {
        return (writePos + 1) % ringBuffer.length == readPos;
    }
}

Double-Ended Queues (Deque)

A Deque (Double Ended Queue) generalizes the queue concept, allowing insertion and deletion at both ends. It satisfies the requirements of both a Stack (LIFO) and a Queue (FIFO). The interface {@code Deque} provides methods like {@code push}, {@code pop}, {@code addFirst}, and {@code addLast}.

Two primary implementations exist in Java:

1. {@code ArrayDeque}: Based on a resizable circular array. Generally offers superior performance for bulk operations.
2. {@code LinkedList}: A doubly-linked list implementation. Useful when frequent iteration over specific segments is required, though slightly heavier then ArrayDeque.

public class DequeUsageDemo {
    public static void main(String[] args) {
        // Array-based implementation
        java.util.Deque<String> arrayDeque = new java.util.ArrayDeque<>();
        arrayDeque.addFirst("Start");
        arrayDeque.addLast("End");
        arrayDeque.removeFirst();
        System.out.println(arrayDeque);

        // Link-based implementation
        java.util.Deque<String> linkedDeque = new java.util.LinkedList<>();
        linkedDeque.push("Top");
        System.out.println(linkedDeque.pop());
    }
}