Linear

Queue Fundamentals

A first-in first-out collection — elements enter at the rear and leave from the front, both in O(1). The backbone of BFS graph traversal, task scheduling, and every system where arrival order must be preserved.

Foundations · Array · Linked List · Stack · Queue · HashMap · Binary Tree · BST · Heap · Trie · Graph · Sorting · Binary Search · Two Pointers · Sliding Window · Dynamic Prog.

Section One · Foundation

What is a Queue?

Every queue enforces a strict contract: elements enter at one end (the rear) and leave from the other end (the front), with no access to anything in between — a linear collection governed entirely by arrival order. The first element added is guaranteed to be the first element processed, which is the natural model for any system where order of arrival must be respected: print jobs, network packets, customer service lines. There is no random access, no searching, no insertion anywhere except the rear; the constraint is the contract. ArrayDeque uses a resizable circular array internally with head and tail indices — enqueue advances the tail, dequeue advances the head, both in O(1) with no element shifting. BFS graph traversal is the canonical queue algorithm; every level-order tree traversal, shortest-path search on unweighted graphs, and multi-source spread problem uses exactly one queue.

Analogy: The checkout line at a supermarket. Customers join at the back and are served from the front — nobody cuts in, nobody is served out of order. The cashier (the algorithm) always processes the customer who has been waiting longest. That guarantee of arrival-order processing is exactly what makes a queue the right structure for BFS: you process nearby nodes before far ones, level by level.

Section Two · Mental Model

How It Thinks

Elements enter at rear, leave from front

▶

Arrival order is guaranteed — first in, first out, always

Head and tail indices on a circular array

▶

Enqueue and dequeue both O(1) — no shifting, no copying

No access to middle elements

▶

The constraint enforces fair ordering — no element can jump the queue

Queue processes nodes level by level

▶

BFS explores the nearest nodes first — shortest path on unweighted graphs

Empty queue has no front element

▶

Always check isEmpty() before dequeue or peek — both throw on empty

Section Three · Operations

Core Operations

Enqueue

Adds a new element at the rear of the queue, increasing size by one in O(1) time.

Pseudocode

 function enqueue(queue, value):
    queue.addLast(value) // O(1) — advances tail index // resize if backing array full: amortized O(1) 

Enqueue — new element arrives at rear

addLast() not add() for queue semantics:

On ArrayDeque used as a queue: use offer() or addLast() to enqueue — both add to the tail.
Never use push() which adds to the head (stack semantics).
Declare as Queue<T> rather than ArrayDeque<T> to prevent calling the wrong methods at compile time.

Dequeue

Removes and returns the front element of the queue, decreasing size by one in O(1) time.

Pseudocode

 function dequeue(queue):
if queue is empty:
throw NoSuchElementException // guard — always check first return queue.removeFirst() // O(1) — advances head index 

Dequeue — front element departs

Dequeue throws — guard with isEmpty():

removeFirst() on an empty ArrayDeque throws NoSuchElementException. poll() is the null-returning alternative — use it when an empty queue is a valid state your code handles.
For BFS, the standard pattern is while (!queue.isEmpty()) dequeue.

Peek

Returns the front element without removing it, allowing inspection of the next element to be processed in O(1).

Pseudocode

 function peek(queue):
if queue is empty:
return null // or throw — depends on method return queue.peekFirst() // O(1) — reads head without moving it 

peek() vs element() vs peekFirst():

On ArrayDeque: peekFirst() returns null if empty, element() throws if empty.
For a queue declared as Queue<T>, peek() maps to peekFirst().
Use peekFirst() when an empty queue is expected; use element() to fail loudly on a bug.

isEmpty

Returns true if the queue contains no elements, preventing dequeue and peek from throwing on an empty queue.

Pseudocode

 function isEmpty(queue):
return queue.size() == 0 // O(1) — size is a stored field 

The BFS loop pattern:

The canonical BFS structure is while (!queue.isEmpty()) { process(queue.poll()); enqueue neighbours; }.
The isEmpty() check is the loop condition — never omit it.
Enqueue neighbours inside the loop, not before it, to avoid processing nodes before their level is established.

BFS Using a Queue

Explores a graph or tree level by level by processing each node and enqueuing its unvisited neighbours before moving on.

Pseudocode

 function bfs(graph, start):
    queue = new Queue
    visited = new Set
enqueue(queue, start)
    visited.add(start)
while queue is not empty:
        node = dequeue(queue)
process(node)
for each neighbour of node:
if neighbour not in visited:
                visited.add(neighbour) // mark on enqueue not dequeue enqueue(queue, neighbour)
// O(V + E) total 

BFS — level-by-level traversal using a queue

Mark visited on enqueue — not on dequeue:

