import java.util.ArrayDeque;
import java.util.Queue;

Queue<String> pending = new ArrayDeque<>();

pending.offer("Marta Ruiz");         // comes in
pending.offer("Diego Alonso");
pending.offer("Nuria Vidal");

System.out.println(pending.peek());       // Marta Ruiz  (looks without taking)
System.out.println(pending.poll());       // Marta Ruiz  (takes)
System.out.println(pending.poll());       // Diego Alonso
System.out.println(pending.size());       // 1

Queue<Reservation> queue = new ArrayDeque<>();

// A processing loop: the queue emptying is NORMAL, it is the stopping condition
Reservation r;
while ((r = queue.poll()) != null) {      // poll returns null: idiomatic and clean
    serve(r);
}

// A one-off query where empty WOULD BE a logic error
Reservation next = queue.remove();        // NoSuchElementException if it is empty

tail = (tail + 1) & (elements.length - 1);   // goes back to 0 when it passes the end

// As a QUEUE (FIFO): in at the back, out at the front
Deque<String> queue = new ArrayDeque<>();
queue.offerLast("Marta Ruiz");
queue.offerLast("Diego Alonso");
System.out.println(queue.pollFirst());    // Marta Ruiz

// As a STACK (LIFO): in and out at the same end
Deque<String> stack = new ArrayDeque<>();
stack.push("registration");
stack.push("withdrawal");
System.out.println(stack.pop());          // withdrawal  (the last one in)

// As a real DEQUE: both ends
Deque<String> both = new ArrayDeque<>();
both.offerFirst("urgent");                // jumps to the front
both.offerLast("normal");                 // waits its turn at the back
System.out.println(both.pollFirst());     // urgent

import java.util.PriorityQueue;
import java.util.Queue;

// By natural order: the SMALLEST comes out first
Queue<Integer> queue = new PriorityQueue<>();
queue.offer(30);
queue.offer(10);
queue.offer(20);

System.out.println(queue.poll());   // 10
System.out.println(queue.poll());   // 20
System.out.println(queue.poll());   // 30

// The loans with the MOST days overdue first
Queue<Loan> notices = new PriorityQueue<>(
    Comparator.comparingInt((Loan l) -> l.daysLate(currentDay)).reversed());

// The most urgent reservations first and, on a tie, the oldest
Queue<Reservation> reservations = new PriorityQueue<>(
    Comparator.comparingInt(Reservation::getPriority)
              .thenComparingInt(Reservation::getRequestDay));

Queue<Integer> queue = new PriorityQueue<>();
queue.offer(30);
queue.offer(10);
queue.offer(20);
queue.offer(5);

System.out.println(queue);             // [5, 10, 20, 30] or [5, 10, 20, 30]... it depends

for (int n : queue) {
    System.out.print(n + " ");         // 5 10 20 30  ... or NOT
}

Queue<Integer> queue = new PriorityQueue<>();
for (int n : new int[]{ 50, 40, 30, 20, 10 }) { queue.offer(n); }

System.out.println("toString: " + queue);       // [10, 20, 40, 50, 30]  <- NOT sorted
System.out.print("iterator: ");
queue.forEach(n -> System.out.print(n + " "));  // 10 20 40 50 30
System.out.print("\npoll:     ");
while (!queue.isEmpty()) { System.out.print(queue.poll() + " "); }   // 10 20 30 40 50

while (!queue.isEmpty()) {
    Loan l = queue.poll();         // in guaranteed priority order
    process(l);
}
// ...but the queue is left empty

Queue<Loan> copy = new PriorityQueue<>(queue);   // copies the heap
while (!copy.isEmpty()) {
    process(copy.poll());
}
// the original queue is left intact

List<Loan> sorted = new ArrayList<>(queue);
sorted.sort(queue.comparator());         // the same criterion as the queue

Deque<String> lastOperations = new ArrayDeque<>();

void log(String operation) {
    lastOperations.offerLast(operation);
    if (lastOperations.size() > 100) {
        lastOperations.pollFirst();          // O(1): discards the oldest
    }
}

