Lesson 10.1 · Queue, Deque and Monotonic Queue

Queues: First In, First Out

Add at the back with offer, remove from the front with poll, look with peek. All O(1) with ArrayDeque.

10 min

Think of it like this

The line at a railway ticket counter: people join at the back and are served from the front, in the order they arrived. Nobody skips ahead.

1.Queue operations in Java

Queue<Integer> q = new ArrayDeque<>(). offer(x) adds to the back, poll() removes from the front (returning null if empty), peek() reads the front. Prefer these over add/remove/element, which throw exceptions when the queue is full or empty.

ArrayDeque is a circular array underneath, so all these are O(1) amortised. LinkedList also implements Queue, but allocates a node per element.

QueueDemo.java

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

public class Main {
    public static void main(String[] args) {
        Queue<String> line = new ArrayDeque<>();
        line.offer("Meera");
        line.offer("Arjun");
        line.offer("Priya");
        System.out.println(line.poll());   // served first
        System.out.println(line.peek());   // next in line
        System.out.println(line);
    }
}

Output

Meera
Arjun
[Arjun, Priya]

2.Queues as simulations

Many problems describe a process: people buying tickets, tasks taking turns, cards being dealt. Simulating it with a queue is often the clearest first solution. Then ask whether a formula can skip the simulation.

Remember

FIFO: first in, first out.
offer / poll / peek, all O(1).
Use ArrayDeque; avoid LinkedList for queues of numbers.

Common mistakes

Using list.remove(0) on an ArrayList as a queue (O(n) per removal).
Calling poll() and unboxing a null from an empty queue.

Command Palette

Queues: First In, First Out

1.Queue operations in Java

2.Queues as simulations