Queue Data Structure — OutOfMemoryError from Unbounded

Every app you've ever used — from WhatsApp to YouTube to your office printer — relies on queues to stay organised. When you hit 'send' on a message, it doesn't teleport instantly; it joins a queue of outgoing messages waiting to be delivered in order. When your printer has three documents waiting, it prints them one by one, in the order you sent them. Queues are one of the most quietly important data structures in all of computer science, and once you see them, you'll spot them everywhere.

The problem queues solve is deceptively simple: how do you manage a collection of tasks or items where ORDER MATTERS and fairness is required? Without a queue, you'd have chaos — the last request might get processed first, messages could arrive out of order, and your printer might randomly decide to print your email before your boss's urgent contract. A queue enforces discipline: you wait your turn, and you get served in the order you arrived.

By the end of this article you'll understand exactly what a queue is and how it differs from other data structures, you'll be able to build a fully working queue in Java from scratch, and you'll know when to reach for a queue in your own projects. You'll also walk away with the gotchas that trip up beginners and the interview questions that catch people off guard.

Why Unbounded Queues Are a Latency Bomb

A queue is a linear data structure that processes elements in First-In-First-Out (FIFO) order. The core mechanic is simple: enqueue adds to the tail, dequeue removes from the head. Both operations are O(1) amortized in array-based implementations (e.g., ArrayDeque) and O(1) worst-case in linked-list variants (e.g., LinkedList).

In practice, the queue's contract guarantees ordering but says nothing about capacity. An unbounded queue grows without limit until memory is exhausted. This is the silent killer: producers can outpace consumers by any margin, and the queue will happily absorb the backlog until the JVM throws OutOfMemoryError. Bounded queues (e.g., ArrayBlockingQueue) enforce a fixed capacity, forcing backpressure onto producers via blocking or rejection policies.

Use a queue whenever you need to decouple producers from consumers — task executors, message brokers, event pipelines. The choice between bounded and unbounded is the single most impactful design decision. Bounded queues give you predictable memory and latency; unbounded queues trade safety for simplicity until they fail catastrophically.

Worked Example — Queue Operations and BFS Simulation

Simulate a print queue: enqueue 'doc1','doc2','doc3'. Queue: front→[doc1,doc2,doc3]←rear.

1. dequeue(): remove doc1. Queue: [doc2,doc3]. Print doc1.
2. enqueue('doc4'): Queue: [doc2,doc3,doc4].
3. dequeue(): remove doc2. Queue: [doc3,doc4]. Print doc2.

BFS traversal of graph {A:[B,C], B:[D], C:[D,E], D:[], E:[]} starting at A: 1. Enqueue A. visited={A}. Queue: [A]. 2. Dequeue A. Enqueue unvisited neighbors B,C. Queue: [B,C]. 3. Dequeue B. Enqueue D. Queue: [C,D]. 4. Dequeue C. Enqueue E (D already visited). Queue: [D,E]. 5. Dequeue D. No new neighbors. Queue: [E]. 6. Dequeue E. No new neighbors. Queue: []. Done. 7. BFS order: A,B,C,D,E.

Python deque (collections.deque) gives O(1) enqueue (append) and dequeue (popleft). A Python list would give O(n) dequeue because all elements shift.

How a Queue Works — Plain English and Operations

A queue is a First-In, First-Out (FIFO) data structure — the oldest item is removed first, like a line at a checkout.

Core operations (all O(1) with deque): 1. enqueue(x) / append: add x to the back. 2. dequeue() / popleft: remove and return the front element. 3. peek(): return the front element without removing. 4. is_empty(): True if no elements.

Always use collections.deque in Python (or ArrayDeque in Java) — list.pop(0) is O(n).