Queue<Runnable> tasks = new ArrayDeque<>();
tasks.offer(() -> System.out.println("Calculate fines"));
tasks.offer(() -> System.out.println("Send notices"));
tasks.offer(() -> System.out.println("Generate report"));

Runnable task;
while ((task = tasks.poll()) != null) {
    task.run();           // they run in order of arrival
}

package com.nexussoftware.bibliotech.service;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class Recommender {

    /** Graph: reference -> related references. */
    private final Map<String, List<String>> related;

    public Recommender(Map<String, List<String>> related) {
        this.related = related;
    }

    /**
     * Breadth-first traversal: returns the references reachable from 'origin'
     * up to 'maxDepth' hops away, in order of CLOSENESS.
     */
    public List<String> recommend(String origin, int maxDepth) {
        List<String> result = new ArrayList<>();
        Set<String>  visited = new HashSet<>();
        Deque<String> toVisit = new ArrayDeque<>();
        Deque<Integer> depths = new ArrayDeque<>();

        toVisit.offerLast(origin);
        depths.offerLast(0);
        visited.add(origin);

        while (!toVisit.isEmpty()) {
            String current = toVisit.pollFirst();            // FIFO: level by level
            int depth = depths.pollFirst();

            if (depth > 0) { result.add(current); }          // the origin is not recommended
            if (depth >= maxDepth) { continue; }

            for (String neighbour : related.getOrDefault(current, List.of())) {
                if (visited.add(neighbour)) {    // add returns false if it was there (05-06)
                    toVisit.offerLast(neighbour);
                    depths.offerLast(depth + 1);
                }
            }
        }
        return result;
    }
}

Map<String, List<String>> graph = Map.of(
    "978-0000000001", List.of("978-0000000002", "978-0000000003"),   // Effective Java
    "978-0000000002", List.of("978-0000000003", "DVD-0007"),         // Design Patterns
    "978-0000000003", List.of("DVD-0007"),                           // Refactoring
    "DVD-0007",       List.of("REV-2024-03")
);

Recommender r = new Recommender(graph);
System.out.println(r.recommend("978-0000000001", 1));    // direct neighbours
System.out.println(r.recommend("978-0000000001", 3));    // up to 3 hops, by closeness

[978-0000000002, 978-0000000003]
[978-0000000002, 978-0000000003, DVD-0007, REV-2024-03]

package com.nexussoftware.bibliotech.service;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import com.nexussoftware.bibliotech.domain.Employee;
import com.nexussoftware.bibliotech.domain.Material;
import com.nexussoftware.bibliotech.domain.Reservation;

/**
 * FIFO queue of reservations for ONE material, on top of ArrayDeque.
 *
 * Compared with the LinkedList version of 05-04: the same O(1) at the ends,
 * but with a circular array instead of nodes -> less memory, better cache
 * locality and no pressure at all on the collector.
 */
public class ReservationQueue {

    private final Material material;
    private final Deque<Reservation> pending = new ArrayDeque<>();

    public ReservationQueue(Material material) {
        this.material = material;
    }

    /** Enqueue at the back: amortised O(1). */
    public void reserve(Employee employee, int day) {
        pending.offerLast(new Reservation(employee, material, day));
    }

    /** An urgent reservation: it jumps to the front. Only a Deque allows this. */
    public void reserveUrgent(Employee employee, int day) {
        pending.offerFirst(new Reservation(employee, material, day, 1));
    }

    /** peekFirst: null if there is nobody. It never throws an exception. */
    public Reservation next() {
        return pending.peekFirst();
    }

    /** pollFirst: serves and removes. O(1). */
    public Reservation serveNext(int day) {
        Reservation r = pending.pollFirst();
        if (r != null) {
            r.markFulfilled();
            material.lend();
        }
        return r;
    }

    /** Cancels an employee's most recent reservation, walking from the back. */
    public boolean cancelLatestOf(Employee employee) {
        Iterator<Reservation> it = pending.descendingIterator();
        while (it.hasNext()) {
            if (it.next().getEmployee().equals(employee)) {
                it.remove();
                return true;
            }
        }
        return false;
    }

