Stacks & Queues Implementation

Array-Based Stack (15 points)

Create a class ArrayStack.java with dynamic resizing:

public class ArrayStack<T> {
    private T[] array;
    private int top;
    private static final int DEFAULT_CAPACITY = 10;
    
    public ArrayStack();                // Default capacity
    public ArrayStack(int capacity);    // Custom capacity
    
    public void push(T item);           // O(1) amortized
    public T pop();                     // O(1)
    public T peek();                    // O(1)
    public boolean isEmpty();           // O(1)
    public int size();                  // O(1)
    public void clear();                // O(1)
    
    // Dynamic resizing
    private void resize(int newCapacity);
}

Requirements:

• Double capacity when full, halve when 1/4 full
• Throw EmptyStackException for pop/peek on empty stack
• Use generics for type safety

Linked List Stack (15 points)

Create a class LinkedStack.java:

public class LinkedStack<T> {
    private class Node {
        T data;
        Node next;
        Node(T data) { this.data = data; }
    }
    
    private Node top;
    private int size;
    
    public void push(T item);           // O(1)
    public T pop();                     // O(1)
    public T peek();                    // O(1)
    public boolean isEmpty();           // O(1)
    public int size();                  // O(1)
    public void clear();                // O(1)
}

Circular Queue (15 points)

Create a class CircularQueue.java with fixed capacity:

public class CircularQueue<T> {
    private T[] array;
    private int front;
    private int rear;
    private int size;
    private int capacity;
    
    public CircularQueue(int capacity);
    
    public void enqueue(T item);        // O(1) - throws if full
    public T dequeue();                 // O(1) - throws if empty
    public T front();                   // O(1)
    public T rear();                    // O(1)
    public boolean isEmpty();           // O(1)
    public boolean isFull();            // O(1)
    public int size();                  // O(1)
}

// Example usage:
CircularQueue<Integer> queue = new CircularQueue<>(5);
queue.enqueue(1);  // [1, _, _, _, _]
queue.enqueue(2);  // [1, 2, _, _, _]
queue.dequeue();   // returns 1, [_, 2, _, _, _]
queue.enqueue(3);  // [_, 2, 3, _, _]
// When rear reaches end, it wraps around to front

Deque (Double-Ended Queue) (15 points)

Create a class Deque.java supporting operations at both ends:

public class Deque<T> {
    // Can use doubly linked list or circular array
    
    public void addFirst(T item);       // O(1)
    public void addLast(T item);        // O(1)
    public T removeFirst();             // O(1)
    public T removeLast();              // O(1)
    public T peekFirst();               // O(1)
    public T peekLast();                // O(1)
    public boolean isEmpty();           // O(1)
    public int size();                  // O(1)
}

Balanced Parentheses (15 points)

Check if parentheses are balanced:

// P5a: Check if string has balanced parentheses (), [], {}
// "({[]})" → true
// "([)]" → false
// "{[]}" → true
public boolean isBalanced(String s);

// P5b: Find minimum insertions to make balanced
// "(((" → 3 (need 3 closing)
// "())" → 1 (need 1 opening)
// "(()))" → 1
public int minInsertions(String s);

// P5c: Remove minimum parentheses to make valid
// "()())()" → "()()()"
// "(a(b(c)d)" → "a(b(c)d)" or "(ab(c)d)"
public String removeInvalidParentheses(String s);

Expression Evaluation (15 points)

Evaluate mathematical expressions:

// P6a: Evaluate postfix expression
// "2 3 + 4 *" → 20 (i.e., (2+3)*4)
// "5 1 2 + 4 * + 3 -" → 14
public int evaluatePostfix(String expression);

// P6b: Convert infix to postfix
// "2 + 3 * 4" → "2 3 4 * +"
// "(2 + 3) * 4" → "2 3 + 4 *"
public String infixToPostfix(String expression);

// P6c: Evaluate infix expression with +, -, *, /, ()
// "2 + 3 * 4" → 14
// "(2 + 3) * 4" → 20
// "10 + 2 * 6" → 22
public int evaluateInfix(String expression);

Monotonic Stack Problems (15 points)

Use monotonic stacks for efficient solutions:

// P7a: Next Greater Element
// For each element, find the next greater element to its right
// [4, 5, 2, 25] → [5, 25, 25, -1]
// [13, 7, 6, 12] → [-1, 12, 12, -1]
public int[] nextGreaterElement(int[] arr);

// P7b: Daily Temperatures
// Days until a warmer temperature
// [73, 74, 75, 71, 69, 72, 76, 73] → [1, 1, 4, 2, 1, 1, 0, 0]
public int[] dailyTemperatures(int[] temperatures);

// P7c: Largest Rectangle in Histogram
// [2, 1, 5, 6, 2, 3] → 10 (rectangle of height 5, width 2)
public int largestRectangleInHistogram(int[] heights);

Stack Design Problems (15 points)

Implement special stack variants:

// P8a: Min Stack - O(1) getMin()
public class MinStack {
    public void push(int val);
    public void pop();
    public int top();
    public int getMin();  // O(1) - return minimum element
}

// P8b: Max Stack - O(1) getMax() and popMax()
public class MaxStack {
    public void push(int val);
    public int pop();
    public int top();
    public int peekMax();
    public int popMax();  // Remove and return max element
}

// P8c: Stack with middle operations
public class MiddleStack {
    public void push(int val);
    public int pop();
    public int getMiddle();    // O(1)
    public int deleteMiddle(); // O(1)
}

Sliding Window Maximum (15 points)

Use deque for efficient sliding window:

// P9a: Maximum of each sliding window of size k
// [1, 3, -1, -3, 5, 3, 6, 7], k=3 → [3, 3, 5, 5, 6, 7]
// Window positions: [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6], [3,6,7]
public int[] maxSlidingWindow(int[] nums, int k);

// P9b: Minimum of each sliding window of size k
// [1, 3, -1, -3, 5, 3, 6, 7], k=3 → [-1, -3, -3, -3, 3, 3]
public int[] minSlidingWindow(int[] nums, int k);

// P9c: First negative in each window of size k
// [12, -1, -7, 8, -15, 30, 16, 28], k=3 → [-1, -1, -7, -15, -15, 0]
public int[] firstNegativeInWindow(int[] nums, int k);

Queue Design & Applications (15 points)

Implement special queue variants:

// P10a: Implement Queue using Two Stacks
public class QueueUsingStacks<T> {
    public void enqueue(T item);  // O(1)
    public T dequeue();           // O(1) amortized
    public T peek();
    public boolean isEmpty();
}

// P10b: Implement Stack using Two Queues
public class StackUsingQueues<T> {
    public void push(T item);
    public T pop();
    public T top();
    public boolean isEmpty();
}

// P10c: LRU Cache using Queue + HashMap
public class LRUCache {
    public LRUCache(int capacity);
    public int get(int key);      // O(1)
    public void put(int key, int value);  // O(1)
}