Worked example — BFS level-order on tree [1, children: 2,3; 2's children: 4,5]: Enqueue 1. queue=[1]. Dequeue 1. Level 0=[1]. Enqueue 2,3. queue=[2,3]. Dequeue 2. Level 1: 2. Enqueue 4,5. queue=[3,4,5]. Dequeue 3. Level 1: 3. No children. queue=[4,5]. Dequeue 4. Level 2: 4. queue=[5]. Dequeue 5. Level 2: 5. queue=[]. Result: [[1],[2,3],[4,5]].

What Is a Queue? The Core Concept Built from the Ground Up

A queue is a linear data structure — meaning items are arranged in a sequence, one after another, like beads on a string. What makes a queue special is its strict rule about where items enter and where they leave.

Items always join at the BACK (also called the 'rear' or 'tail'). Items always leave from the FRONT (also called the 'head'). That's it. That single rule — enter at the back, leave from the front — is what makes a queue a queue.

This behaviour has a name: FIFO, which stands for First In, First Out. The first item that joined the queue is the first item that gets to leave. Think of it as the universe enforcing fairness.

There are two core operations every queue must support: — ENQUEUE: adding an item to the back of the queue. — DEQUEUE: removing an item from the front of the queue.

There are also two supporting operations you'll use constantly: — PEEK (or FRONT): look at the item at the front without removing it, like craning your neck to see who's first in line. — IS EMPTY: check whether the queue has any items at all.

Notice what you CANNOT do with a true queue: you can't grab an item from the middle, you can't jump to the back, and you can't remove from the back. That restriction isn't a bug — it's the feature. It's what makes queues predictable and safe.

import java.util.LinkedList;
import java.util.Queue;

public class QueueConceptDemo {
    public static void main(String[] args) {

        // Java's built-in Queue interface, backed by a LinkedList.
        // Think of ticketQueue as the line at a cinema ticket counter.
        Queue<String> ticketQueue = new LinkedList<>();

        // ENQUEUE — people joining the back of the line
        ticketQueue.offer("Alice");   // Alice arrives first
        ticketQueue.offer("Bob");     // Bob arrives second
        ticketQueue.offer("Charlie"); // Charlie arrives third

        System.out.println("Queue after everyone joins: " + ticketQueue);
        // Output shows front-to-back order

        // PEEK — who is at the front WITHOUT removing them?
        String firstInLine = ticketQueue.peek();
        System.out.println("Who is at the front? " + firstInLine);
        System.out.println("Queue unchanged after peek: " + ticketQueue);

        // DEQUEUE — serving the person at the front
        String servedCustomer = ticketQueue.poll(); // removes and returns the front item
        System.out.println("Served: " + servedCustomer);
        System.out.println("Queue after serving: " + ticketQueue);

        // IS EMPTY — check before trying to serve
        System.out.println("Is the queue empty? " + ticketQueue.isEmpty());

        // Serve the remaining customers one by one
        while (!ticketQueue.isEmpty()) {
            System.out.println("Now serving: " + ticketQueue.poll());
        }

        System.out.println("Queue after all served: " + ticketQueue);
        System.out.println("Is the queue empty now? " + ticketQueue.isEmpty());
    }
}

Building a Queue from Scratch — So You Actually Understand What's Inside

Using Java's built-in Queue is fine for production code, but building one yourself is how you truly understand it. Let's build a queue using a simple array under the hood. This is the version interviewers love to ask about.

The key insight is that we need to track two positions: where the front of the queue is, and where the back of the queue is. We'll use two integer variables — frontIndex and rearIndex — as pointers.

When we enqueue an item, we place it at rearIndex and then move rearIndex forward by one. When we dequeue an item, we grab whatever is at frontIndex and then move frontIndex forward by one. The queue 'shrinks from the front' and 'grows from the back'.

There's a classic trap here: as you dequeue items, frontIndex creeps forward, and eventually you'll reach the end of the array even though there's empty space at the beginning (where old items used to be). The professional solution is a CIRCULAR QUEUE — when rearIndex hits the end of the array, it wraps around to index 0 and reuses that space. We'll implement that here, because that's the real, battle-tested version.

This implementation will also teach you about overflow (queue is full) and underflow (queue is empty) — two error conditions every queue must handle.

public class CircularArrayQueue {

    private String[] storage;   // the array holding our queue items
    private int frontIndex;     // points to the item at the front of the queue
    private int rearIndex;      // points to the next empty slot at the back
    private int currentSize;    // how many items are currently in the queue
    private int capacity;       // maximum number of items this queue can hold

    // Constructor — set up an empty queue with a fixed capacity
    public CircularArrayQueue(int capacity) {
        this.capacity = capacity;
        this.storage = new String[capacity];
        this.frontIndex = 0;
        this.rearIndex = 0;
        this.currentSize = 0;
        // All slots start as null (empty)
    }

    // ENQUEUE — add an item to the back of the queue
    public boolean enqueue(String item) {
        if (isFull()) {
            System.out.println("Queue is full! Cannot add: " + item);
            return false; // overflow condition — refuse gracefully
        }
        storage[rearIndex] = item; // place item at the current rear slot
        // The magic of circular: wrap rearIndex back to 0 when it hits the end
        rearIndex = (rearIndex + 1) % capacity;
        currentSize++;
        return true;
    }

    // DEQUEUE — remove and return the item at the front
    public String dequeue() {
        if (isEmpty()) {
            System.out.println("Queue is empty! Nothing to dequeue.");
            return null; // underflow condition — refuse gracefully
        }
        String itemAtFront = storage[frontIndex]; // grab the front item
        storage[frontIndex] = null;               // clear the slot (good practice)
        // Circular wrap: move frontIndex forward, wrapping if necessary
        frontIndex = (frontIndex + 1) % capacity;
        currentSize--;
        return itemAtFront;
    }

    // PEEK — see the front item without removing it
    public String peek() {
        if (isEmpty()) {
            return null;
        }
        return storage[frontIndex];
    }

    // IS EMPTY — true if there are no items in the queue
    public boolean isEmpty() {
        return currentSize == 0;
    }

    // IS FULL — true if the queue has reached its capacity
    public boolean isFull() {
        return currentSize == capacity;
    }

    // Helper to visualise the queue state during testing
    public void printQueue() {
        if (isEmpty()) {
            System.out.println("Queue: [empty]");
            return;
        }
        System.out.print("Queue (front to back): ");
        for (int i = 0; i < currentSize; i++) {
            // Use modulo to traverse circularly from frontIndex
            System.out.print("[" + storage[(frontIndex + i) % capacity] + "] ");
        }
        System.out.println();
    }

    // ── MAIN — test drive our hand-built queue ──────────────────────────────
    public static void main(String[] args) {

        CircularArrayQueue airportSecurityLine = new CircularArrayQueue(4);

        // Passengers joining the security line
        airportSecurityLine.enqueue("Passenger: Diana");
        airportSecurityLine.enqueue("Passenger: Edward");
        airportSecurityLine.enqueue("Passenger: Fatima");
        airportSecurityLine.enqueue("Passenger: George");
        airportSecurityLine.printQueue();

        // Try to add one more — queue is full
        airportSecurityLine.enqueue("Passenger: Hannah");

        // First two passengers go through security
        System.out.println("Cleared security: " + airportSecurityLine.dequeue());
        System.out.println("Cleared security: " + airportSecurityLine.dequeue());
        airportSecurityLine.printQueue();

        // Now there's room — Hannah can join
        airportSecurityLine.enqueue("Passenger: Hannah");
        System.out.println("Front of line right now: " + airportSecurityLine.peek());
        airportSecurityLine.printQueue();

        // Clear everyone out
        while (!airportSecurityLine.isEmpty()) {
            System.out.println("Cleared security: " + airportSecurityLine.dequeue());
        }

        // Try to dequeue from empty queue
        airportSecurityLine.dequeue();
    }
}

Where Queues Are Used in the Real World — The 'When Do I Use This?' Answer

Knowing what a queue is isn't enough. You need to know WHEN to reach for it. The pattern is always the same: use a queue whenever you have tasks or items that must be processed in the order they arrive, with no favouritism.

Here are the most common real-world uses:

PRINT SPOOLING: Your OS maintains a print queue. Documents get printed in the order they were sent. Nobody's report jumps the queue because they're the CEO (at least, not at the OS level).

CPU TASK SCHEDULING: Operating systems use queues to manage which processes get CPU time. Processes wait their turn in a ready queue.

BREADTH-FIRST SEARCH (BFS): This is huge in coding interviews. BFS uses a queue to explore a graph level by level — you visit all neighbours before going deeper. We'll touch on this in the interview questions section.

MESSAGE BROKERS: Systems like RabbitMQ and Apache Kafka are essentially industrial-strength queues. Your bank transaction, your Uber request, your food delivery notification — all queued.

WEB SERVER REQUEST HANDLING: When thousands of users hit a website at once, requests get queued and served in order so the server doesn't collapse.

The unifying pattern: tasks arrive at different times and speeds than they can be processed. A queue acts as the buffer in between — absorbing the bursts and feeding work through at a manageable rate.

import java.util.LinkedList;
import java.util.Queue;

public class PrintSpoolerSimulation {

    // Simulates a printer that can only print one document at a time
    static void simulatePrinter(Queue<String> printQueue) {
        System.out.println("=== Printer starting up ===");

        // Keep printing as long as there are documents waiting
        while (!printQueue.isEmpty()) {
            // poll() retrieves AND removes the front document
            String currentDocument = printQueue.poll();
            System.out.println("Printing: " + currentDocument);

            // Simulate the time it takes to print (just a message here)
            System.out.println("  → " + currentDocument + " complete. Next!");
        }

        System.out.println("=== Print queue empty. Printer idle. ===");
    }

    public static void main(String[] args) {

        // The office print queue — documents arrive in this order
        Queue<String> officePrintQueue = new LinkedList<>();

        // Three people send documents at roughly the same time
        officePrintQueue.offer("Alice's Expense Report.pdf");     // sent first
        officePrintQueue.offer("Bob's Project Proposal.docx");    // sent second
        officePrintQueue.offer("Charlie's Meeting Notes.txt");    // sent third

        System.out.println("Documents queued up: " + officePrintQueue);
        System.out.println("Total documents waiting: " + officePrintQueue.size());
        System.out.println();

        // Hand the queue off to the printer
        simulatePrinter(officePrintQueue);

        // Alice sends another document after the queue cleared
        System.out.println();
        officePrintQueue.offer("Alice's Quarterly Review.pdf");
        System.out.println("New document arrived: " + officePrintQueue.peek());
        simulatePrinter(officePrintQueue);
    }
}

Queue Overflow Is a Lie — Learn the Real Failure Modes of Bounded Queues

Every tutorial parrots "isFull()" like it's a quaint party check. In production, a bounded queue that reports full is already in a failure cascade. The real issue isn't the check — it's what you do when the queue says no. Block the producer and you stall upstream. Drop the message and you lose data. Resize and you invite latency spikes. The worst pattern I've seen is a silent retry loop: producer hammers isFull in a tight spin, pinning a core while the queue stays full. The fix is a backpressure strategy before you ever hit capacity. Choose: bounded blocking with a timeout, or a circuit breaker that drops the oldest entry (bounded discard). Never let isFull become a busy-wait. Know your queue's saturation point, monitor its depth, and decide the failure mode at design time, not during an outage.

// io.thecodeforge — dsa tutorial

import java.util.concurrent.ArrayBlockingQueue;
import java.util.concurrent.TimeUnit;

public class BoundedQueueWithBackpressure {
    private static final int QUEUE_CAPACITY = 100;
    private static final long OFFER_TIMEOUT_MS = 500;
    private final ArrayBlockingQueue<String> queue = new ArrayBlockingQueue<>(QUEUE_CAPACITY);

    public boolean tryEnqueue(String message) throws InterruptedException {
        // Block for at most 500ms instead of spinning on isFull()
        return queue.offer(message, OFFER_TIMEOUT_MS, TimeUnit.MILLISECONDS);
    }

    public String tryDequeue() throws InterruptedException {
        // Returns null after timeout, never blocks forever
        return queue.poll(100, TimeUnit.MILLISECONDS);
    }

    public static void main(String[] args) throws InterruptedException {
        BoundedQueueWithBackpressure bp = new BoundedQueueWithBackpressure();
        // Simulate producer — fails fast if queue stays full
        boolean enqueued = bp.tryEnqueue("payment_event_123");
        if (!enqueued) {
            System.err.println("Queue full, dropping message: payment_event_123");
            // Trigger alert, don't spin
        }

        String message = bp.tryDequeue();
        if (message == null) {
            System.out.println("No message within timeout, consumer idle");
        } else {
            System.out.println("Processed: " + message);
        }
    }
}

Peek Is Not Free — Stop Reading What You Don't Own

peek() looks like a harmless read — you just want to see the front without removing it. In a single-threaded toy, fine. In production, peek() is a footgun. Between the peek and the dequeue, another thread or process can snatch that front element. Now you're operating on stale or phantom data. Worse: if you peek then conditionally dequeue, you introduce TOCTOU (time-of-check time-of-use) bugs. Your log says you peeked a high-priority order, then dequeued a cancellation because the queue state changed. Production pattern: if you need to examine before consuming, use a peek-and-dequeue atomic operation (like a transaction) or redesign to not need that peek at all. The only legitimate use for peek is debugging or a peek-only consumer that never pops. Otherwise, dequeue directly and handle the result. Less code, fewer race conditions.

// io.thecodeforge — dsa tutorial

import java.util.concurrent.ConcurrentLinkedQueue;

public class PeekRaceConditionDemo {
    private final ConcurrentLinkedQueue<String> queue = new ConcurrentLinkedQueue<>();

    public static void main(String[] args) throws InterruptedException {
        PeekRaceConditionDemo demo = new PeekRaceConditionDemo();
        demo.queue.offer("order_001");
        demo.queue.offer("cancel_001");

        // Thread 1: peeks then sleeps, simulating slow consumer
        Thread t1 = new Thread(() -> {
            String front = demo.queue.peek(); // sees order_001
            System.out.println("Thread1 peeked: " + front);
            try { Thread.sleep(100); } catch (InterruptedException e) { }
            String removed = demo.queue.poll(); // might be cancel_001 now!
            System.out.println("Thread1 dequeued: " + removed);
        });

        // Thread 2: dequeues during the sleep
        Thread t2 = new Thread(() -> {
            String removed = demo.queue.poll(); // takes order_001
            System.out.println("Thread2 dequeued: " + removed);
        });

        t1.start();
        t2.start();
        t1.join();
        t2.join();
    }
}

Algorithm: BFS Without The Magic — Your Queue Is The Only Tool That Matters

Breadth-First Search looks like magic in textbooks. It's not. BFS is just a queue standing in line. Every node you visit gets enqueued. Every neighbor you find is a dequeue away. The algorithm has exactly one rule: first discovered, first processed. That's the queue contract.

Why does this matter in production? Because BFS isn't just for graphs. You're using it when you process work items in arrival order. When you handle rate-limited API calls in sequence. When your background job runner processes tasks in FIFO order. The queue isn't a data structure choice — it's the algorithm itself.

The trap: people forget BFS needs a visited set. Without it, your queue turns into an infinite loop machine. In Java, that visited set is a HashSet. In production, that set lives in Redis or a database. The queue is stateless — the visited state is what keeps you sane. Always separate the two.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class BfsQueue {
    public static void bfs(Map<Integer, List<Integer>> graph, int start) {
        Queue<Integer> q = new LinkedList<>();
        Set<Integer> visited = new HashSet<>();
        
        q.add(start);
        visited.add(start);
        
        while (!q.isEmpty()) {
            int node = q.poll();
            System.out.println("Visited: " + node);
            
            for (int neighbor : graph.getOrDefault(node, List.of())) {
                if (!visited.contains(neighbor)) {
                    visited.add(neighbor);
                    q.add(neighbor);
                }
            }
        }
    }
    
    public static void main(String[] args) {
        Map<Integer, List<Integer>> graph = Map.of(
            1, List.of(2, 3),
            2, List.of(4),
            3, List.of(4),
            4, List.of()
        );
        bfs(graph, 1);
    }
}

Medium Problem: Sliding Window Maximum — Why Your Naive Queue Fails At Scale

Sliding Window Maximum sounds easy: given an array and window size k, return max in each window. The naive solution is O(n*k) — deque and enqueue k elements for every window shift. That's fine for k=3. For k=100,000 on a stream of a million records? Your system melts.

The trick: maintain a deque (double-ended queue) that stores indices, not values. Before adding a new element, pop from the back any indices whose values are smaller. The front always holds the max for the current window. When the front index falls out of the window, pop it. Every element enters and leaves exactly once — O(n) total.

Why seniors love this: it's not about the problem. It's about recognizing that a plain queue doesn't know priority. You need a monotonic deque. In production, this pattern appears in rate limiting, monitoring dashboards, and real-time analytics. Stock tickers, server CPU graphs, live video feeds — all need sliding window max without O(n*k) death.

// io.thecodeforge — dsa tutorial

import java.util.*;

public class SlidingWindowMax {
    public static int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) return new int[0];
        int[] result = new int[nums.length - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();
        
        for (int i = 0; i < nums.length; i++) {
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();
            }
            dq.addLast(i);
            
            if (dq.peekFirst() <= i - k) {
                dq.pollFirst();
            }
            
            if (i >= k - 1) {
                result[i - k + 1] = nums[dq.peekFirst()];
            }
        }
        return result;
    }
    
    public static void main(String[] args) {
        int[] nums = {1, 3, -1, -3, 5, 3, 6, 7};
        int k = 3;
        System.out.println(Arrays.toString(maxSlidingWindow(nums, k)));
    }
}