If you mark a node visited when you dequeue it, the same node can be enqueued multiple times before it is processed, causing redundant work or infinite loops on cyclic graphs.
Mark visited immediately when you enqueue — before the node is processed, not after.

Common Mistake: Using a Stack instead of a Queue for BFS and getting DFS by accident. Both iterate until empty and both visit every node — but a stack processes the most recently added node next (LIFO), producing depth-first order. A queue processes the earliest-added node next (FIFO), producing breadth-first order. The data structure determines the traversal order, not the loop logic.

═══════════════════════════════════════════════════════════════════════ -->

Section Four · Variant

Circular Queue

A circular queue (ring buffer) is a fixed-capacity queue implemented on a plain array where the tail wraps around to index 0 when it reaches the end — avoiding the O(n) shift that a naive array queue requires. Both head and tail are integer indices that advance modulo capacity: enqueue moves tail = (tail + 1) % capacity, dequeue moves head = (head + 1) % capacity, both in O(1). The trade-off is fixed capacity — a ring buffer cannot grow; overflow must be handled explicitly, either by rejecting new elements or by expanding (which breaks the O(1) space guarantee). Ring buffers are the implementation of choice for bounded queues in operating systems, audio streaming, and network packet buffers where predictable memory usage matters more than unlimited capacity.

Simple Queue (array)

Naive array implementation

Enqueue: O(1) — write to tail index
Dequeue: O(n) — shift all elements left
Or: O(1) dequeue + O(n) periodic compaction
Wasted space at the front accumulates

Circular Queue (ring buffer)

Wrap-around implementation

Enqueue: O(1) — tail = (tail+1) % capacity
Dequeue: O(1) — head = (head+1) % capacity
Fixed capacity — must handle overflow
Zero wasted space — indices wrap around

Ring buffer — 8 slots, head and tail pointers

Wraparound — tail wraps from slot 7 to slot 0

Full vs empty — the size counter solves it:

When head == tail, the ring buffer is either full or empty — you cannot tell from indices alone.
The cleanest solution is a separate size counter: enqueue increments it, dequeue decrements it, full means size == capacity, empty means size == 0.

Section Five · Variant

Deque — Double-Ended Queue

A deque (pronounced "deck") generalises both queue and stack — O(1) add/remove at both front and rear. A queue restricts you to add-at-back, remove-from-front. A deque opens both ends for both operations. Java's ArrayDeque is the recommended implementation for all queue, stack, and deque use cases — faster than LinkedList (cache-friendly) and faster than the legacy Stack class (no synchronisation overhead).

Restrict to…	Behaviour	Replaces
`addFirst` / `removeFirst` only	LIFO — Stack	Legacy `Stack` class
`addLast` / `removeFirst` only	FIFO — Queue	`LinkedList` as queue
All four operations	True Deque	Sliding window max, monotonic deque, 0-1 BFS

Deque has its own dedicated page:

covering the circular buffer internals, ArrayDeque vs LinkedList benchmarks, the monotonic deque pattern (Sliding Window Maximum), and full Java/Python implementations.
→ Go to the Deque deep dive

Section Six · Implementation

Build It Once

Build this from scratch once — it makes the mechanics concrete. In any real project or interview, reach for the built-in (Section 07).

Java — Queue and Circular Queue core mechanics

// ── Part 1: Queue wrapper — shows the correct API usage pattern ──// Build once to understand the mechanics — use ArrayDeque directly in practice.import java.util.ArrayDeque;
import java.util.Deque;
classSimpleQueue<T> {
private Deque<T> deque = new ArrayDeque<>();
voidenqueue(T value) {
        deque.addLast(value); // O(1) — add to rear
}

    T dequeue() {
if (deque.isEmpty()) throw new RuntimeException("Queue empty");
return deque.removeFirst(); // O(1) — remove from front
}

    T peek() {
if (deque.isEmpty()) return null;
return deque.peekFirst(); // O(1) — read front
}
}
// ── Part 2: Circular Queue — ring buffer from scratch ──classCircularQueue {
privateint[] data;
privateint head = 0, tail = 0, size = 0, capacity;
CircularQueue(int capacity) {
this.capacity = capacity;
        data = newint[capacity];
    }
booleanenqueue(int val) {
if (size == capacity) return false; // full — reject
data[tail] = val;
        tail = (tail + 1) % capacity; // O(1) — wraparound
size++;
return true;
    }
intdequeue() {
if (size == 0) throw new RuntimeException("Empty");
int val = data[head];
        head = (head + 1) % capacity; // O(1) — wraparound
size--;
return val;
    }
intpeek() { return data[head]; } // O(1)booleanisFull() { return size == capacity; }
}
  
 Queue — Full Implementation  
   
Java — Complete Queue implementations
 // ═══════════════════════════════════════════════════════════ // Class 1: Queue<T> — generic wrapper over ArrayDeque // ═══════════════════════════════════════════════════════════ import java.util.ArrayDeque;
