Stacks and Queues: Choosing the Right Structure

Stacks and queues are not just vocabulary words. They describe two different ways to control the order of work. A stack is useful when the newest unfinished task should be handled first. A queue is useful when the oldest waiting task should be handled first.

Stack example: balanced symbols

A stack is natural for checking parentheses because every closing symbol should match the most recent unmatched opening symbol.

public static boolean balanced(String text)
{
    Stack<Character> stack = new Stack<>();

    for (int i = 0; i < text.length(); i++)
    {
        char ch = text.charAt(i);

        if (ch == '(' || ch == '[')
        {
            stack.push(ch);
        }
        else if (ch == ')' || ch == ']')
        {
            if (stack.isEmpty())
                return false;

            char open = stack.pop();
            if (ch == ')' && open != '(')
                return false;
            if (ch == ']' && open != '[')
                return false;
        }
    }

    return stack.isEmpty();
}

The final stack.isEmpty() matters. A string like "(([]" never finds a wrong closing symbol, but it still has unmatched openings.

Queue example: breadth-first levels

A queue is natural when students need to process items in the order discovered. That is why breadth-first search uses a queue.

Queue<String> q = new LinkedList<>();
HashSet<String> visited = new HashSet<>();

q.add("A");
visited.add("A");

while (!q.isEmpty())
{
    String current = q.remove();

    for (String next : graph.get(current))
    {
        if (!visited.contains(next))
        {
            visited.add(next);
            q.add(next);
        }
    }
}

Marking a node visited when it is added to the queue prevents the same node from being enqueued multiple times by different neighbors.

How to choose

Problem phrase	Likely structure	Reason
Undo, most recent, backtracking	Stack	Newest item should be handled first.
Waiting line, arrival order, level by level	Queue	Oldest item should be handled first.
Shortest path by number of edges	Queue	BFS explores distance 1 before distance 2.

Practice prompt

Trace balanced("([()])") and balanced("([)]"). Then trace a queue on graph edges A-B, A-C, B-D, C-D starting at A.