Stacks and Queues - (Theory)

Stack Basics

A stack is a LIFO (Last In First Out) data structure. Key operations:

• Push: Add element to top (O(1))
• Pop: Remove top element (O(1))
• Peek/Top: View top element (O(1))
• isEmpty: Check if empty (O(1))

Java Implementation:

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

public class StackBasics {
    public static void main(String[] args) {
        Deque<Integer> stack = new ArrayDeque<>();
        
        // Push elements
        stack.push(10);
        stack.push(20);
        stack.push(30);
        
        System.out.println("Top element: " + stack.peek()); // 30
        
        // Pop elements
        System.out.println(stack.pop()); // 30
        System.out.println(stack.pop()); // 20
        
        // Check empty
        System.out.println("Is empty? " + stack.isEmpty()); // false
    }
}

Stack Patterns

1. Next Greater Element to Right (NGR)

For each element, find the next greater element to its right. If none, return -1.

Example:
Input: [4, 5, 2, 10] → Output: [5, 10, 10, -1]

Approach:

• Traverse right to left.
• Use stack to track larger elements.
• For each element, pop smaller elements from stack.

Java Code:

public int[] nextGreaterRight(int[] arr) {
    int n = arr.length;
    int[] res = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && stack.peek() <= arr[i]) {
            stack.pop();
        }
        res[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(arr[i]);
    }
    return res;
}

TC: O(n), SC: O(n)

2. Next Greater Element to Left (NGL)

For each element, find the next greater element to its left. If none, return -1.

Example:
Input: [4, 5, 2, 10] → Output: [-1, -1, 5, -1]

Java Code:

public int[] nextGreaterLeft(int[] arr) {
    int n = arr.length;
    int[] res = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && stack.peek() <= arr[i]) {
            stack.pop();
        }
        res[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(arr[i]);
    }
    return res;
}

TC: O(n), SC: O(n)

3. Next Smaller Element to Right (NSR)

For each element, find the next smaller element to its right. If none, return -1.

Example:
Input: [4, 5, 2, 10] → Output: [2, 2, -1, -1]

Java Code:

public int[] nextSmallerRight(int[] arr) {
    int n = arr.length;
    int[] res = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && stack.peek() >= arr[i]) {
            stack.pop();
        }
        res[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(arr[i]);
    }
    return res;
}

TC: O(n), SC: O(n)

4. Next Smaller Element to Left (NSL)

For each element, find the next smaller element to its left. If none, return -1.

Example:
Input: [4, 5, 2, 10] → Output: [-1, 4, -1, 2]

Java Code:

public int[] nextSmallerLeft(int[] arr) {
    int n = arr.length;
    int[] res = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && stack.peek() >= arr[i]) {
            stack.pop();
        }
        res[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(arr[i]);
    }
    return res;
}

TC: O(n), SC: O(n)

5. Stock Span Problem

Calculate the span of stock prices (days with price ≤ current price including current).

Example:
Input: [100, 80, 60, 70, 60, 75, 85] → Output: [1, 1, 1, 2, 1, 4, 6]

Java Code:

public int[] stockSpan(int[] prices) {
    int n = prices.length;
    int[] span = new int[n];
    Deque<Integer> stack = new ArrayDeque<>(); // Store indices
    
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && prices[stack.peek()] <= prices[i]) {
            stack.pop();
        }
        span[i] = stack.isEmpty() ? i + 1 : i - stack.peek();
        stack.push(i);
    }
    return span;
}

TC: O(n), SC: O(n)

6. Maximum Area Histogram (MAH)

Find the largest rectangle area under a histogram.

Approach:

• Use NSL and NSR to find boundaries for each bar.
• Area = height × (right boundary - left boundary - 1).

Java Code:

public int maxAreaHistogram(int[] heights) {
    int n = heights.length;
    int[] left = nextSmallerLeftIndex(heights);
    int[] right = nextSmallerRightIndex(heights);
    int maxArea = 0;
    
    for (int i = 0; i < n; i++) {
        int width = right[i] - left[i] - 1;
        maxArea = Math.max(maxArea, heights[i] * width);
    }
    return maxArea;
}

