0/4 traced
Dequeue
Remove the element from the front of the queue.
worst case O(n) time O(1) space
1int dequeue(Queue& q) {2if (q.size == 0) return -1;3int v = q.data[0];4for (int i = 1; i < q.size; ++i) q.data[i-1] = q.data[i];5q.size--; q.tail--; return v;6}
front index
0rear index
4size
4capacity
6indexing
linearBuffer · front stays at index 0; dequeue shifts every survivor left
0 10 R
1 20
2 30
3 40
4 ·
5 ·
FrontRear ShiftedFree slot Read / write this line
Exact work through this line 2 +2 on this line
O(n) time O(1) auxiliary space 1 peak reported values
1comparisons
1reads
0writes
0pointer reads
0pointer writes
0swaps
0allocations
0deallocations
0node visits
0iterations
0calls
0returns
Variables before line
size4
capacity6
readIndexnull
writeIndexnull
currentnull
resultnull
nodes
Variables after line
size4
capacity6
readIndex0
writeIndexnull
currentnull
result10
nodes
Reads, writes, and state changes on this line
result.value null → 10 highlight
Why this bound?
O(n) time · O(1) space
worstnode 1node 2node 3node 4 Work can grow once per node → n
Auxiliary memory model
cursortemporarycounter
A bounded number of scalar/reference slots is reused, so auxiliary storage stays constant.
- Removing index 0 leaves a gap that must be closed to keep the front at index 0.
- All 3 survivors shift one slot left, each a read-write pair.
- Work grows linearly with the queue length: O(n) time, O(1) auxiliary space.
Assumptions behind this claim
- Array elements sit in one contiguous buffer indexed in O(1).
- The front is index 0, so every survivor shifts.
- Each displayed read, write, comparison, allocation, or pointer update is one counted primitive.
- Trace construction and visualization bookkeeping are excluded from the algorithm count.
Step 1 of 5 · dequeue-check Read front
The front value 10 at index 0 is saved to return.
About this implementation
A queue is FIFO. A naive array keeps the front at index 0, so every dequeue shifts the rest left (O(n)); a circular buffer advances a front index modulo capacity instead (O(1)). A linked queue enqueues in O(1) when it keeps a rear pointer, but O(n) without one because it must walk to the last node.