Queues

If you've ever stood in line at a bubble tea shop, you already understand a queue. That's basically the whole idea — but in code, this simple concept turns into one of the most useful data structures you'll meet. In this post we'll walk through what a queue is, how to implement one in Java, and then level it up into a priority queue.

This is written for someone seeing it for the first time, so I won't assume much beyond "you've written a few Java classes."

1. The mental model

Picture a checkout line at the supermarket:

  front                                 rear
   ↓                                     ↓
 [ A ] ← [ B ] ← [ C ] ← [ D ] ← (new person joins here)
   ↑
 (cashier serves whoever is here next)

Two rules govern this line:

• New people join at the rear.
• The cashier always serves whoever is at the front. That's it. That's a queue. And the rule it follows has a famous three-letter name: FIFO — First In, First Out. The first person in line is the first person out.

Compare this to a stack, which is LIFO (Last In, First Out) — like a stack of plates where you only take the top one. Same family of "linear" structures, different access rule.

2. Where queues live in Java

Before we build one, let's see where Queue sits in Java's official Collections Framework:

                  Iterable
                     │
                 Collection
                ┌────┼─────┐
              List   Queue   Set
               │      │       │
        ArrayList   PriorityQueue   HashSet
        LinkedList     Deque       LinkedHashSet
        Vector       ArrayDeque    TreeSet
        Stack

A few takeaways:

• Queue is a sibling of List and Set — they're all Collections.
• Queue is an interface, not a concrete class. You don't new Queue(). You use an implementation like LinkedList or PriorityQueue.
• Deque (double-ended queue) is a more flexible cousin that allows add/remove at both ends. We won't focus on it here.

3. The two operations that define a queue

You only really need two:

You'll often also see helpers like peek() (look at the front without removing), size(), and isEmpty(). But enqueue and dequeue are the heart of it.

Try it yourself

I built a tiny visualizer — type a value, hit ENQUEUE, watch it appear at the rear. Hit DEQUEUE to pull from the front. The borders highlight which node is the front (red) and which is the rear (blue).

4. Implementing a queue: why a linked list wins

Here's a subtle but important question: should I use an ArrayList or a LinkedList under the hood?

Let's think about what each operation costs.

With an ArrayList:

• enqueue (add at end) → cheap, just appends. ✅
• dequeue (remove from index 0) → ⚠️ expensive! Every other element has to shift left by one. That's an O(n) hit on every removal. With a LinkedList:
• enqueue (add at tail) → O(1). ✅
• dequeue (remove from head) → O(1). ✅ Both queue operations are constant-time with a linked list. That's why the textbook recommends a linked list as the backing structure for a queue.

   Queue conceptually          Queue implemented as a LinkedList
 
   ┌───┬───┬───┐                ┌───┐   ┌───┐   ┌───┐
   │ A │ B │ C │                │ A │ → │ B │ → │ C │
   └───┴───┴───┘                └───┘   └───┘   └───┘
    front     rear                first           last
                                  (dequeue        (enqueue
                                   from here)      to here)

5. Two ways to wire a GenericQueue to a LinkedList

Once you've decided to use a linked list, you still have a design choice. Java's textbook author Y. Daniel Liang lays out two paths.

Option A: Inheritance — GenericQueue extends LinkedList

Your queue is-a linked list, and inherits all of its methods.

• ✅ Easy to write.
• ❌ But… your queue now exposes every LinkedList method (like add(int index, E e), get(i), etc.). That breaks the queue's contract — users can sneakily insert in the middle, peek at index 5, all sorts of things a real queue shouldn't allow.

Option B: Composition — GenericQueue has-a LinkedList

Your queue owns a private linked list and only exposes enqueue, dequeue, getSize.

• ✅ Encapsulates the implementation. The user can only do queue things.
• ✅ You could swap the internal LinkedList for something else later without breaking callers.
• This is the preferred design.

   (a) Inheritance                    (b) Composition
 
   LinkedList ◁──── GenericQueue      GenericQueue ◆──── LinkedList
                                       (holds one privately)

