Foundation 06
Queue
A first-in, first-out collection: new items join the back and leave from the front.
01
Mental model
What the structure guarantees
A queue preserves arrival order. That property is why breadth-first search processes every state at distance d before any state at distance d + 1.
02
Implementation
How that model appears in code
Use deque in Python, ArrayDeque through the Queue interface in Java, and std::queue in C++. Removing index zero from an array-backed list is not a queue implementation; it shifts the remaining items.
Queue basics
Queue<Integer> queue = new ArrayDeque<>();
queue.add(7);
int front = queue.peek();
int removed = queue.poll();from collections import deque
queue = deque([7])
front = queue[0]
removed = queue.popleft()queue<int> q;
q.push(7);
int front = q.front();
q.pop();03
Operation costs
What gets more expensive as the input grows
OperationCostWhy
Add at back
O(1)Only the tail changes.Peek or remove front
O(1)A queue implementation keeps direct access to the head.Search the queue
O(n)Items may need to be inspected in order.04
Tradeoffs
Choose it for the operations it makes cheap
Good fit
- Breadth-first search
- Level-order traversal
- Scheduling in arrival order
Poor fit
- Depth-first exploration
- Random access
- Priority-based removal
Used by
Breadth-first search modules planned for a later release
05
Common mistakes
Errors that survive a first glance
Do not use Python list.pop(0)
It shifts every remaining element. deque.popleft performs the intended constant-time operation.
Queue is a Java interface
Instantiate ArrayDeque and store it in a Queue variable.
A priority queue is a different contract
It removes by priority, not strictly by arrival time.