private int[] nextSmallerLeftIndex(int[] arr) {
    int n = arr.length;
    int[] res = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
            stack.pop();
        }
        res[i] = stack.isEmpty() ? -1 : stack.peek();
        stack.push(i);
    }
    return res;
}

private int[] nextSmallerRightIndex(int[] arr) {
    int n = arr.length;
    int[] res = new int[n];
    Deque<Integer> stack = new ArrayDeque<>();
    
    for (int i = n - 1; i >= 0; i--) {
        while (!stack.isEmpty() && arr[stack.peek()] >= arr[i]) {
            stack.pop();
        }
        res[i] = stack.isEmpty() ? n : stack.peek();
        stack.push(i);
    }
    return res;
}

TC: O(n), SC: O(n)

7. Expression Evaluation

a. Infix to Postfix

Convert infix expression to postfix.

Java Code:

public String infixToPostfix(String exp) {
    StringBuilder sb = new StringBuilder();
    Deque<Character> stack = new ArrayDeque<>();
    String precedence = "+-*/^";
    String associativity = "LLLLRL"; // L: Left, R: Right
    
    for (char c : exp.toCharArray()) {
        if (Character.isLetterOrDigit(c)) sb.append(c);
        else if (c == '(') stack.push(c);
        else if (c == ')') {
            while (!stack.isEmpty() && stack.peek() != '(') 
                sb.append(stack.pop());
            stack.pop(); // Remove '('
        } else {
            while (!stack.isEmpty() && 
                   (precedence.indexOf(stack.peek()) > precedence.indexOf(c) || 
                   (precedence.indexOf(stack.peek()) == precedence.indexOf(c) && 
                    associativity.charAt(precedence.indexOf(c)) == 'L')) {
                sb.append(stack.pop());
            }
            stack.push(c);
        }
    }
    while (!stack.isEmpty()) sb.append(stack.pop());
    return sb.toString();
}

b. Postfix Evaluation

Evaluate postfix expression.

Java Code:

public int evalPostfix(String postfix) {
    Deque<Integer> stack = new ArrayDeque<>();
    for (char c : postfix.toCharArray()) {
        if (Character.isDigit(c)) stack.push(c - '0');
        else {
            int b = stack.pop(), a = stack.pop();
            switch(c) {
                case '+': stack.push(a + b); break;
                case '-': stack.push(a - b); break;
                case '*': stack.push(a * b); break;
                case '/': stack.push(a / b); break;
                case '^': stack.push((int)Math.pow(a, b)); break;
            }
        }
    }
    return stack.pop();
}

TC: O(n) for both, SC: O(n)

8. Balanced Parentheses

Check if parentheses are balanced.

Java Code:

public boolean isBalanced(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c == '(' || c == '[' || c == '{') stack.push(c);
        else if (!stack.isEmpty() && 
                ((c == ')' && stack.peek() == '(') ||
                 (c == ']' && stack.peek() == '[') ||
                 (c == '}' && stack.peek() == '{'))) {
            stack.pop();
        } else return false;
    }
    return stack.isEmpty();
}

TC: O(n), SC: O(n)

9. Redundant Brackets

Check if expression has redundant brackets.

Java Code:

public boolean hasRedundant(String s) {
    Deque<Character> stack = new ArrayDeque<>();
    for (char c : s.toCharArray()) {
        if (c != ')') stack.push(c);
        else {
            boolean hasOperator = false;
            while (!stack.isEmpty() && stack.peek() != '(') {
                char top = stack.pop();
                if ("+-*/".indexOf(top) != -1) hasOperator = true;
            }
            if (!hasOperator) return true;
            stack.pop(); // Remove '('
        }
    }
    return false;
}

TC: O(n), SC: O(n)

10. Min Stack

Design a stack that supports getMin() in O(1) time.

Java Code:

class MinStack {
    private Deque<Integer> stack = new ArrayDeque<>();
    private Deque<Integer> minStack = new ArrayDeque<>();
    
    public void push(int val) {
        stack.push(val);
        if (minStack.isEmpty() || val <= minStack.peek()) 
            minStack.push(val);
    }
    
    public void pop() {
        if (stack.pop().equals(minStack.peek())) 
            minStack.pop();
    }
    
    public int top() { return stack.peek(); }
    public int getMin() { return minStack.peek(); }
}

TC: O(1) for all operations, SC: O(n)