    /** Expires the reservations that have been waiting too long. */
    public int expire(int currentDay, int maxDays) {
        int before = pending.size();
        pending.removeIf(r -> r.daysWaiting(currentDay) > maxDays);
        return before - pending.size();
    }

    /** Position in the queue (1 = next up). 0 if there is no reservation. */
    public int positionOf(Employee employee) {
        int position = 1;
        for (Reservation r : pending) {     // a Deque has NO get(i): always for-each
            if (r.getEmployee().equals(employee)) { return position; }
            position++;
        }
        return 0;
    }

    public List<Reservation> list() { return new ArrayList<>(pending); }
    public int     waiting()        { return pending.size(); }
    public boolean hasPending()     { return !pending.isEmpty(); }
}

package com.nexussoftware.bibliotech.service;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;
import com.nexussoftware.bibliotech.domain.Severity;
import com.nexussoftware.bibliotech.domain.Loan;

/** Due-date notices served by urgency, not by order of arrival. */
public class NoticeQueue {

    private final Queue<Loan> notices;
    private final int currentDay;

    public NoticeQueue(int currentDay) {
        this.currentDay = currentDay;
        // Most days overdue first; on a tie, the oldest loan.
        // The tie-breaker makes the order DETERMINISTIC: without it, two loans
        // with the same delay would come out in arbitrary order.
        this.notices = new PriorityQueue<>(
            Comparator.comparingInt((Loan l) -> daysLate(l)).reversed()
                      .thenComparingInt(Loan::getLoanDay));
    }

    private int daysLate(Loan l) {
        return l.getMaterial().calculateDaysLate(currentDay - l.getLoanDay());
    }

    /** Enqueues only what is really overdue. O(log n). */
    public void enqueue(Loan l) {
        if (l != null && !l.isReturned() && l.isOverdue(currentDay)) {
            notices.offer(l);
        }
    }

    public void enqueueAll(List<Loan> loans) {
        for (Loan l : loans) { enqueue(l); }
    }

    /** The most urgent one, without taking it out. O(1). */
    public Loan mostUrgent() {
        return notices.peek();
    }

    /**
     * Processes ALL the notices in order of urgency.
     *
     * IMPORTANT: the queue has to be emptied with poll(). Walking it with a
     * for-each or printing its toString() would give the internal heap's order,
     * which is NOT the priority order.
     */
    public int processAll() {
        int processed = 0;
        Loan l;
        while ((l = notices.poll()) != null) {     // the idiom from section 2
            int late = daysLate(l);
            Severity s = l.getMaterial().classifySeverity(currentDay - l.getLoanDay());
            System.out.printf("[%-10s] %-16s %-24s %3d days  %6.2f EUR%n",
                    s, l.getEmployee().getName(), l.getMaterial().getTitle(),
                    late, l.calculateFine(currentDay));
            processed++;
        }
        return processed;
    }

    /** The N most urgent ones, WITHOUT emptying the queue: we work on a copy. */
    public List<Loan> topUrgent(int howMany) {
        Queue<Loan> copy = new PriorityQueue<>(notices);   // copies the heap
        List<Loan> result = new ArrayList<>();
        for (int i = 0; i < howMany && !copy.isEmpty(); i++) {
            result.add(copy.poll());
        }
        return result;
    }

    public int pending() { return notices.size(); }
}

Employee marta = new Employee("Marta Ruiz",   "EMP-001");
Employee diego = new Employee("Diego Alonso", "EMP-002");
Employee nuria = new Employee("Nuria Vidal",  "EMP-003");

Material effectiveJava = new Book("Effective Java", "Joshua Bloch", "978-0000000001", 2018);

// --- Reservation queue (FIFO) ---
effectiveJava.lend();
ReservationQueue reservations = new ReservationQueue(effectiveJava);
reservations.reserve(marta, 100);
reservations.reserve(diego, 101);
reservations.reserveUrgent(nuria, 102);      // jumps to the front

