21. Python Chapter 8.5 — linear, linked and circular queues - revision mindmap
All mindmaps · Full chapter · Practice answers
Open full-resolution image · Printable collection - page 21
The map is a completed revision summary. Cover a branch and reconstruct it, then try the linked chapter practice. Read the image at full size when labels are small.
Text version
Queue contract
- FIFO
- Enqueue rear; dequeue/remove front
- Peek reads; display preserves state
- Arrival-order justification versus LIFO
Implementation choices
- Shifting list: move remaining items
- Linear array: no wrap; stated reset/reclamation policy
- Circular array: wrap indices to reuse vacancies
- Linked queue: node links and extra pointer memory
Count-based circular state
- Front = next read index; rear = last inserted index
- Initially front 0, rear −1, size 0
- Empty size 0; full size = capacity
- Advance modulo capacity; size distinguishes empty/full
Sentinel and linked state
- HCI sentinel: start/end initially −1
- Full when next end equals start
- Sentinel last removal resets both indices
- Linked last removal sets both front and rear to None
Derive the operations
- Enqueue: check → advance/link → store → update state
- Dequeue: check → save → advance/unlink → reset if needed
- Display: temporary index/reference through live order
- Queue → stack → queue reverses; check mutation contract
Worked example & exam traps
- Capacity 4: enqueue A,B,C,D; dequeue A,B; enqueue E,F.
- Physical [E,F,C,D]; front=2, rear=1, size=4.
- Logical FIFO order: C → D → E → F. Next insertion is rejected.
- Avoid: front = rear always empty; mix conventions; forget linked rear reset
Sources and reading
This map condenses Chapter 21 and its source trail. Use the self-learning reading guide for the corresponding VJC pages and A notes. It does not add topics to the stated promo scope.