Historical Context & Motivation
Long before computers existed, people were already using the idea of a queue every single day. Think about a line at the school cafeteria: the first person to arrive is the first person served. This first-in, first-out (FIFO) pattern turns out to be one of the most important ideas in computer science. Early programmers needed a way to manage tasks that should be handled in the exact order they arrive — from print jobs to network requests. Java's collections framework gives us clean, built-in tools to implement this pattern.
LinkedList class as part of the original java.util package, providing a doubly-linked list implementation.List and reorganizing collection classes under a unified hierarchy.Queue interface to the collections framework. LinkedList was updated to implement it, giving developers a standard FIFO contract.The central question this lesson addresses is straightforward: how do you store and retrieve elements in Java so that the first item you add is always the first item you remove? The Queue interface and the LinkedList class work together to solve exactly this problem.
Core Principles & Definitions
Before diving into code, you need to understand four foundational ideas that make Java's Queue and LinkedList work. Each of these concepts builds on the previous one, so take them in order.
FIFO Principle
Interface vs. Implementation
offer, poll, peek). LinkedList is one concrete class that implements it.Linked Nodes
Program to the Interface
Queue<T> rather than LinkedList<T>. This keeps your code flexible — you can swap in a different Queue implementation later without changing the rest of your program.offer() is like pulling into the lane, poll() is like getting your food and driving away, and peek() is like checking who's at the front window without actually serving them.Visual Explanation — How a Queue Works
The diagram below shows the internal structure of a LinkedList being used as a Queue. Each box represents a node that holds a value and a reference (pointer) to the next node. New elements enter at the tail, and elements are removed from the head.
poll() removes elements, and the tail (back) is where offer() adds them. The dashed box shows a new element about to be linked.Notice how the linked structure makes FIFO operations efficient. When you call offer("Eve"), the list simply creates a new node and attaches it after the current tail — no shifting of existing elements is required. When you call poll(), the list removes the head node and updates the head pointer to the next node. Both operations happen in constant time, regardless of how many elements are in the queue.
How It Works — The Queue API
The Queue interface in Java defines two styles of methods for each operation: one that throws an exception when something goes wrong, and one that returns a special value (like null or false). For most high school projects, the "special value" versions are more convenient because they avoid messy exception handling.
| Operation | Throws Exception | Returns Special Value | Description |
|---|---|---|---|
| Insert | add(e) | offer(e) | Adds element to the tail of the queue |
| Remove | remove() | poll() | Removes and returns the head element |
| Examine | element() | peek() | Returns the head element without removing it |
Declaring a Queue with LinkedList
Here is the standard way to create a queue in Java. Notice the left side uses the interface type and the right side uses the implementation type:
Queue<String> — the interface type (what operations are available). new LinkedList<>() — the concrete class that provides the actual storage. The <String> is a generic type parameter telling Java this queue holds String objects.The Three Core Operations
true if the element was added. For a LinkedList-backed queue, this always succeeds because LinkedList is unbounded.null instead of throwing an exception.Detailed Breakdown — Queue Operations Step by Step
Let's trace through a complete sequence of queue operations to see exactly how the state changes. The diagram below shows a step-by-step timeline of a queue being built up and then consumed. Each row represents one operation, and the colored boxes show the queue's state after that operation completes.
offer) add elements to the tail. Pink steps (poll) remove from the head. Yellow (peek) inspects without modifying. Notice how A is always removed before B, and B before C — that's FIFO.poll() or peek() on an empty queue returns null. Always check for null or use isEmpty() before processing the result — otherwise you'll hit a NullPointerException later in your code.Worked Example — Customer Service Simulation
Let's build a small program that simulates a customer-service queue. Three customers join the line, and they're served one by one. We'll walk through every line of code.
Queue<String> to program to the interface:
import java.util.LinkedList;
import java.util.Queue;
Queue<String> customers = new LinkedList<>();[]offer() to add three customers. Each call places the new customer at the tail of the queue.
customers.offer("Maya"); // [Maya]
customers.offer("Raj"); // [Maya, Raj]
customers.offer("Zoe"); // [Maya, Raj, Zoe][Maya, Raj, Zoe]System.out.println("Next: " + customers.peek());
This prints Next: Maya — the queue is unchanged.Next: Maya | Queue unchangedwhile loop to serve all customers. The loop continues as long as poll() returns a non-null value:
String current;
while ((current = customers.poll()) != null) {
System.out.println("Serving: " + current);
}Serving: Maya → Serving: Raj → Serving: Zoe (FIFO confirmed!)System.out.println(customers.isEmpty()); // true
System.out.println(customers.peek()); // nullisEmpty() returns true; peek() returns nullQueue vs. Stack vs. ArrayList — When to Use What
Java gives you several data structures for storing collections of objects. Choosing the right one depends on the order in which you need to access elements. The table below compares three common options so you can decide which fits your problem.
| Feature | Queue (LinkedList) | Stack | ArrayList |
|---|---|---|---|
| Access Order | FIFO — first in, first out | LIFO — last in, first out | Random — access by index |
| Add Operation | offer() — O(1) | push() — O(1) | add() — O(1) amortized |
| Remove Operation | poll() — O(1) | pop() — O(1) | remove(0) — O(n) |
| Best Use Case | Task scheduling, BFS, print queues | Undo operations, DFS, expression parsing | Frequent lookups by position, sorting |
| Null-safe remove? | Yes — poll() returns null | No — pop() throws exception | No — throws exception |
Queue. If you need LIFO order (like an undo button), use a Deque as a stack. If you need to jump to any position by index, use ArrayList. Don't try to use an ArrayList as a queue — removing from the front is O(n) because every other element has to shift over, like everyone in a movie theater moving down one seat.Connection to Advanced Queues
The basic Queue interface you've learned is just the starting point. Java provides several more specialized queue types that you'll encounter as you move into AP Computer Science A and beyond. Understanding the basic Queue interface gives you a solid foundation for all of them.
| Basic Queue | Advanced Queue Type | Key Difference |
|---|---|---|
Queue<E> | Deque<E> | Double-ended queue — add/remove from both ends. Can act as a queue or a stack. |
Queue<E> | PriorityQueue<E> | Elements are served by priority (smallest first), not by arrival order. |
Queue<E> | BlockingQueue<E> | Thread-safe queue for multi-threaded programs. Waits when empty or full. |
LinkedList | ArrayDeque | Faster than LinkedList for most queue operations because it uses a resizable array internally. |
In particular, ArrayDeque is worth knowing about because Java's official documentation recommends it over LinkedList when you need a pure queue or stack. It avoids the memory overhead of creating a separate node object for every element. That said, LinkedList is still the most common choice in textbooks and AP exams, so mastering it first is the right move.
Practice Problems
poll() and peek(). If you called peek() three times in a row on a non-empty queue, would the return value change between calls? Why or why not?System.out.println output?
Queue<Integer> q = new LinkedList<>();
q.offer(10);
q.offer(20);
q.offer(30);
q.poll();
q.offer(40);
System.out.println(q.peek());reverseQueue that takes a Queue<String> and returns a new Queue<String> with the elements in reverse order. You may use any additional data structure. (Hint: which data structure naturally reverses order?)Queue<String> that accepts a new message and enforces this 5-message limit. Include the condition check.remove(0) to get FIFO behavior, so there's no reason to learn Queue." Write a paragraph explaining why this reasoning is flawed. Consider both performance and code design.Lesson Summary
The Queue interface defines a FIFO (first-in, first-out) contract with three key operations: offer() adds to the tail, poll() removes from the head (returning null if empty), and peek() inspects the head without removing it. The LinkedList class implements this interface using a doubly-linked node structure, giving both offer() and poll() O(1) time complexity.
Always program to the interface by declaring variables as Queue<T> rather than LinkedList<T>. This makes your code more readable (it signals FIFO intent), more flexible (you can swap implementations), and less error-prone (you won't accidentally use non-queue methods). Queues are foundational in computing — from task scheduling and print jobs to the Breadth-First Search algorithm you'll encounter in more advanced courses.