System.out.println("Next: " + reservations.next().getEmployee().getName());
System.out.println("Position of Marta: " + reservations.positionOf(marta));

// --- Notice queue (by priority) ---
List<Loan> loans = List.of(
    new Loan(new Book("Effective Java",  "Joshua Bloch",  "978-0000000001", 2018), marta, 100),
    new Loan(new Magazine("Java Magazine", "REV-2024-03", 42, "Monthly"),          diego, 120),
    new Loan(new Dvd("Refactoring Live", "DVD-0007",      95),                     nuria, 125),
    new Loan(new Book("Design Patterns", "Erich Gamma",   "978-0000000002", 1994), diego, 110)
);

NoticeQueue notices = new NoticeQueue(140);
notices.enqueueAll(loans);
System.out.println("\nPending notices: " + notices.pending());
System.out.println("Most urgent: " + notices.mostUrgent().getMaterial().getTitle());
System.out.println("\n--- Processing by urgency ---");
notices.processAll();

Next: Nuria Vidal
Position of Marta: 2

Pending notices: 4
Most urgent: Java Magazine

--- Processing by urgency ---
[SEVERE    ] Diego Alonso     Java Magazine             13 days    1.30 EUR
[SEVERE    ] Nuria Vidal      Refactoring Live          12 days    6.00 EUR
[SEVERE    ] Marta Ruiz       Effective Java            25 days    6.25 EUR
[SEVERE    ] Diego Alonso     Design Patterns           15 days    3.75 EUR

package com.nexussoftware.bibliotech.service;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.Iterator;
import java.util.List;
import com.nexussoftware.bibliotech.domain.Employee;

/** Waiting room at the loans desk. */
public class WaitingRoom {

    private final Deque<Employee> queue = new ArrayDeque<>();

    /** Amortised O(1): write at 'tail' and increment it. */
    public void arrive(Employee e) {
        if (e != null) { queue.offerLast(e); }
    }

    /**
     * O(1): write at 'head-1' and decrement it (the array is CIRCULAR,
     * so 'head' can wrap around to the end of the array).
     * With an ArrayList this would be add(0, e): O(n).
     */
    public void arrivePriority(Employee e) {
        if (e != null) { queue.offerFirst(e); }
    }

    /** O(1). pollFirst returns null if it is empty; removeFirst would throw. */
    public Employee serve() {
        return queue.pollFirst();
    }

    /** O(1). */
    public Employee next() {
        return queue.peekFirst();
    }

    /**
     * O(n): the queue has to be walked looking for the employee. It is the only
     * expensive operation in this class, and it is acceptable because leaving
     * from the middle of the queue is exceptional.
     */
    public boolean leave(Employee e) {
        return queue.removeFirstOccurrence(e);   // uses equals (03-09)
    }

    /** O(n). A Deque has no get(i): the position is only known by walking. */
    public int positionOf(Employee e) {
        int position = 1;
        for (Employee current : queue) {
            if (current.equals(e)) { return position; }
            position++;
        }
        return 0;
    }

    /** O(n). descendingIterator walks from 'tail' to 'head'. */
    public List<Employee> reverseOrder() {
        List<Employee> result = new ArrayList<>(queue.size());
        Iterator<Employee> it = queue.descendingIterator();
        while (it.hasNext()) { result.add(it.next()); }
        return result;
    }

    /** Empties the queue serving in order. The standard idiom with poll. */
    public void closeDesk() {
        System.out.println("--- Closing the desk: " + queue.size() + " waiting ---");
        Employee e;
        int turn = 1;
        while ((e = queue.pollFirst()) != null) {
            System.out.printf("  Turn %d: %s (%s)%n",
                              turn++, e.getName(), e.getIdentifier());
        }
        System.out.println("--- Desk closed ---");
    }

    public int     waiting() { return queue.size(); }
    public boolean isEmpty() { return queue.isEmpty(); }
}

Employee marta = new Employee("Marta Ruiz",   "EMP-001");
Employee diego = new Employee("Diego Alonso", "EMP-002");
Employee nuria = new Employee("Nuria Vidal",  "EMP-003");