Basics of Queue Data Structure

A queue is a linear data structure that follows the First-In-First-Out (FIFO) principle, meaning the element added first is the first one removed. Think of a real-world queue: people join at the back and leave from the front. The core operations are enqueue (add to rear), dequeue (remove from front), peek (view front without removal), and isEmpty. Queues are fundamental for ordered processing, task scheduling, and breadth-first traversal. The two primary implementations are array-based (circular buffer to reuse space) and linked-list-based (dynamic memory). Understanding these basics is critical before tackling bounded vs unbounded queues or performance analysis. A queue's simplicity hides its power: it enforces fairness and order without complex logic. Always consider the trade-offs between fixed-capacity arrays (bounded, zero allocation) and dynamic structures (flexible but heap-dependent). Mastering queue basics prevents common pitfalls like memory leaks from unbounded growth or false overflow in circular buffers.

// io.thecodeforge — dsa tutorial
public class QueueBasics {
    private int[] arr;
    private int front, rear, size, capacity;
    public QueueBasics(int cap) { capacity = cap; arr = new int[cap]; front = 0; rear = -1; size = 0; }
    public void enqueue(int x) {
        if (size == capacity) throw new IllegalStateException("Queue full");
        rear = (rear + 1) % capacity;
        arr[rear] = x;
        size++;
    }
    public int dequeue() {
        if (size == 0) throw new IllegalStateException("Queue empty");
        int val = arr[front];
        front = (front + 1) % capacity;
        size--;
        return val;
    }
    public int peek() { return arr[front]; }
    public boolean isEmpty() { return size == 0; }
}

