Queues, Circular Buffers & Linked List Pointer Mechanics

A Queue enforces First-In First-Out (FIFO) access.

Circular Queue Mechanics:

To prevent false overflow where unused memory accumulates at the front of an array, the end of the array wraps around to index 0 using modulo arithmetic.

- Enqueue: rear = (rear + 1) % N; Q[rear] = item;

- Dequeue: front = (front + 1) % N; return Q[front];

- Empty: front == rear.

- Full: (rear + 1) % N == front (sacrifices 1 physical slot to disambiguate full from empty).

Queue Implemented with Two Stacks:

- Push to S1 for Enqueue(x): O(1).

- Dequeue(): If S2 is non-empty, pop S2. If S2 is empty, transfer all elements from S1 to S2 (inverting order) and pop S2.

Each element is pushed to S1 once, popped from S1 once, pushed to S2 once, and popped from S2 once. Total 4 operations over its lifetime: Amortized O(1) time.

A Linked List stores elements in dynamically allocated nodes containing data and pointers.

Floyd's Tortoise and Hare Cycle Finding Theorem:

Let a singly linked list have a linear non-cyclic prefix of length k, followed by a cycle of length C.

- Slow pointer S advances 1 node per tick.

- Fast pointer F advances 2 nodes per tick.

When S enters the cycle at time k, F is at position k mod C inside the cycle. The relative distance between F and S increases by 1 each step. Thus, F catches S in at most C steps.

Finding the Cycle Entry:

When they meet at distance d from the start of the cycle: the distance from head to cycle start is k. The distance from the meeting point to cycle start is also k (mod C). Moving S to head and advancing both 1 step per tick guarantees they meet exactly at the cycle entrance!