WaitingRoom room = new WaitingRoom();
room.arrive(marta);
room.arrive(diego);
room.arrivePriority(nuria);             // jumps to the front

System.out.println("Next: " + room.next().getName());                  // Nuria Vidal
System.out.println("Position of Marta: " + room.positionOf(marta));    // 2
System.out.println("Diego leaves: " + room.leave(diego));              // true
room.closeDesk();

Next: Nuria Vidal
Position of Marta: 2
Diego leaves: true
--- Closing the desk: 2 waiting ---
  Turn 1: Nuria Vidal (EMP-003)
  Turn 2: Marta Ruiz (EMP-001)
--- Desk closed ---

package com.nexussoftware.bibliotech.service;

import java.util.ArrayList;
import java.util.Comparator;
import java.util.List;
import java.util.PriorityQueue;
import java.util.Queue;

/** A catalogue maintenance task. Priority 1 = maximum urgency. */
record MaintenanceTask(String description, int priority, int creationDay) {
    MaintenanceTask {
        if (description == null || description.isBlank()) { description = "(no description)"; }
        if (priority < 1 || priority > 10) { priority = 5; }
        if (creationDay < 0) { creationDay = 0; }
    }
}

public class TaskScheduler {

    private final Queue<MaintenanceTask> queue;

    public TaskScheduler() {
        // Lowest priority number first. On a tie, the oldest.
        // The tie-breaker makes the order DETERMINISTIC and also fair: between two
        // equal urgencies, the one that has waited longest wins.
        this.queue = new PriorityQueue<>(
            Comparator.comparingInt(MaintenanceTask::priority)
                      .thenComparingInt(MaintenanceTask::creationDay));
    }

    /** O(log n): the element floats up through the heap. */
    public void schedule(MaintenanceTask t) {
        if (t != null) { queue.offer(t); }
    }

    /** O(1): the root of the heap. */
    public MaintenanceTask next() {
        return queue.peek();
    }

    /** O(log n): takes the root out and reorganises. */
    public MaintenanceTask execute() {
        return queue.poll();
    }

    /**
     * The next N WITHOUT emptying the original queue.
     * PriorityQueue's copy constructor duplicates the heap.
     */
    public List<MaintenanceTask> upcoming(int howMany) {
        Queue<MaintenanceTask> copy = new PriorityQueue<>(queue);
        List<MaintenanceTask> result = new ArrayList<>();
        for (int i = 0; i < howMany && !copy.isEmpty(); i++) {
            result.add(copy.poll());
        }
        return result;
    }

    public int executeAll() {
        int n = 0;
        MaintenanceTask t;
        while ((t = queue.poll()) != null) {
            System.out.printf("  [P%d] day %3d  %s%n", t.priority(), t.creationDay(),
                              t.description());
            n++;
        }
        return n;
    }

    /** Shows that only poll() respects the priority order. */
    public void demoUnorderedIterator() {
        System.out.println("=== The iterator does NOT traverse in priority order ===");

        System.out.println("toString():");
        System.out.println("  " + queue);

        System.out.print("for-each:  ");
        for (MaintenanceTask t : queue) { System.out.print("P" + t.priority() + " "); }
        System.out.println();

        System.out.print("forEach:   ");
        queue.forEach(t -> System.out.print("P" + t.priority() + " "));
        System.out.println();

        System.out.print("poll:      ");
        Queue<MaintenanceTask> copy = new PriorityQueue<>(queue);
        MaintenanceTask t;
        while ((t = copy.poll()) != null) { System.out.print("P" + t.priority() + " "); }
        System.out.println("   <- the ONLY guaranteed order");

        System.out.println("Cause: the internal array only satisfies the heap property");
        System.out.println("(each node <= its children), not a total order.");
    }

    public int pending() { return queue.size(); }
}