Rule of thumb: Prefer composition over inheritance unless your subclass is genuinely a more specific kind of the parent. A queue isn't a "kind of linked list" — it's a different abstraction that happens to use one internally.

6. GenericQueue<E> — the code

Here's the textbook implementation using composition. It's short enough to memorize:

public class GenericQueue<E> {
    private java.util.LinkedList<E> list = new java.util.LinkedList<>();
 
    public void enqueue(E e) {
        list.addLast(e);          // add at rear
    }
 
    public E dequeue() {
        return list.removeFirst(); // remove from front
    }
 
    public int getSize() {
        return list.size();
    }
 
    @Override
    public String toString() {
        return "Queue: " + list.toString();
    }
}

A few things worth noticing:

• <E> is a generic type parameter. It lets you build GenericQueue<String>, GenericQueue<Integer>, or GenericQueue<MyOwnClass> from the same definition.
• addLast and removeFirst are methods Java's LinkedList already provides. We're just renaming them to the queue vocabulary.
• The internal list is private — outside code can't reach in and break invariants.

Testing it

GenericQueue<String> queue = new GenericQueue<>();
 
queue.enqueue("Tom");          // Queue: [Tom]
queue.enqueue("Susan");        // Queue: [Tom, Susan]
queue.enqueue("Kim");
queue.enqueue("Michael");      // Queue: [Tom, Susan, Kim, Michael]
 
System.out.println(queue.dequeue()); // Tom
System.out.println(queue.dequeue()); // Susan
System.out.println(queue);           // Queue: [Kim, Michael]

Notice how Tom — the first one in — is also the first one out. FIFO in action.

7. Priority Queues — when FIFO isn't enough

Now imagine an emergency room.

A patient with a stab wound arrives at 10:00 AM. A patient with a sprained ankle arrives at 10:05 AM. Should the ankle be treated first because they arrived first? Of course not.

That's the limitation of a plain queue: it doesn't care how important an element is. In real life, sometimes you need to jump the line.

Priority Queue: A queue where each element has a priority, and the highest-priority element comes out first — regardless of insertion order.

Some people call this "largest-in, first-out" behavior, though as you'll see, "largest" can mean either biggest number or smallest number depending on how you set it up.

Visualizing it

Here's the classic textbook picture: elements are dumped into a container with priorities, and removal always pulls out the highest-priority one. With 8, 3, 18, 15, 13 in the bowl (higher number = higher priority), 18 leaves first.

(Try toggling the "higher = higher priority" / "lower = higher priority" mode at the top — same data, different winner.)

8. Java's built-in PriorityQueue

Good news: Java ships one. You don't have to build it yourself.

import java.util.PriorityQueue;

It implements the Queue<E> interface, so the method names look familiar:

A note on naming: offer / poll / peek are the queue-aware versions that return null or false instead of throwing on edge cases (empty queue, capacity full). The older add / remove exist too but can throw exceptions. Prefer the new names.

How does it know what "highest priority" means?

Two ways:

1. Natural ordering. If your elements implement Comparable<E>, PriorityQueue uses that. For String, natural order is alphabetical, so "Georgia" comes out before "Texas".
2. Custom Comparator. Pass one to the constructor and you control the order.

9. Example 1 — strings, two orderings

import java.util.*;
 
public class PriorityQueueDemo {
  public static void main(String[] args) {
    // Default: natural ordering (alphabetical for Strings)
    PriorityQueue<String> queue1 = new PriorityQueue<>();
    queue1.offer("Oklahoma");
    queue1.offer("Indiana");
    queue1.offer("Georgia");
    queue1.offer("Texas");
 
    System.out.println("Priority queue using Comparable:");
    while (queue1.size() > 0) {
      System.out.print(queue1.poll() + " ");
    }
    // → Georgia Indiana Oklahoma Texas
 
    // Reversed order via Collections.reverseOrder()
    PriorityQueue<String> queue2 =
        new PriorityQueue<>(4, Collections.reverseOrder());
    queue2.offer("Oklahoma");
    queue2.offer("Indiana");
    queue2.offer("Georgia");
    queue2.offer("Texas");
 
    System.out.println("\nPriority queue using Comparator:");
    while (queue2.size() > 0) {
      System.out.print(queue2.poll() + " ");
    }
    // → Texas Oklahoma Indiana Georgia
  }
}

