Queues: FIFO Operations and Trade-offs
Explain queue behaviour, trace the four required operations, and justify when a FIFO structure fits a problem.
What you need to be able to do
- explain a queue as a first-in, first-out (FIFO) structure;
- use and trace enqueue, dequeue, front and isEmpty accurately;
- explain how queue operations affect performance and memory use;
- justify whether a queue is appropriate for a specific problem.
Rapid Recall Deck
Attempt each card first. If a term is new, flip and study it, then answer it again without looking. Mark only secure recall as “Know it”.
Trace a queue from front to rear
[A, B, C] ← Rear. The queue then performs enqueue(D), front(), dequeue(), enqueue(E), dequeue().Trace the operations
isEmpty().enqueue(D)→[A, B, C, D]front()returnsA; queue stays[A, B, C, D]dequeue()returnsA; queue becomes[B, C, D]enqueue(E)→[B, C, D, E]dequeue()returnsB; queue becomes[C, D, E]
isEmpty() returns False because three items remain.
Front and rear have different jobs
Rear
enqueue adds a new item at the rear. New arrivals wait behind items that arrived earlier.
Front
dequeue removes the front item, while front inspects that item without removing it.
Explain FIFO precisely
A student says, “A queue always removes the newest item because that item is at the rear.” Explain the error.
New items are enqueued at the rear, but items are dequeued from the front. Therefore the item that has been in the queue the longest reaches the front first and is removed first. The newest item waits at the rear rather than leaving immediately.
What changes as a queue grows?
Explain the effect of heavy demand
A print queue grows from 3 jobs to 3,000 jobs while the printer processes only one job at a time. Explain one effect on memory and one reason the queue still preserves fair arrival order.
Memory use increases because the queue must store information for many more waiting jobs. FIFO order is preserved because each new job is enqueued at the rear while the oldest waiting job is dequeued from the front.
Queue or stack?
Explain why a queue fits the help-desk rule
A help desk wants tickets handled in the order they were submitted unless a separate priority rule is introduced. Explain why a queue fits that rule and why a stack would not.
Each submitted ticket can be enqueued at the rear. The help desk then dequeues the ticket at the front, so the oldest waiting ticket is handled first. A stack would instead process the newest ticket first and would not match the required arrival order.
Teacher-created Paper 2 practice
1. A queue initially contains, from front to rear, [5, 8, 11]. Trace: enqueue(14), dequeue(), front(), enqueue(17).
2. Explain how front() differs from dequeue().
3. A network device buffers packets that should normally be forwarded in arrival order. Explain why FIFO queue behaviour is suitable.
enqueue(14)→[5,8,11,14];dequeue()returns 5 →[8,11,14];front()returns 8 with no change;enqueue(17)→[8,11,14,17].front()returns the front item without removing it;dequeue()returns and removes the front item.- Packets can be enqueued as they arrive and dequeued for forwarding from the front, preserving arrival order. This matches FIFO when no other scheduling rule overrides that order.
Finish the learning cycle
IA — main task
Continue refining the IA problem/planning material. Identify any data that arrives over time or needs to be processed in an order, and document the requirement without forcing a particular data structure yet.
Syllabus — short retrieval
Repeat only the queue cards marked “Review again”, then explain aloud why a printer queue is FIFO and an Undo history is LIFO.