import java.util.Deque;
public class Queue<T> {
private Deque<T> deque = new ArrayDeque<>();
void enqueue(T value) { // O(1) amortized
deque.addLast(value);
    }

    T dequeue() { // O(1) if (deque.isEmpty())
throw new RuntimeException("Queue empty");
return deque.removeFirst();
    }

    T peek() { // O(1) return deque.peekFirst();
    }
boolean isEmpty() { // O(1) return deque.isEmpty();
    }
int size() { // O(1) return deque.size();
    }
public String toString() {
return deque.toString();
    }
public static void main(String[] args) {
        Queue<Integer> q = new Queue<>();
        q.enqueue(10); q.enqueue(20); q.enqueue(30);
        System.out.println(q); // [10, 20, 30]
System.out.println(q.dequeue()); // 10 (FIFO)
System.out.println(q.peek()); // 20 (new front)
System.out.println(q.size()); // 2 // BFS sketch with java.util.Queue interface
java.util.Queue<String> bfs = new ArrayDeque<>();
        bfs.offer("A");
while (!bfs.isEmpty()) {
            String node = bfs.poll(); // O(1) dequeue
System.out.print(node + " ");
        }
    }
}
// ═══════════════════════════════════════════════════════════ // Class 2: CircularQueue — fixed-capacity ring buffer // ═══════════════════════════════════════════════════════════ public class CircularQueue {
private int[] data;
private int head, tail, size, capacity;
public CircularQueue(int capacity) {
this.capacity = capacity;
        data = new int[capacity];
        head = 0; tail = 0; size = 0;
    }
public boolean enqueue(int val) { // O(1) if (size == capacity) return false;
        data[tail] = val;
        tail = (tail + 1) % capacity;
        size++;
return true;
    }
public int dequeue() { // O(1) if (size == 0) throw new RuntimeException("Empty");
int val = data[head];
        head = (head + 1) % capacity;
        size--;
return val;
    }
public int peek() { // O(1) if (size == 0) throw new RuntimeException("Empty");
return data[head];
    }
public boolean isEmpty() { return size == 0; }
public boolean isFull()  { return size == capacity; }
public int size()        { return size; }
public String toString() {
        StringBuilder sb = new StringBuilder("[");
for (int i = 0; i < size; i++)
            sb.append(i > 0 ? ", " : "").append(data[(head + i) % capacity]);
return sb.append("]").toString();
    }
public static void main(String[] args) {
        CircularQueue cq = new CircularQueue(4);
        cq.enqueue(10); cq.enqueue(20);
        cq.enqueue(30); cq.enqueue(40);
        System.out.println(cq); // [10, 20, 30, 40]
System.out.println(cq.isFull()); // true
cq.dequeue(); cq.dequeue(); // remove 10, 20
cq.enqueue(50); cq.enqueue(60); // wrap around
System.out.println(cq); // [30, 40, 50, 60]
}
}
Python — Queue implementations
 # ── Part 1: collections.deque as a queue ── from collections import deque

q = deque()
q.append(10) # enqueue — O(1)
q.append(20)
q.append(30)
front = q.popleft() # dequeue — O(1), returns 10
peek  = q[0] # peek   — O(1), returns 20
empty = len(q) == 0 # isEmpty — O(1) # BFS with deque def bfs(graph, start):
    queue = deque([start])
    visited = {start}
while queue:
        node = queue.popleft() # O(1) for neighbour in graph[node]:
if neighbour not in visited:
                visited.add(neighbour) # mark on enqueue
queue.append(neighbour)
# ── Part 2: CircularQueue — ring buffer ── class CircularQueue:
def __init__(self, capacity):
        self.data = [None] * capacity
        self.head = 0
self.tail = 0
self.size = 0
self.capacity = capacity
def enqueue(self, val): # O(1) if self.size == self.capacity:
return False
self.data[self.tail] = val
        self.tail = (self.tail + 1) % self.capacity
        self.size += 1 return True def dequeue(self): # O(1) if self.size == 0:
raise IndexError("Empty")
        val = self.data[self.head]
        self.head = (self.head + 1) % self.capacity
        self.size -= 1 return val
def peek(self): return self.data[self.head] # O(1) def is_full(self): return self.size == self.capacity
def is_empty(self): return self.size == 0 def __str__(self):
        items = [self.data[(self.head + i) % self.capacity]
for i in range(self.size)]
return str(items)
# Usage
cq = CircularQueue(4)
cq.enqueue(10); cq.enqueue(20); cq.enqueue(30); cq.enqueue(40)
cq.dequeue(); cq.dequeue() # remove 10, 20
cq.enqueue(50); cq.enqueue(60) # wrap around
print(cq) # [30, 40, 50, 60] 

Section Seven · Java Built-in