Hard Queue Problems — Advanced Techniques

Hard queue problems challenge your ability to combine queue properties with specialized patterns. Two canonical examples are Sliding Window Maximum (SWM) and Task Scheduler. SWM requires finding the maximum in every contiguous subarray of size k. A naive O(n*k) solution fails; the optimal approach uses a deque (double-ended queue) storing indices in decreasing order. This reduces complexity to O(n) by maintaining candidate maximums. Task Scheduler involves arranging tasks with cooldowns — use a max-heap paired with a queue to track cooldown timing. Another hard problem is Design Circular Deque with constant-time operations. Applying BFS on graphs with constraints (like shortest path with obstacles) demands queue manipulation edge cases. Hard problems test your understanding of queue limits: memory, concurrency (producer-consumer with bounded queues), and latency (avoiding polling with blocking operations). Mastering these builds intuition for real-world systems like message brokers or rate limiters.

// io.thecodeforge — dsa tutorial
import java.util.*;
public class SlidingWindowMax {
    public int[] maxSlidingWindow(int[] nums, int k) {
        if (nums.length == 0) return new int[0];
        int[] res = new int[nums.length - k + 1];
        Deque<Integer> dq = new ArrayDeque<>();
        for (int i = 0; i < nums.length; i++) {
            while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) dq.pollFirst();
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
            dq.offerLast(i);
            if (i >= k - 1) res[i - k + 1] = nums[dq.peekFirst()];
        }
        return res;
    }
}