Stacks and Queues

1. Stack Introduction

2. Queue Introduction

3. Advanced Applications

Array-based Stack

public class ArrayStack {
    private T[] array;
    private int top;
    private static final int DEFAULT_CAPACITY = 10;
    
    @SuppressWarnings("unchecked")
    public ArrayStack() {
        array = (T[]) new Object[DEFAULT_CAPACITY];
        top = -1;
    }
    
    public void push(T item) {
        if (top == array.length - 1) {
            resize();
        }
        array[++top] = item;
    }
    
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        T item = array[top];
        array[top--] = null; // Help with garbage collection
        return item;
    }
    
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return array[top];
    }
    
    public boolean isEmpty() {
        return top == -1;
    }
    
    public int size() {
        return top + 1;
    }
    
    @SuppressWarnings("unchecked")
    private void resize() {
        T[] newArray = (T[]) new Object[array.length * 2];
        System.arraycopy(array, 0, newArray, 0, array.length);
        array = newArray;
    }
}

Linked List Stack

public class LinkedStack {
    private static class Node {
        private T data;
        private Node next;
        
        public Node(T data) {
            this.data = data;
        }
    }
    
    private Node top;
    private int size;
    
    public LinkedStack() {
        top = null;
        size = 0;
    }
    
    public void push(T item) {
        Node newNode = new Node<>(item);
        newNode.next = top;
        top = newNode;
        size++;
    }
    
    public T pop() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        T item = top.data;
        top = top.next;
        size--;
        return item;
    }
    
    public T peek() {
        if (isEmpty()) {
            throw new EmptyStackException();
        }
        return top.data;
    }
    
    public boolean isEmpty() {
        return top == null;
    }
    
    public int size() {
        return size;
    }
}

Array-based Queue

public class ArrayQueue {
    private T[] array;
    private int front;
    private int rear;
    private int size;
    private static final int DEFAULT_CAPACITY = 10;
    
    @SuppressWarnings("unchecked")
    public ArrayQueue() {
        array = (T[]) new Object[DEFAULT_CAPACITY];
        front = 0;
        rear = -1;
        size = 0;
    }
    
    public void enqueue(T item) {
        if (size == array.length) {
            resize();
        }
        rear = (rear + 1) % array.length;
        array[rear] = item;
        size++;
    }
    
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        T item = array[front];
        array[front] = null; // Help with garbage collection
        front = (front + 1) % array.length;
        size--;
        return item;
    }
    
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return array[front];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public int size() {
        return size;
    }
    
    @SuppressWarnings("unchecked")
    private void resize() {
        T[] newArray = (T[]) new Object[array.length * 2];
        for (int i = 0; i < size; i++) {
            newArray[i] = array[(front + i) % array.length];
        }
        array = newArray;
        front = 0;
        rear = size - 1;
    }
}

Linked List Queue

public class LinkedQueue {
    private static class Node {
        private T data;
        private Node next;
        
        public Node(T data) {
            this.data = data;
        }
    }
    
    private Node front;
    private Node rear;
    private int size;
    
    public LinkedQueue() {
        front = null;
        rear = null;
        size = 0;
    }
    
    public void enqueue(T item) {
        Node newNode = new Node<>(item);
        if (isEmpty()) {
            front = newNode;
        } else {
            rear.next = newNode;
        }
        rear = newNode;
        size++;
    }
    
    public T dequeue() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        T item = front.data;
        front = front.next;
        if (front == null) {
            rear = null; // Queue is now empty
        }
        size--;
        return item;
    }
    
    public T peek() {
        if (isEmpty()) {
            throw new NoSuchElementException();
        }
        return front.data;
    }
    
    public boolean isEmpty() {
        return front == null;
    }
    
    public int size() {
        return size;
    }
}

Stack Exercises

Implement solutions to these classic stack problems:

• Balanced parentheses check
• Evaluate postfix expressions
• Implement a min stack (a stack that can retrieve its minimum element in O(1) time)
• Stack-based implementation of queue

Queue Exercises

Practice queue implementation with these problems:

• Implement a circular buffer
• Implement a priority queue
• Queue-based implementation of stack
• Level-order traversal of a binary tree

Advanced Problems

Challenge yourself with these more complex problems:

• Implement a sliding window maximum algorithm
• Solve the stock span problem
• Design a LRU (Least Recently Used) cache

Online Practice Resources:

• LeetCode Stack Problems - Practice Here
• LeetCode Queue Problems - Practice Here
• HackerRank Challenges - Practice Here