Key Takeaways

• Operations: push(), pop(), peek(), isEmpty().
• Complexity: Most stack-based algorithms run in O(n) time and space.
• Applications: Expression parsing, backtracking, DFS, syntax checking.

Queue and Common Patterns

Queue Basics

A queue is a FIFO (First In First Out) data structure. Key operations:

• Enqueue: Add element to rear (O(1))
• Dequeue: Remove element from front (O(1))
• Front/Peek: View front element (O(1))
• isEmpty: Check if empty (O(1))

Java Implementation:

import java.util.LinkedList;
import java.util.Queue;

public class QueueBasics {
    public static void main(String[] args) {
        Queue<Integer> q = new LinkedList<>();
        
        // Enqueue elements
        q.add(10);
        q.add(20);
        q.add(30);
        
        System.out.println("Front element: " + q.peek()); // 10
        
        // Dequeue elements
        System.out.println(q.remove()); // 10
        System.out.println(q.remove()); // 20
        
        System.out.println("Is empty? " + q.isEmpty()); // false
    }
}

Queue Patterns

1. Sliding Window Maximum

Find maximum in each sliding window of size k.

Example:
Input: [1,3,-1,-3,5,3,6,7], k=3 → Output: [3,3,5,5,6,7]

Approach:

• Use deque to maintain indices of potential maxima
• Remove elements smaller than current from rear
• Remove out-of-window elements from front

Java Code:

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums == null || k <= 0) return new int[0];
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> dq = new ArrayDeque<>();
    
    for (int i = 0; i < n; i++) {
        // Remove out-of-window elements
        while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) {
            dq.pollFirst();
        }
        
        // Remove smaller elements from rear
        while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) {
            dq.pollLast();
        }
        
        dq.offerLast(i);
        if (i >= k - 1) {
            result[i - k + 1] = nums[dq.peekFirst()];
        }
    }
    return result;
}

TC: O(n), SC: O(k)

2. First Non-Repeating Character in Stream

Find first non-repeating character for each position in stream.

Example:
Input: "aabc" → Output: "a#bb"

Java Code:

public String firstNonRepeating(String stream) {
    int[] freq = new int[26];
    Queue<Character> q = new LinkedList<>();
    StringBuilder sb = new StringBuilder();
    
    for (char ch : stream.toCharArray()) {
        freq[ch - 'a']++;
        q.offer(ch);
        
        while (!q.isEmpty() && freq[q.peek() - 'a'] > 1) {
            q.poll();
        }
        
        sb.append(q.isEmpty() ? '#' : q.peek());
    }
    return sb.toString();
}

TC: O(n), SC: O(1) (fixed character set)

3. Rotten Oranges (BFS with Queue)

Calculate minimum time to rot all oranges.

Approach:

• Enqueue all rotten oranges with time=0
• Process neighbors (BFS), updating fresh oranges
• Check remaining fresh oranges

Java Code:

public int orangesRotting(int[][] grid) {
    int m = grid.length, n = grid[0].length;
    Queue<int[]> q = new LinkedList<>();
    int fresh = 0, time = 0;
    int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
    
    // Initialize queue and count fresh oranges
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            if (grid[i][j] == 2) q.offer(new int[]{i, j, 0});
            else if (grid[i][j] == 1) fresh++;
        }
    }
    
    // BFS processing
    while (!q.isEmpty()) {
        int[] cell = q.poll();
        time = Math.max(time, cell[2]);
        
        for (int[] d : dirs) {
            int x = cell[0] + d[0], y = cell[1] + d[1];
            if (x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1) {
                grid[x][y] = 2;
                fresh--;
                q.offer(new int[]{x, y, cell[2] + 1});
            }
        }
    }
    return fresh == 0 ? time : -1;
}

TC: O(mn), SC: O(mn)

4. Circular Queue Implementation

Fixed-size FIFO structure with efficient wraparound.

Java Code:

class MyCircularQueue {
    private int[] data;
    private int front, rear, size, capacity;
    
    public MyCircularQueue(int k) {
        data = new int[k];
        capacity = k;
        front = 0; rear = -1; size = 0;
    }
    
    public boolean enQueue(int val) {
        if (isFull()) return false;
        rear = (rear + 1) % capacity;
        data[rear] = val;
        size++;
        return true;
    }
    