TaskScheduler p = new TaskScheduler();
p.schedule(new MaintenanceTask("Check damaged copies",  5, 100));
p.schedule(new MaintenanceTask("Replace damaged DVD",   1, 130));
p.schedule(new MaintenanceTask("Annual inventory",      8, 90));
p.schedule(new MaintenanceTask("Fix incorrect ISBNs",   1, 110));
p.schedule(new MaintenanceTask("Clean shelves",         5, 95));

System.out.println("Next: " + p.next().description());
System.out.println("Next 2: ");
p.upcoming(2).forEach(t -> System.out.println("  " + t.description()));
System.out.println("Pending after querying: " + p.pending());

p.demoUnorderedIterator();
System.out.println("\n--- Executing all ---");
p.executeAll();

Next: Fix incorrect ISBNs
Next 2:
  Fix incorrect ISBNs
  Replace damaged DVD
Pending after querying: 5

=== The iterator does NOT traverse in priority order ===
toString():
  [MaintenanceTask[...priority=1, creationDay=110], ...]
for-each:  P1 P1 P8 P5 P5
forEach:   P1 P1 P8 P5 P5
poll:      P1 P1 P5 P5 P8    <- the ONLY guaranteed order
...
--- Executing all ---
  [P1] day 110  Fix incorrect ISBNs
  [P1] day 130  Replace damaged DVD
  [P5] day  95  Clean shelves
  [P5] day 100  Check damaged copies
  [P8] day  90  Annual inventory

package com.nexussoftware.bibliotech.service;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Deque;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

public class RecommenderComparison {

    private final Map<String, List<String>> related;

    public RecommenderComparison(Map<String, List<String>> related) {
        this.related = related;
    }

    /**
     * BREADTH (BFS): a FIFO queue. It explores by LEVELS: first all the
     * direct neighbours, then the neighbours of those, and so on.
     */
    public List<String> breadthFirst(String origin, int maxDepth) {
        return traverse(origin, maxDepth, true);
    }

    /**
     * DEPTH (DFS): a LIFO stack. It goes as far as it can down one branch
     * before backtracking. SAME code, only the end it takes from changes.
     */
    public List<String> depthFirst(String origin, int maxDepth) {
        return traverse(origin, maxDepth, false);
    }

    private List<String> traverse(String origin, int maxDepth, boolean breadth) {
        List<String>   result  = new ArrayList<>();
        Set<String>    visited = new HashSet<>();
        Deque<String>  toVisit = new ArrayDeque<>();
        Deque<Integer> depths  = new ArrayDeque<>();

        toVisit.offerLast(origin);
        depths.offerLast(0);
        visited.add(origin);

        while (!toVisit.isEmpty()) {
            // THE ONLY DIFFERENCE between BFS and DFS is on this line:
            //   pollFirst -> FIFO -> breadth
            //   pollLast  -> LIFO -> depth
            String current = breadth ? toVisit.pollFirst() : toVisit.pollLast();
            int depth = breadth ? depths.pollFirst() : depths.pollLast();

            if (depth > 0) { result.add(current); }
            if (depth >= maxDepth) { continue; }

            for (String neighbour : related.getOrDefault(current, List.of())) {
                if (visited.add(neighbour)) {     // add returns false if it was there (05-06)
                    toVisit.offerLast(neighbour);
                    depths.offerLast(depth + 1);
                }
            }
        }
        return result;
    }

    public static void main(String[] args) {
        Map<String, List<String>> graph = Map.of(
            "978-0000000001", List.of("978-0000000002", "DVD-0007"),
            "978-0000000002", List.of("978-0000000003"),
            "978-0000000003", List.of("REV-2024-03"),
            "DVD-0007",       List.of("REV-2024-03")
        );

        RecommenderComparison r = new RecommenderComparison(graph);
        System.out.println("BREADTH (BFS): " + r.breadthFirst("978-0000000001", 3));
        System.out.println("DEPTH (DFS):   " + r.depthFirst("978-0000000001", 3));
    }
}

BREADTH (BFS): [978-0000000002, DVD-0007, 978-0000000003, REV-2024-03]
DEPTH (DFS):   [DVD-0007, REV-2024-03, 978-0000000002, 978-0000000003]