Beginner 5 min · March 05, 2026

Queue Data Structure — OutOfMemoryError from Unbounded

An unbounded LinkedBlockingQueue in production caused OutOfMemoryError.

Naren · Founder

Plain-English first. Then code. Then the interview question.

⚡Quick Answer

A queue is a FIFO data structure: the first item added is the first item removed.
Two core operations: enqueue (add to rear) and dequeue (remove from front).
Java's ArrayDeque and LinkedList provide O(1) enqueue and dequeue.
Use offer() and poll() over add() and remove() to handle full/empty queues gracefully.
Production mistake: unbounded queues cause OOM when producers outpace consumers.
Biggest mistake: sharing a plain queue across threads without synchronization leads to data corruption.

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.

Worked Example — Queue Operations and BFS Simulation

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

dequeue(): remove doc1. Queue: [doc2,doc3]. Print doc1.
enqueue('doc4'): Queue: [doc2,doc3,doc4].
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.

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.

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.

Queue vs Stack: Side-by-Side Comparison

Feature / Aspect	Queue (FIFO)	Stack (LIFO)
Order principle	First In, First Out	Last In, First Out
Real-world analogy	Queue at a ticket counter	Stack of pancakes
Add operation name	Enqueue (add to rear)	Push (add to top)
Remove operation name	Dequeue (remove from front)	Pop (remove from top)
Peek operation	See the front item	See the top item
Common use cases	BFS, print spooling, message queues	DFS, undo/redo, call stack
Java built-in class	LinkedList / ArrayDeque (as Queue)	Stack / ArrayDeque (as Stack)
Time complexity (add/remove)	O(1) for both	O(1) for both
Access to middle elements	Not allowed — violates FIFO	Not allowed — violates LIFO

Key Takeaways

A queue is FIFO — the first item added is the first item removed, just like a line at a ticket counter. This is not just a rule, it's a guarantee that keeps systems fair and ordered.
The two essential operations are enqueue (add to back) and dequeue (remove from front) — everything else, like peek and isEmpty, supports those two core actions.
In Java, always use offer() to add and poll() to remove — they handle edge cases (full/empty queue) gracefully by returning false or null instead of throwing exceptions.
The circular queue trick — using (index + 1) % capacity — is how array-based queues avoid wasting space, and it's a favourite implementation question in technical interviews.
For multi-threaded production systems, prefer java.util.concurrent.BlockingQueue over manual synchronization — it's been battle-tested for years.
Always bound queue size to prevent OutOfMemoryError in producer-consumer scenarios — an unbounded queue is a ticking time bomb.

Common Mistakes to Avoid

Using remove() instead of poll() on an empty queue
Symptom: NoSuchElementException thrown when queue is empty, crashing the application.
Fix: Always use poll() which returns null when empty. Check for null before operating on the returned value, or wrap in isEmpty() guard.
Treating a queue like a list and accessing items by index
Symptom: Compilation error (Queue does not support get(index)) or unexpected behaviour if using LinkedList.peek() incorrectly.
Fix: If you need random access, use ArrayList. Otherwise, use the correct queue methods: offer(), poll(), peek().
Forgetting the isEmpty() check before dequeue in a loop
Symptom: NullPointerException when poll() returns null and you call methods on the result without null-checking.
Fix: Always check isEmpty() before each poll() call, or null-check immediately after poll(). Better: use while (!queue.isEmpty()) { process(queue.poll()); }
Using an unbounded queue in a producer-consumer scenario without backpressure
Symptom: OutOfMemoryError when producers outpace consumers; queue grows until heap exhausted.
Fix: Use a bounded queue (ArrayBlockingQueue) with a sensible capacity. Implement backpressure: either block the producer, drop items, or use a circuit breaker.
Sharing a plain Queue across threads without synchronization
Symptom: Data corruption, lost items, ConcurrentModificationException, or unexpected nulls in multi-threaded context.
Fix: Use thread-safe queue implementations: BlockingQueue implementations, ConcurrentLinkedQueue, or wrap with Collections.synchronizedQueue and synchronize all compound operations.

Interview Questions on This Topic

