Lesson 18Beginner47 minAssessment-backed

Queue and FIFO Thinking

Use first-in-first-out behavior for scheduling, buffering, event processing, rate control, and breadth-first traversal.

What you will be able to do

Explain queue behavior as first-in-first-out ordering.

Use queues for fair processing, buffering, BFS, and producer-consumer systems.

Implement queue workflows in Java, Python, and JavaScript.

Know when arrays with shift/front deletion are costly.

Describe backpressure, capacity, and retry risks in production queues.

A queue is the structure for work that should be handled in arrival order. If a stack models the latest unresolved work, a queue models fairness, buffering, scheduling, and breadth-first expansion.

The FIFO Mental Model

FIFO means first in, first out. Enqueue adds work to the back. Dequeue removes work from the front. The central question is whether older work should be processed before newer work.

Queue enqueue dequeue flow — Queues preserve arrival order. That makes them natural for fair scheduling and buffered processing.

Scenario: Background Job Processing

A product sends email receipts after checkout. The request path should not wait for the email provider. Instead, checkout enqueues a job, and workers dequeue jobs in order. If workers fall behind, the queue length becomes a product and operations signal.

Concern	Queue design question	Production implication
Fairness	Should old jobs run before new jobs?	FIFO prevents starvation for normal jobs.
Backpressure	What happens when producers are faster than consumers?	Queue length, latency, and memory grow.
Retries	Where do failed jobs go?	Need retry limits and dead-letter queues.
Priority	Are all jobs equal?	May need priority queue, not plain FIFO.

Producer consumer queue with workers and backpressure — Production queues are data structures plus operational policy: capacity, retries, visibility, and failure handling.

Same Pattern in Java, Python, and JavaScript

The following examples process tickets in arrival order. Java and Python have efficient deque types. JavaScript arrays can work for small queues, but repeated shift is costly for large queues, so a head index is safer.

import java.util.*;

class TicketQueue {
    static List<String> process(List<String> tickets) {
        Queue<String> queue = new ArrayDeque<>(tickets);
        List<String> result = new ArrayList<>();
        while (!queue.isEmpty()) {
            result.add(queue.remove());
        }
        return result;
    }
}

Where Queues Show Up

Background jobs and worker pools.
Breadth-first search and level-order traversal.
Rate-limited request buffers.
Streaming ingestion and message brokers.
Print queues, task schedulers, and retry pipelines.

Assessment trap

FIFO order is not the same as priority order. If the most urgent item must run first, you need a priority queue or scheduling policy.

Interview signalFrequently Asked Interview Questions

These are canonical interview patterns for this topic, phrased as concrete problem statements. They avoid vague theory questions and prepare you for the exact reasoning interviewers expect: invariant, edge cases, complexity, and trade-off.

Implement a FIFO queue using two LIFO stacks.
Process tickets in arrival order.
Find the shortest path length in an unweighted grid from start to target.

Production practiceCompany-Style Practice Examples

These are not claimed as exact company-specific questions. They are the interview patterns repeatedly used by product companies to test whether you can move from brute force to a defensible implementation.

Example	Brute-force approach	Stronger solution	Production notes
Queue using stacks	Use expensive front deletion.	Use two stacks to reverse order only when needed.	Amortized O(1) queue operations.
Shortest path in unweighted grid	DFS and hope first path is shortest.	Use BFS queue by layers.	FIFO preserves distance order.
Background jobs	Run side effects in request path.	Enqueue jobs and let workers consume.	Mention retries, backpressure, and dead-letter policy.

Solved modelInterview Question Solutions

Question 1: Queue Using Two Stacks

Implement a FIFO queue using two LIFO stacks. Push into an input stack. For dequeue/peek, move items to the output stack only when output is empty. Each item moves at most twice.

import java.util.*;

class MyQueue {
    private final Deque<Integer> in = new ArrayDeque<>();
    private final Deque<Integer> out = new ArrayDeque<>();
    void push(int x) { in.push(x); }
    int pop() { move(); return out.pop(); }
    int peek() { move(); return out.peek(); }
    boolean empty() { return in.isEmpty() && out.isEmpty(); }
    private void move() { while (out.isEmpty() && !in.isEmpty()) out.push(in.pop()); }
}

Question 2: FIFO Ticket Processing

Process tickets in arrival order. Use queue semantics. Avoid repeated front deletion for large JavaScript arrays by using a head index.

import java.util.*;

class Tickets {
    static List<String> process(List<String> tickets) {
        Queue<String> queue = new ArrayDeque<>(tickets);
        List<String> done = new ArrayList<>();
        while (!queue.isEmpty()) done.add(queue.remove());
        return done;
    }
}

Question 3: Unweighted Grid Shortest Path

Find the shortest path length in an unweighted grid from start to target. Use BFS with a queue because all edges have equal cost. The first time you reach the target is the shortest distance.

import java.util.*;

class GridBfs {
    static int shortest(int[][] grid) {
        int rows = grid.length, cols = grid[0].length;
        Queue<int[]> q = new ArrayDeque<>();
        q.add(new int[]{0,0,0}); grid[0][0] = 1;
        int[][] dirs = {{1,0},{-1,0},{0,1},{0,-1}};
        while (!q.isEmpty()) { int[] cur = q.remove(); if (cur[0] == rows - 1 && cur[1] == cols - 1) return cur[2]; for (int[] d : dirs) { int r = cur[0]+d[0], c = cur[1]+d[1]; if (r>=0&&c>=0&&r<rows&&c<cols&&grid[r][c]==0) { grid[r][c]=1; q.add(new int[]{r,c,cur[2]+1}); } } }
        return -1;
    }
}

Solved modelWorked Interview Answer

Process tickets in arrival order without costly front deletion. FIFO processing removes the oldest item first. For JavaScript arrays, a head index avoids repeated shifting for large queues.

import java.util.*;

class Tickets {
    static List<String> process(List<String> tickets) {
        Queue<String> queue = new ArrayDeque<>(tickets);
        List<String> done = new ArrayList<>();
        while (!queue.isEmpty()) done.add(queue.remove());
        return done;
    }
}

Hands-on drillTry It Yourself

Practice task

Model a checkout receipt email pipeline. Define enqueue, dequeue, retry, dead-letter, queue length, and backpressure behavior.

Failure patternsCommon Mistakes to Avoid

Using array front deletion repeatedly for large JavaScript queues.
Confusing FIFO with priority ordering.
Ignoring what happens when producers outpace consumers.
Retrying forever without dead-letter handling.

Execution guardrailQuick-Start Checklist

Define enqueue and dequeue ends.
Preserve arrival order unless priority is required.
Track capacity or queue length.
Define retry and failure policy.
State operation cost.

Recall drillKnowledge Check

Question	Strong answer
What does FIFO mean?	The earliest enqueued item is processed first.
Why is BFS queue-based?	It explores nodes in arrival/layer order.
What is backpressure?	A signal or limit when producers create work faster than consumers handle it.

VocabularyKey Terms

Term	Meaning
Enqueue	Add work to the back of a queue.
Dequeue	Remove work from the front.
Backpressure	Controlling producers when queues grow.
Dead-letter queue	A place for jobs that repeatedly fail.

Next practiceFurther Reading

Practice queue using stacks and BFS shortest path.
Review message queue reliability concepts.
Study priority queues later for urgent-first scheduling.

Stack and LIFO Thinking

Recursion and Call Stack