    public boolean deQueue() {
        if (isEmpty()) return false;
        front = (front + 1) % capacity;
        size--;
        return true;
    }
    
    public int Front() {
        return isEmpty() ? -1 : data[front];
    }
    
    public int Rear() {
        return isEmpty() ? -1 : data[rear];
    }
    
    public boolean isEmpty() {
        return size == 0;
    }
    
    public boolean isFull() {
        return size == capacity;
    }
}

TC: O(1) all operations, SC: O(n)

5. Reverse a Queue

Reverse elements in a queue.

Java Code:

public void reverseQueue(Queue<Integer> q) {
    Stack<Integer> s = new Stack<>();
    while (!q.isEmpty()) s.push(q.poll());
    while (!s.isEmpty()) q.offer(s.pop());
}

TC: O(n), SC: O(n)

6. Generate Binary Numbers 1 to n

Generate binary numbers from 1 to n using queue.

Example:
n=3 → ["1", "10", "11"]

Java Code:

public List<String> generateBinary(int n) {
    Queue<String> q = new LinkedList<>();
    List<String> result = new ArrayList<>();
    q.offer("1");
    
    while (n-- > 0) {
        String s = q.poll();
        result.add(s);
        q.offer(s + "0");
        q.offer(s + "1");
    }
    return result;
}

TC: O(n), SC: O(n)

7. Implement Stack using Queues

LIFO using two queues.

Approach:

• Push: Add to q2, transfer all from q1 to q2, swap queues
• Pop: Remove from q1

Java Code:

class MyStack {
    private Queue<Integer> q1 = new LinkedList<>();
    private Queue<Integer> q2 = new LinkedList<>();
    
    public void push(int x) {
        q2.offer(x);
        while (!q1.isEmpty()) q2.offer(q1.poll());
        Queue<Integer> temp = q1;
        q1 = q2;
        q2 = temp;
    }
    
    public int pop() {
        return q1.poll();
    }
    
    public int top() {
        return q1.peek();
    }
    
    public boolean empty() {
        return q1.isEmpty();
    }
}

TC: Push O(n), Pop O(1), SC: O(n)

8. Implement Queue using Stacks

FIFO using two stacks.

Approach:

• Enqueue: Push to input stack
• Dequeue: If output stack empty, transfer all from input

Java Code:

class MyQueue {
    private Stack<Integer> in = new Stack<>();
    private Stack<Integer> out = new Stack<>();
    
    public void push(int x) {
        in.push(x);
    }
    
    public int pop() {
        if (out.isEmpty()) transfer();
        return out.pop();
    }
    
    public int peek() {
        if (out.isEmpty()) transfer();
        return out.peek();
    }
    
    private void transfer() {
        while (!in.isEmpty()) out.push(in.pop());
    }
    
    public boolean empty() {
        return in.isEmpty() && out.isEmpty();
    }
}

TC: Amortized O(1) for all operations, SC: O(n)

9. Priority Queue Patterns

a. Kth Largest Element

public int findKthLargest(int[] nums, int k) {
    PriorityQueue<Integer> pq = new PriorityQueue<>();
    for (int num : nums) {
        pq.offer(num);
        if (pq.size() > k) pq.poll();
    }
    return pq.peek();
}

TC: O(n log k), SC: O(k)

b. Merge K Sorted Lists

public ListNode mergeKLists(ListNode[] lists) {
    PriorityQueue<ListNode> pq = new PriorityQueue<>((a, b) -> a.val - b.val);
    for (ListNode node : lists) 
        if (node != null) pq.offer(node);
    
    ListNode dummy = new ListNode(0);
    ListNode curr = dummy;
    while (!pq.isEmpty()) {
        curr.next = pq.poll();
        curr = curr.next;
        if (curr.next != null) pq.offer(curr.next);
    }
    return dummy.next;
}

TC: O(n log k), SC: O(k)

Key Takeaways

• Queue Patterns: Sliding window, BFS, stream processing, reversal
• Operations: offer(), poll(), peek(), isEmpty()
• Variants: Circular queue, deque, priority queue
• Complexity: Most queue patterns run in O(n) time
• Applications: BFS, caching, buffering, scheduling