Queues in Java

Mon, Jan 23, 2023 2-minute read

A queue data structure works in a similar way to a real-life queue at a supermarket or bank. Items/people get added to the back of the queue and removed from the front. They call this system “First In, First Out” (FIFO) to compare it to a stack (think stack of papers) where the last thing that gets put on is the first thing to get taken off and the thing at the bottom of the stack stays on until the very end.

In some cases, like a supermarket checkout, you do want to keep the order of the queue so a normal queue is ok.

  private Queue<Patient> waitingRoom = new ArrayDeque<Patient>();

What about the scenario where the order people enter the queue isn’t necessarily the order you want to pull them out? Like a hospital emergency room? In this case, you wouldn’t want someone having a heart attack to be seen after someone with a stubbed toe, even if they arrived after. This is where a Priority Queue comes in.

In a PriorityQueue, you tell the queue what to sort the items by when you create it, and it will give you the highest priority patient when you ask. Interestingly, it doesn’t actually store the items in order (probably to save computation time), but when you poll()??, it will give you the most urgent patient. Good to have.

import java.util.*;

class Patient implements Comparable<Patient> {
    String name;
    int priority;

    public Patient(String name, int priority) {
        this.name = name;
        this.priority = priority;
    }

    public int compareTo(Patient other) {
        return this.name.compareTo(other.name);
    }

    public String toString() {
        return this.name;
    }

    public int getPri() {
        return this.priority;
    }
}

class Hospital {
    public static void main(String[] args) {
        Patient andy = new Patient("Andy", 2);
        Patient bob = new Patient("Bob", 3);
        Patient charlie = new Patient("Charlie",1);

        System.out.println(andy.compareTo(bob)); // -1
        System.out.println(andy.compareTo(charlie)); // -2

        Queue<Patient> pq = new PriorityQueue<Patient>((Patient p1, Patient p2) -> {
            if (p1.getPri() < p2.getPri()) {
                return -1;
            } else if (p1.getPri() > p2.getPri()) {
                return 1;
            } else {
                return 0;
            }
        });

        pq.add(andy);
        pq.add(bob);
        pq.add(charlie);

        System.out.println(pq.poll()); // Charlie
        System.out.println(pq.poll()); // Andy
        System.out.println(pq.poll()); // Bob
        System.out.println(pq.poll()); // null
        System.out.println(pq.poll()); // null
    }
}