← DSA I

FIFO execution laboratory

Queue Lab

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) {
2 if (q.size == 0) return -1;
3 int v = q.data[0];
4 for (int i = 1; i < q.size; ++i) q.data[i-1] = q.data[i];
5 q.size--; q.tail--; return v;
6}
front index0
rear index4
size4
capacity6
indexinglinear

Buffer · front stays at index 0; dequeue shifts every survivor left

0 10 F R
1 20
2 30
3 40 R
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

worst
node 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.

  1. Removing index 0 leaves a gap that must be closed to keep the front at index 0.
  2. All 3 survivors shift one slot left, each a read-write pair.
  3. 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.

1 / 5