All standard queue operations are restricted to the two ends. Unlike linked lists or arrays, you cannot access or modify elements in the middle of a queue by default. This restriction ensures the FIFO property is maintained.
Exam tip: Always explicitly label which end is front and which is rear when tracing operations: swapping these is the most common mistake in CIE exams.
2. Standard Queue Operations★★☆☆☆⏱ 4 min
All valid queue implementations support the following core operations, each with an expected time complexity of $O(1)$:
`enqueue(item)`: Add a new element to the rear of the queue
`dequeue()`: Remove and return the element from the front of the queue
`peek()` / `front()`: Return the value of the front element without removing it
`isEmpty()`: Return `True` if the queue has no elements, else `False`
`isFull()`: Return `True` if the queue has no remaining space (fixed-size implementations only)
3. Common Queue Implementations★★★☆☆⏱ 5 min
METHODS COMPARED
Queues are most commonly implemented with two underlying structures, compared below:
Fixed Array-based Queue
Uses a contiguous array to store queue elements, with integer pointers for front and rear indices.
Linked-list-based Queue
Uses linked list nodes, with separate pointers to the front and rear nodes of the list.
The circular queue is an improved fixed array implementation that solves the problem of empty slots left at the start of the array after deletions. The rear index wraps around to the start of the array once it reaches the end, reusing empty slots.
Exam tip: CIE often asks for circular queue implementations: remember that one slot is always left empty to distinguish between the full and empty states.
4. Applications of Queues★★☆☆☆⏱ 3 min
**Process scheduling**: Operating systems use queues to order waiting CPU processes by arrival time
**Printer spooling**: Print jobs are queued so the first job sent is the first job printed
**Breadth-First Search (BFS)**: Graph traversal uses a queue to track nodes to visit next
**Data buffering**: Queues handle asynchronous data transfer (e.g. video streaming, IO buffers)
Common Pitfalls
Why: Learners often confuse which end supports which operation, breaking the FIFO property
Why: If all slots are filled, front = rear which matches the empty queue condition, causing logical errors
Why: Learners often assume elements must be shifted in array implementations, which is only true for naive non-pointer implementations
Why: Common confusion between BFS and DFS requirements