Use It In Java

IN JAVA

USE Queue<T> queue = new ArrayDeque<>()
Deque<T> deque = new ArrayDeque<>()

IMPORT import java.util.ArrayDeque;
import java.util.Queue;
import java.util.Deque;

METHODS

Method	End	Complexity	Throws if empty?	Note
`offer(value)`	Rear	O(1)	No	Preferred enqueue
`add(value)`	Rear	O(1)	No	Same as offer for ArrayDeque
`poll()`	Front	O(1)	No (returns null)	Preferred dequeue
`remove()`	Front	O(1)	Yes	Throws NoSuchElementException
`peek()`	Front	O(1)	No (returns null)	Preferred front-peek
`element()`	Front	O(1)	Yes	Throws if empty
`addFirst(value)`	Front	O(1)	No	Deque only — stack/deque use
`addLast(value)`	Rear	O(1)	No	Deque only — same as offer
`size()`	—	O(1)	—	Stored as field

GOTCHA ArrayDeque does not permit null elements. If you call offer(null) or add(null), it throws NullPointerException immediately. This matters when processing data that may contain nulls — use LinkedList instead, which permits null elements, or filter nulls before enqueuing. This is the only case where LinkedList is preferable to ArrayDeque as a queue.

CHOOSE Declare as Queue<T> when you only need FIFO operations — the interface prevents accidentally calling addFirst() or other deque methods. Declare as Deque<T> when you need both-ends access. Use ArrayDeque in both cases — it is faster than LinkedList, uses less memory, and has better cache behaviour.

Section Eight · Decision Guide

Pick The Right Structure

Decision flowchart — choosing the right queue variant

Structure	Enqueue	Dequeue	Ordering	Best For
Queue = ArrayDeque ← this	O(1)	O(1)	FIFO	BFS, task queues, level-order traversal
Deque	O(1) both ends	O(1) both ends	FIFO or LIFO	Sliding windows, monotonic deque, 0-1 BFS
Stack	O(1)	O(1)	LIFO	Undo, parsing, DFS, backtracking
PriorityQueue	O(log n)	O(log n)	Priority first	Dijkstra, scheduling by priority, top-k
Circular Queue	O(1)	O(1)	FIFO, fixed capacity	Bounded buffers, embedded systems, audio streams

No Need LIFO? Yes ArrayDeque as Stack push/pop — replaces legacy Stack PriorityQueue O(log n)O(log n)NoPriorityDijkstra, top-K Circular Queue O(1)O(1)NoFIFOBounded buffers, OS

Section Nine · Practice

Problems To Solve

Queue interview problems almost always involve one of two patterns: BFS (use a queue to explore a graph or tree level by level — any problem involving shortest path on unweighted graphs, level-order traversal, or multi-source spreading is a BFS candidate) or monotonic deque (maintain a deque in sorted order to answer range maximum or minimum queries in O(1) as a sliding window moves). Look for the words “level”, “shortest”, “minimum steps”, “spreading”, or “sliding window maximum” as signals that one of these two patterns applies.

Difficulty	Pattern	Problem	Key Insight
Medium	bfs	Number of Islands	BFS from each unvisited land cell — enqueue neighbours, mark visited on enqueue not on dequeue to avoid processing the same cell twice.
Medium	bfs	Binary Tree Level Order Traversal	Enqueue the root, then process level by level — snapshot the queue size at the start of each level to know how many nodes belong to that level.
Medium	bfs	Rotting Oranges	Multi-source BFS — enqueue all rotten oranges at time 0, then spread rot level by level; the answer is the number of levels processed.
Medium	design	Design Circular Queue	A fixed-size array with head and tail indices and a size counter — enqueue moves tail forward mod capacity, dequeue moves head forward mod capacity.
Medium	greedy	Task Scheduler	Count task frequencies, always schedule the most frequent remaining task — a max-heap (PriorityQueue) on frequencies gives the greedy choice in O(log k) per slot.
Hard	monotonic	Sliding Window Maximum	A monotonic decreasing deque of indices — remove from the front when the window slides past, remove from the back when a larger element enters.

Interview Pattern:

BFS solves roughly 70% of queue interview problems — whenever you see “shortest path”, “minimum steps”, or “level by level”, reach for a queue and BFS immediately.
The second pattern is monotonic deque: if the problem involves a sliding window and asks for the maximum or minimum in the current window, a deque that evicts smaller (or larger) elements from the rear gives O(1) window queries.
Recognise the keyword, apply the pattern.

→ See all Queue problems with full solutions

LearningTree

Queue | DSA Guide

Queue Fundamentals

What is a Queue?

How It Thinks

Core Operations

Circular Queue

Naive array implementation

Wrap-around implementation

Deque — Double-Ended Queue

Build It Once

Use It In Java

Pick The Right Structure

Problems To Solve