Applications

1static int shortestPath(int[][] g) {                     // 4-directional moves, 0 = wall
2    int R = g.length, C = g[0].length;
3    int[][] dist = new int[R][C]; for (int[] row : dist) Arrays.fill(row, -1);
4    Deque<int[]> queue = new ArrayDeque<>();
5    // single source: (0, 0); multi-source: every cell equal to 2, all at distance 0
6    dist[0][0] = 0; queue.offer(new int[]{0, 0});
7    while (!queue.isEmpty()) {
8        int[] cur = queue.poll();
9        for (int[] d : new int[][]{{-1, 0}, {0, 1}, {1, 0}, {0, -1}}) {
10            int r = cur[0] + d[0], c = cur[1] + d[1];
11            if (r < 0 || r >= R || c < 0 || c >= C || g[r][c] == 0 || dist[r][c] != -1) continue;
12            dist[r][c] = dist[cur[0]][cur[1]] + 1;           // first arrival is the shortest, because BFS goes level by level
13            queue.offer(new int[]{r, c});
14        }
15    }
16    return dist[R - 1][C - 1];                               // -1 when unreachable; multi-source: max over all cells
17}

1Comparator<Integer> cmp = Comparator.naturalOrder();   // Comparator.reverseOrder() makes a max-queue
2PriorityQueue<Integer> pq = new PriorityQueue<>(cmp);
3pq.offer(x);              // append at the end, then sift up
4Integer top = pq.poll();  // last element to the root, then sift down
5Integer next = pq.peek(); // the root only; nothing is removed

1class RingQueue {
2    private final int[] data; private int head, tail, size;
3    RingQueue(int capacity) { data = new int[capacity]; }
4    boolean offer(int x) {
5        if (size == data.length) return false;              // full
6        data[tail] = x;
7        tail = (tail + 1) % data.length;                   // wrap around
8        size++; return true;
9    }
10    Integer poll() {
11        if (size == 0) return null;                         // empty
12        int x = data[head];
13        head = (head + 1) % data.length;                   // wrap around
14        size--; return x;
15    }
16}

1class BoundedQueue {
2    private final ArrayDeque<Integer> q = new ArrayDeque<>(); private final int capacity;
3    boolean offer(int x) {
4        if (q.size() == capacity) return false;          // overflow: reject
5        q.addLast(x); return true;                       // join at the rear
6    }
7    Integer poll() {
8        return q.pollFirst();                            // front leaves first; null when empty
9    }
10    Integer peek() { return q.peekFirst(); }            // front, not removed
11}

1class RecentCounter {
2    private final Deque<Integer> q = new ArrayDeque<>(); private final int window;
3    RecentCounter(int window) { this.window = window; }
4    int ping(int t) {
5        q.addLast(t);
6        while (q.peekFirst() < t - window) q.pollFirst();     // too old to count
7        return q.size();
8    }
9}

1static int[] roundRobin(int[] burst, int quantum) {          // returns each process's finish time
2    int n = burst.length, time = 0; int[] left = burst.clone(), finish = new int[n];
3    Queue<Integer> ready = new ArrayDeque<>();
4    for (int i = 0; i < n; i++) ready.offer(i);
5    while (!ready.isEmpty()) {
6        int p = ready.poll();
7        int run = Math.min(quantum, left[p]);
8        time += run; left[p] -= run;
9        if (left[p] > 0) ready.offer(p);                      // not done: back of the line
10        else finish[p] = time;
11    }
12    return finish;
13}