Queues & Deques

10 cards, about a minute. Read them the night before an interview, or right after the chapter to lock it in.

1. ◆what it is

   A queue is FIFO: offer at the rear, poll from the front — whoever waited longest leaves first. A deque opens both ends.

   #1
2. ↯use it when

   "In arrival order", BFS / fewest steps, "in the last X seconds", rotation games, and the max or min of every window.

   #2
3. { }template

   Deque<Integer> q = new ArrayDeque<>(); → offer, poll, peek, isEmpty. The same object is a stack with push/pop/peek.

   #3
4. O( )cost

   offer / poll / peek: O(1) (amortized when ArrayDeque grows). ArrayList.remove(0) is O(n), so n dequeues become O(n²).

   #4
5. { }template

   Ring buffer: head + size. Next free = (head + size) % k, rear = (head + size − 1) % k, dequeue = head = (head + 1) % k.

   #5
6. !trap

   head == tail means both empty and full — keep a size. Stepping left? (head − 1 + k) % k, because Java's % can be negative.

   #6
7. !trap

   Monotonic deque: store indices, not values — otherwise you can't tell when the front has left the window.

   #7
8. O( )cost

   Monotonic deque and two-stack queue: each element goes in once and comes out at most once → O(n) total, amortized O(1) each.

   #8
9. ✦pro tip

   Time window with growing timestamps? Offer the new one, poll expired ones from the front; the answer is the size.

   #9
10. !trap

    poll() on an empty queue returns null — int x = q.poll(); then throws. And ArrayDeque refuses null elements.

    #10

Shaky on a card? Open the chapter or flip its recall cards.