Same elements, opposite outputs — just by swapping in Collections.reverseOrder().

10. Example 2 — your own objects

What if you want to queue something Java doesn't know how to compare? Like a Customer?

You have to teach it. Implement Comparable<Customer> and define compareTo:

public class Customer implements Comparable<Customer> {
  private Integer id;
  private String name;
 
  public Customer(Integer id, String name) {
    this.id = id;
    this.name = name;
  }
 
  public Integer getID() { return id; }
  public String  getName() { return name; }
 
  @Override
  public int compareTo(Customer c) {
    return this.getID().compareTo(c.getID());
  }
 
  @Override
  public String toString() {
    return "Customer [id=" + id + ", name=" + name + "]";
  }
}

Now you can drop Customer objects into a PriorityQueue and it'll know what to do:

PriorityQueue<Customer> customerQueue =
    new PriorityQueue<>(Collections.reverseOrder());
 
customerQueue.add(new Customer(3, "Donald"));
customerQueue.add(new Customer(1, "Chong"));
customerQueue.add(new Customer(2, "Ali"));
customerQueue.add(new Customer(4, "Bala"));
 
Customer c = customerQueue.peek();
if (c != null) {
  System.out.println(c.getName() + " is in the queue");
  while ((c = customerQueue.poll()) != null) {
    System.out.println(c);
  }
}

Output:

Bala is in the queue
Customer [id=4, name=Bala]
Customer [id=3, name=Donald]
Customer [id=2, name=Ali]
Customer [id=1, name=Chong]

Because we used reverseOrder(), the biggest id wins. Bala (id=4) is the VIP.

compareTo cheat sheet:

• Returns negative → this is "less than" other
• Returns zero → equal priority
• Returns positive → this is "greater than" other

By default, "greater" = "later out". Reverse it with a Comparator if you want the largest first.

11. Quick check — can you answer these?

Before moving on, see if you can answer these without scrolling back up.

1. Where in a queue do you insert? Where do you delete?
2. What does FIFO stand for?
3. Why is a LinkedList a better choice than an ArrayList to implement a queue?
4. What are the two preferred methods to add and remove in java.util.PriorityQueue (the ones that don't throw)?
5. If you put 5, 1, 8, 3 into a default PriorityQueue<Integer> and call poll() four times, what comes out and in what order?

Answers

1. Insert at the rear (back/tail). Delete from the front (head).
2. First In, First Out.
3. Removing from the front of an ArrayList is O(n) because every other element has to shift. With a doubly-linked list, head removal is O(1).
4. offer(e) to add, poll() to remove.
5. 1, 3, 5, 8 — natural ordering for Integer is ascending, so smallest comes out first.

12. Exercise — build your own

Want a workout? Try implementing a queue using an array instead of a linked list. Call it ArrayQueue<E>. You'll need to think about:

• Two index pointers — one for the front, one for the rear.
• What happens when rear reaches the end of the array? (Hint: a circular array wraps rear back to 0.)
• How and when to resize() when the array fills up. Sketch of the API:

public class ArrayQueue<E> {
    public ArrayQueue();
    public ArrayQueue(int initialCapacity);
    public void enqueue(E e);
    public E    dequeue();
    public E    getElement();   // peek
    public boolean isEmpty();
    public int  size();
    private void resize();      // grow when full
}

This is a classic interview-style exercise. You learn a lot by getting the circular-array bookkeeping right.

13. Where to go next

Queues show up everywhere once you start looking — task schedulers, BFS in graph algorithms, print spoolers, message brokers, request handling in web servers. Priority queues power Dijkstra's shortest-path algorithm and A* search. The simple FIFO idea is doing a lot of work behind the scenes in real systems.

Coming up next in this series: trees — the structure that makes priority queues fast under the hood (via something called a binary heap), and a whole lot more.