Sets, queues and stacks

Intermediate

Introduction

Lists and maps are not the whole toolbox. Sometimes the question is "have I seen this before?", which is a job for a set. Sometimes items must be handled in the order they arrived, like customers in a queue, or the most recent first, like the undo history of an editor. Java's queues and stacks do exactly that, and a priority queue always hands out the most urgent item.

How it works

A set holds each value at most once. add returns false when the value is already there, and contains is fast:

Set<String> seen = new HashSet<>();
if (!seen.add(name)) System.out.println("duplicate: " + name);

HashSet has no order, TreeSet keeps its items sorted, and LinkedHashSet keeps them in the order first added. Sets support the classic operations through methods: addAll (union), retainAll (intersection) and removeAll (difference).

A queue processes items first in, first out. ArrayDeque is the usual implementation: offer adds at the back, poll removes from the front (returning null when empty), and peek looks at the front without removing it. Breadth-first searches, print queues and task lists all use queues.

A stack processes items last in, first out. ArrayDeque is also the recommended stack: push, pop and peek work at the top. (The old Stack class still exists but is slower and not recommended.) Undo histories, bracket matching and depth-first searches use stacks.

A PriorityQueue always gives back the smallest item first, whatever the order they were added in. Give it a comparator for a different order: new PriorityQueue<>((a, b) -> b - a) hands out the largest first. Its toString does not show the items in priority order; only poll does.

For your own classes, sets and map keys rely on equals and hashCode to decide whether two objects are the same. Records generate both automatically; ordinary classes must override them together, or two equal-looking objects will both be kept.

Example

import java.util.*;

public class Main {
    public static void main(String[] args) {
        String[] visits = {"rina", "arif", "rina", "zoya", "arif"};

        Set<String> unique = new HashSet<>(Arrays.asList(visits));
        Set<String> sorted = new TreeSet<>(unique);
        Set<String> firstSeen = new LinkedHashSet<>(Arrays.asList(visits));
        System.out.println(unique.size() + " " + sorted + " " + firstSeen);

        Queue<String> line = new ArrayDeque<>();   // first in, first out
        line.offer("first");
        line.offer("second");
        System.out.println(line.poll() + " then " + line.peek());

        Deque<Integer> stack = new ArrayDeque<>(); // last in, first out
        stack.push(1);
        stack.push(2);
        System.out.println(stack.pop() + " " + stack.pop());

        PriorityQueue<Integer> pq = new PriorityQueue<>(List.of(5, 1, 4));
        System.out.println(pq.poll() + " " + pq.poll());
    }
}
Open in compiler

Line by line

  1. The HashSet keeps three distinct names; the TreeSet sorts them; the LinkedHashSet keeps first-seen order.
  2. The queue hands out "first" before "second", and peek shows the next one without removing it.
  3. The stack hands out 2 before 1: last in, first out.
  4. The priority queue hands out 1, then 4, the smallest first.

Expected result

3 [arif, rina, zoya] [rina, arif, zoya]
first then second
2 1
1 4

In the real world

Web crawlers keep a set of visited pages and a queue of pages to visit. Operating systems schedule tasks with priority queues, compilers check brackets with stacks, and analytics code counts distinct users with sets.

Common mistakes

  • Using a List for membership checks on large data, which is slow; use a Set.
  • Expecting a PriorityQueue to print in order; only polling returns items in order.
  • Using Stack or Vector in new code instead of ArrayDeque.
  • Putting objects without equals and hashCode in a HashSet, so duplicates are not recognised.

Best practices

  • Choose the collection by the question: order, uniqueness, lookup by key, or processing order.
  • Use offer, poll and peek, which return null on an empty queue instead of throwing.
  • Use records, or override equals and hashCode together, for objects in sets and map keys.

Summary

Sets hold unique items: HashSet unordered, TreeSet sorted, LinkedHashSet in first-seen order. ArrayDeque serves as a queue (offer, poll, peek) and as a stack (push, pop, peek), and PriorityQueue always hands out the smallest or most urgent item. Sets and map keys use equals and hashCode to recognise equal objects.

Quick check

1. What does set.add(x) return when x is already in the set?
2. Which order does a queue follow?
3. Which class is recommended for a stack in new Java code?
4. A PriorityQueue holds 5, 1 and 4. What does poll() return first?

Key takeaways

  • HashSet removes duplicates quickly; TreeSet sorts; LinkedHashSet keeps first-seen order.
  • ArrayDeque is the standard queue (offer, poll) and stack (push, pop).
  • PriorityQueue returns items by priority, not by insertion order.

Practice problems for this lesson

My notes

Write down what you want to remember from this lesson. Notes are saved on this device as you type, and appear on your dashboard.