Stacks, Queues, Deques, Backtracking & Trees for Placements

By FreePare Team · Wed Aug 19 2026 · 10 min read

Lab 3 of the 75-problem placement system

This is the third of four labs. It assumes Lab 1's foundations and the pattern gates in Lab 2, and is followed by Lab 4 on binary-search-tree invariants, heaps and graph representations.

A stack, queue, or deque is not just storage. It is a claim about which item becomes available next. Recursion is also a storage policy: the runtime keeps unfinished calls for you. Tree algorithms combine both ideas, which is why a one-character boundary error or a vague return contract can corrupt an otherwise familiar solution.

This lab turns those hidden policies into invariants you can trace.

Learning contract

You will be able to:

• select LIFO, FIFO, or both-end access from the problem's ordering rule;
• implement parsing, BFS, monotonic-stack, and window-deque patterns;
• define backtracking state, choices, constraints, undo, termination, and pruning;
• write recursive and iterative tree traversals with explicit contracts;
• test empty and skewed structures, not only balanced examples;
• pass a three-part exit lab at 80% or higher.

Java 25 is the primary language. ArrayDeque supports stack and queue use without the legacy synchronization and API shape of Stack. Its API does not permit null elements, which keeps null available as an absence signal for some operations.

The NIST Dictionary of Algorithms and Data Structures provides a neutral reference for traversal and data-structure terminology used in this lab.

Entry check

1. What unfinished obligation does a bracket parser push?

2. Why is FIFO order necessary for unweighted shortest-path BFS?

3. What does a decreasing monotonic stack represent?

4. In a window deque, do you store values or indices, and why?

5. What must be restored after a backtracking branch?

6. What does a tree-height function return for an empty tree?

7. Why can recursive DFS fail on a valid skewed tree?

8. Which test distinguishes tree-node identity from duplicate values?

Fewer than six correct: work in order. Six or more: start with the counterexamples, then take the exit lab.

1. Stack: unfinished work in reverse order

Balanced delimiters

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

static boolean balanced(String text) {
    Deque<Character> openings = new ArrayDeque<>();

    for (int i = 0; i < text.length(); i++) {
        char symbol = text.charAt(i);
        switch (symbol) {
            case '(', '[', '{' -> openings.push(symbol);
            case ')' -> {
                if (openings.isEmpty() || openings.pop() != '(') return false;
            }
            case ']' -> {
                if (openings.isEmpty() || openings.pop() != '[') return false;
            }
            case '}' -> {
                if (openings.isEmpty() || openings.pop() != '{') return false;
            }
            default -> { /* ignored by this contract */ }
        }
    }
    return openings.isEmpty();
}

Invariant: the stack contains exactly the unmatched opening delimiters in encounter order, with the most recent on top. A closing delimiter must discharge the most recent compatible obligation.

Counterexamples: ")" tests empty-stack protection, "([)]" tests nesting, and "((" tests unfinished obligations at end-of-input.

Monotonic stack

For each value, find the next strictly greater value to its right:

import java.util.Arrays;

static int[] nextGreater(int[] values) {
    int[] answer = new int[values.length];
    Arrays.fill(answer, -1);
    Deque<Integer> stack = new ArrayDeque<>(); // unresolved indices

    for (int i = 0; i < values.length; i++) {
        while (!stack.isEmpty() && values[stack.peek()] < values[i]) {
            answer[stack.pop()] = values[i];
        }
        stack.push(i);
    }
    return answer;
}

The stack's values are decreasing from bottom to top. Each index is pushed once and popped at most once, so total time is Theta(n) even though a while loop appears inside a for loop.

Duplicate policy matters. The strict < means an equal value is not "greater." Change the comparison only if the requirement changes.

2. Queue and deque: ordering the frontier

FIFO and BFS

In an unweighted graph, BFS discovers vertices by nondecreasing edge distance because every vertex at distance d leaves the queue before any newly discovered vertex at distance d + 1.

static int[] distances(java.util.List<java.util.List<Integer>> graph, int source) {
    int[] distance = new int[graph.size()];
    java.util.Arrays.fill(distance, -1);
    Deque<Integer> queue = new ArrayDeque<>();

    distance[source] = 0;
    queue.addLast(source);

    while (!queue.isEmpty()) {
        int node = queue.removeFirst();
        for (int next : graph.get(node)) {
            if (distance[next] == -1) {
                distance[next] = distance[node] + 1;
                queue.addLast(next);
            }
        }
    }
    return distance;
}

Mark on enqueue, not dequeue. Otherwise multiple parents can enqueue the same vertex and inflate work.

Sliding-window maximum

Store indices because the algorithm must know both value order and window membership.

static int[] windowMaximum(int[] values, int k) {
    if (k <= 0 || k > values.length) {
        throw new IllegalArgumentException("invalid window size");
    }

    int[] result = new int[values.length - k + 1];
    Deque<Integer> deque = new ArrayDeque<>();

    for (int i = 0; i < values.length; i++) {
        while (!deque.isEmpty() && deque.peekFirst() <= i - k) {
            deque.removeFirst();
        }
        while (!deque.isEmpty() && values[deque.peekLast()] <= values[i]) {
            deque.removeLast();
        }
        deque.addLast(i);

        if (i >= k - 1) {
            result[i - k + 1] = values[deque.peekFirst()];
        }
    }
    return result;
}

Two invariants hold:

1. every stored index belongs to the current window;

2. stored values decrease from front to back.