QCan you explain the difference between a queue and a stack, and give a real-world example of where you'd use each one?JuniorReveal
A queue is FIFO (First In, First Out) — the oldest item is processed first. Real-world example: print spooler where documents print in order of submission. A stack is LIFO (Last In, First Out) — the most recent item is processed first. Example: undo/redo in a text editor where the most recent action can be undone first. In coding, use a queue for BFS traversal of a graph and a stack for DFS or expression evaluation.
QHow would you implement a queue using two stacks? Walk me through the logic and the time complexity of each operation.Mid-levelReveal
Use two stacks: inbox for enqueue operations and outbox for dequeue operations. - enqueue(x): push x onto inbox. O(1). - dequeue(): if outbox is empty, pop all elements from inbox and push onto outbox (reversing order). Then pop from outbox. Amortized O(1) per dequeue, because each element is moved at most once. - peek(): similar to dequeue but pop and push back? Actually, just check outbox.peek() after ensuring it's filled. Java: use Stack or ArrayDeque. Edge cases: empty queue on dequeue should throw or return null. This implementation is a classic interview question to test understanding of FIFO vs LIFO.
QWhat is the difference between poll() and remove() in Java's Queue interface — and which one would you use in production, and why?JuniorReveal
Both retrieve and remove the head of the queue. poll() returns null if the queue is empty; remove() throws NoSuchElementException. In production, use poll() because it allows graceful handling of empty queues without exception overhead. Coupled with a null-check or isEmpty() guard, poll() avoids crashes and is safer.
QHow would you implement a bounded blocking queue in Java from scratch? What concurrency primitives would you use?SeniorReveal
I'd implement a circular array with locks and conditions. Use a ReentrantLock with two Condition objects: notFull and notEmpty. On enqueue: acquire lock, wait while count == capacity (notFull.await()), insert, signal notEmpty. On dequeue: acquire lock, wait while count == 0 (notEmpty.await()), remove, signal notFull. This ensures thread safety and blocks producers/consumers appropriately. Java provides LinkedBlockingQueue and ArrayBlockingQueue, but understanding the internals shows deep knowledge of concurrency.
QWhy does Python's list perform poorly as a queue? How would you fix it?Mid-levelReveal
list.pop(0) is O(n) because it shifts all remaining elements left. For large queues, especially in BFS, this degrades performance to O(n^2). The fix is to use collections.deque which provides O(1) append and popleft via a doubly-linked list of fixed-size blocks. In production code, always use deque for queue-like operations.

Frequently Asked Questions

What is a queue data structure in simple terms?

A queue is a collection of items where the first item added is always the first item removed — just like people lining up at a coffee shop. You add new items to the back and remove them from the front. This FIFO (First In, First Out) rule is what defines a queue and makes it useful for any situation where order of arrival matters.

What is the difference between a queue and a stack?

A queue is FIFO — the oldest item leaves first, like a queue at a supermarket checkout. A stack is LIFO — the most recently added item leaves first, like a stack of books where you always take from the top. Use a queue when you need to preserve arrival order (BFS, task scheduling). Use a stack when you need to reverse things or undo operations (DFS, browser history).

When should I use a queue instead of a list or array?

Use a queue when you only ever need to add to one end and remove from the other — and you need that access pattern enforced. A queue makes your intent explicit in the code and prevents accidental random access. If you find yourself needing to read or modify items in the middle, an array or list is the right tool. Queues shine in producer-consumer scenarios, BFS graph traversal, and anywhere tasks must be processed in strict arrival order.

Why does Python's list perform poorly as a queue?

list.pop(0) is O(n) because it shifts every element left after the removal. deque is a doubly-linked list that provides O(1) append and popleft. For large queues, using a list instead of deque makes BFS O(V^2) instead of O(V+E).

What is a circular queue and why is it useful?

A circular queue uses a fixed-size array with head and tail indices that wrap around using modulo. This avoids the memory waste of a linear queue where dequeued slots cannot be reused. It is ideal for producer-consumer scenarios where buffer size is bounded and fixed.

How do I make a queue thread-safe in Java?

The simplest way is to use one of the java.util.concurrent.BlockingQueue implementations: ArrayBlockingQueue, LinkedBlockingQueue, or ConcurrentLinkedQueue. If you must use a non-thread-safe queue, wrap it with Collections.synchronizedQueue and synchronize every compound operation (like isEmpty followed by poll). Better yet, use BlockingQueue which handles blocking and synchronization internally.

🔥

That's Stack & Queue. Mark it forged?

5 min read · try the examples if you haven't