The common boundary bug is evicting with < i - k instead of <= i - k, which keeps one expired index. Test values = [9, 1, 1], k = 2.

Run that test, both ways

The two versions differ by one character, so nothing short of a trace settles it. With k = 2 the answer has two entries: the maximum of the window [9, 1] and the maximum of the window [1, 1].

Correct version, evicting with <= i - k:

Result: [9, 1], which is what the two windows contain.

Buggy version, evicting with < i - k. Only the last row changes:

Result: [9, 9]. The second window is [1, 1] and the function reports 9, because index 0 left the window and never left the deque. Notice what makes this bug survive review: 9 is a real value from the real input, so every output still looks plausible, and a test that only checks "each answer appears somewhere in the array" passes. The invariant is the thing that fails — every stored index belongs to the current window — and it is the thing to assert.

3. Backtracking: choose, recurse, undo

Backtracking is a depth-first search over decisions. Write six items before code:

State:
Choices:
Constraint:
Apply:
Undo:
Termination/output:

Unique permutations with duplicates

static java.util.List<java.util.List<Integer>> uniquePermutations(int[] values) {
    java.util.Arrays.sort(values);
    java.util.List<java.util.List<Integer>> result = new java.util.ArrayList<>();
    boolean[] used = new boolean[values.length];
    build(values, used, new java.util.ArrayList<>(), result);
    return result;
}

private static void build(
        int[] values,
        boolean[] used,
        java.util.List<Integer> path,
        java.util.List<java.util.List<Integer>> result) {
    if (path.size() == values.length) {
        result.add(java.util.List.copyOf(path));
        return;
    }

    for (int i = 0; i < values.length; i++) {
        if (used[i]) continue;
        if (i > 0 && values[i] == values[i - 1] && !used[i - 1]) continue;

        used[i] = true;
        path.add(values[i]);
        build(values, used, path, result);
        path.remove(path.size() - 1);
        used[i] = false;
    }
}

State: chosen indices and current path. Choice: one unused index. Constraint: skip equivalent sibling choices. Undo: remove the value and clear used[i].

The result copy is essential. Adding the mutable path itself would make every result refer to the same object.

Pruning must be proved safe

Pruning means rejecting a state only when no completion can satisfy the contract or improve the best known answer. "This branch looks bad" is not a proof.

For positive candidate values in a target-sum search, currentSum > target is safe pruning. If negative values are allowed, a later negative could repair the sum, so the same prune is unsound.

Backtracking time is often output-sensitive. If a problem asks for every valid arrangement, runtime cannot be smaller than the total size of the output it must construct.

4. Trees: define what each call returns

final class TreeNode {
    int value;
    TreeNode left;
    TreeNode right;

    TreeNode(int value) { this.value = value; }
}

Recursive and iterative DFS

Recursive inorder traversal:

static void inorder(TreeNode node, java.util.List<Integer> output) {
    if (node == null) return;
    inorder(node.left, output);
    output.add(node.value);
    inorder(node.right, output);
}

Iterative equivalent:

static java.util.List<Integer> inorderIterative(TreeNode root) {
    java.util.List<Integer> output = new java.util.ArrayList<>();
    Deque<TreeNode> stack = new ArrayDeque<>();
    TreeNode current = root;

    while (current != null || !stack.isEmpty()) {
        while (current != null) {
            stack.push(current);
            current = current.left;
        }
        current = stack.pop();
        output.add(current.value);
        current = current.right;
    }
    return output;
}

Both take Theta(n) time. Their active storage is Theta(h), where h is tree height. On a skewed tree, h = n; iterative traversal moves that storage to an explicit heap object and avoids depending on the runtime call-stack limit.

Level-order BFS

At the start of each outer iteration, capture the current queue size. Those nodes form exactly one level; children enqueued during the iteration belong to the next level.

Height and diameter

Choose a convention and keep it. Here, an empty tree has height 0, a leaf has height 1, and diameter is measured in nodes.

record TreeSummary(int height, int diameter) {}

static TreeSummary summarize(TreeNode node) {
    if (node == null) return new TreeSummary(0, 0);

    TreeSummary left = summarize(node.left);
    TreeSummary right = summarize(node.right);

    int height = 1 + Math.max(left.height(), right.height());
    int throughNode = 1 + left.height() + right.height();
    int diameter = Math.max(throughNode, Math.max(left.diameter(), right.diameter()));
    return new TreeSummary(height, diameter);
}

Return contract: each subtree reports both its height and best internal diameter. This avoids recomputing height at every node.

Serialization requires null markers

Pre-order values alone cannot distinguish all shapes. For example, a root with only a left child and a root with only a right child can produce the same value order. Add an explicit null marker and define escaping if values are textual.

Test empty tree, leaf, left chain, right chain, perfect tree, duplicate values, minimum/maximum values, and a tree deep enough to challenge recursion.

Problem batch: Q01-Q12

Exit lab

In 80 minutes:

1. solve one stack/deque task and state the ordering invariant;

2. solve one backtracking task with explicit undo and safe pruning;

3. solve one tree task twice: recursive and iterative or queue-based.

Each is scored out of 10 for selection, invariant/proof, code, edge tests, and time/space. Pass at 24/30, with no missing empty-structure test. Retry hint-assisted items after 2 and 7 days without prior code.

Next in this series: The Tree That Lied, which moves from the local invariants traced here to the ones a node inherits from an ancestor.

Tags: programming-fundamentals, coding-fundamentals, coding-interview-tips, dsa-guide, coding-practice, smart-study-tips, problem-solving-framework, student-learning-guide