Learn
B2.2.4 | QUEUES AND FIFO
01 | ARRIVE FIRST, LEAVE FIRST
Three students send documents to a printer: A, then B, then C. If the printer serves waiting jobs in arrival order, A should be selected first even though C is the most recent arrival.
A queue is a data structure with first in, first out (FIFO) access. Entries join at the rear and are removed from the front. The earliest remaining entry is served next.
This common SL/HL lesson explains enqueue, dequeue, front and isEmpty, then connects implementation choices to performance, memory and appropriate applications. A queue is defined by its access rule, not by the direction in which you draw it.
02 | FRONT AND REAR HAVE DIFFERENT JOBS
After A, B and C arrive, the logical queue is [A,B,C], written front → rear. Dequeue returns A, while another enqueue adds an item after C.
In a one-entry queue, that entry is both front and rear. In an empty queue there is no front value to return, even if an implementation still stores pointer indexes for the next operation.
03 | FOUR CORE OPERATIONS
| Operation | Purpose | Changes contents? | Example on [A,B,C] |
|---|---|---|---|
| enqueue(value) | Add a new entry at the rear. | Yes | enqueue(D) gives [A,B,C,D]. |
| dequeue() | Remove and return the front entry. | Yes | Returns A and leaves [B,C]. |
| front() | Read the front entry without removing it. | No | Returns A; contents stay [A,B,C]. |
| isEmpty() | Report whether zero entries are waiting. | No | False for this queue. |
front is also called peek in some APIs. The operation names form an abstract interface; Python and Java library names may differ. The method front() is distinct from a stored front index.
04 | TRACE INTERLEAVED ARRIVALS AND REMOVALS
| Operation | Returned item / result | Queue front → rear |
|---|---|---|
| Start | No item | [] |
| enqueue(A) | No item required by this interface | [A] |
| enqueue(B) | No item required | [A,B] |
| front() | A | [A,B] |
| dequeue() | A | [B] |
| enqueue(C) | No item required | [B,C] |
| dequeue() | B | [C] |
| isEmpty() | False | [C] |
| dequeue() | C | [] |
C cannot move ahead of B merely because it arrived after A was served. The access rule applies to the entries still waiting.
Record both the item returned and the remaining contents. A dequeue is not just a read; front is the read-only operation.
05 | FIFO AND LIFO SOLVE DIFFERENT PROBLEMS
With A, then B, then C added and no removals between additions, a queue removes A,B,C. A stack removes C,B,A. Both organise pending entries, but the required service order differs.
A queue fits ordinary arrival-order printing; a stack fits reversing the most recent edit before earlier edits. The choice follows the problem rather than one structure being inherently better.
A priority queue uses a priority rule instead of ordinary FIFO. Do not call a queue strict arrival-order service if urgent jobs are allowed to jump ahead.
06 | UNDERFLOW, CAPACITY AND OVERFLOW
Attempting dequeue or front on an empty queue is an underflow situation. Define a clear response, such as an exception or a separate failure result. A legitimate stored value must not be confused with an empty marker.
A bounded queue has a maximum number of waiting entries. An enqueue beyond that bound needs an overflow policy: reject the new item, block/wait where appropriate, or deliberately discard under a stated policy. These are different behaviours.
A dynamic implementation still has finite resources. FIFO specifies ordering, not unlimited storage or a particular overflow response.
07 | INTERACTIVE: MANAGE A WAITING QUEUE
Enqueue short job names and predict each next result. This teaching queue rejects new entries at its chosen application limit. The diagram and history show front → rear. Changing the limit resets the queue.
| Operation | Result | Waiting entries |
|---|
Try enqueue A, enqueue B, front, dequeue, enqueue C, dequeue. The returned items should be A then B. Test an empty access and a full queue, checking that rejected operations leave existing entries unchanged.
08 | PYTHON LIST: SIMPLE BUT NOT THE BEST FRONT-REMOVAL TOOL
jobs = []
jobs.append("A")
jobs.append("B")
print(jobs[0]) # front: A
print(jobs.pop(0)) # dequeue: A
print(jobs) # ['B']
This implements FIFO correctly for the example. However, pop(0) shifts the remaining list entries towards the beginning, so repeated front removals can become costly for long lists.
Correct behaviour and efficient implementation are separate questions. Changing pop(0) to pop() avoids those shifts but changes the access rule to last-in-first-out for these additions.
For a Python queue with frequent operations at both ends, collections.deque is a suitable standard-library option.
09 | PYTHON DEQUE: QUEUE OPERATIONS AT THE ENDS
from collections import deque
jobs = deque()
jobs.append("A") # enqueue at rear
jobs.append("B")
print(jobs[0]) # front: A
print(jobs.popleft()) # dequeue: A
print(list(jobs)) # ['B']
print(len(jobs) == 0) # False
append and popleft provide the required ends. Front access uses index 0 after checking that an entry exists. This is a deque used with a queue policy, not permission for queue clients to remove whichever end they prefer.
Deque end operations avoid shifting every remaining entry as list.pop(0) does. Its internal storage strategy differs from a single resizable list array.
10 | CONSTRUCT A QUEUE INTERFACE
from collections import deque
def enqueue(queue, item):
queue.append(item)
def is_empty(queue):
return len(queue) == 0
def dequeue(queue):
if is_empty(queue):
raise IndexError("Cannot dequeue an empty queue")
return queue.popleft()
def front(queue):
if is_empty(queue):
raise IndexError("An empty queue has no front")
return queue[0]
jobs = deque()
enqueue(jobs, "A")
enqueue(jobs, "B")
print(front(jobs)) # A
print(dequeue(jobs)) # A
print(dequeue(jobs)) # B
print(is_empty(jobs)) # True
This interface raises IndexError for empty dequeue and front. Its exception policy is explicit rather than returning an ambiguous None. None could be stored as a legitimate entry in this deque.
The functions mutate the supplied queue where appropriate. Read-only front and is_empty do not change its size or order.
11 | A FIXED LINEAR ARRAY CAN RUN OUT OF END SPACE
An array-based queue can keep a front read position and a rear write position. In a simple non-circular design, rear only moves towards the end. After removals, unused slots can accumulate at the beginning.
If rear reaches the end, the implementation may need to shift entries, compact occasionally or reject further enqueues according to its design, even though some earlier slots are unused.
A circular queue reuses those earlier slots by wrapping indexes around. The logical FIFO order is maintained through pointers and a count, rather than by requiring the front entry to remain at physical index 0.
12 | CIRCULAR QUEUE: STATE THE POINTER CONVENTION
Our circular model reserves capacity five. front_index identifies the next slot to read; rear_index identifies the next slot to write. Both begin at 0, and count begins at 0.
Advance a position with (index + 1) % capacity. Modulo wraps index 4 back to 0. Enqueue writes at rear_index and advances it; dequeue reads at front_index and advances it.
Count distinguishes empty from full: empty is count == 0, full is count == capacity. In this convention, front_index == rear_index can occur in either state. Equality alone is insufficient.
13 | SEE A WRAPAROUND TRACE
| Operation on capacity5 | front_index | rear_index: next write | count | Logical queue |
|---|---|---|---|---|
| Start | 0 | 0 | 0 | [] |
| Enqueue A,B,C,D | 0 | 4 | 4 | [A,B,C,D] |
| Dequeue twice | 2 | 4 | 2 | [C,D] |
| Enqueue E | 2 | 0 | 3 | [C,D,E] |
| Enqueue F | 2 | 1 | 4 | [C,D,E,F] |
| Enqueue G | 2 | 2 | 5 | [C,D,E,F,G] |
At the end, physical slots 0..4 contain F,G,C,D,E. Reading the logical queue starts at front_index 2 and wraps, producing C,D,E,F,G.
The rear index points to the next write position, not the most recently added entry. When full, that position is occupied and must not be overwritten; check count before enqueue.
14 | INTERACTIVE: PHYSICAL SLOTS VERSUS LOGICAL ORDER
This capacity-five circular queue shows fixed physical indexes separately from the logical queue. Empty/full checks use count. Removed slots are cleared, while pointer positions continue around the ring. The history reports the most recent action.
Follow the trace above: enqueue A–D, dequeue twice, then enqueue E–G. Observe that front and rear indexes both become 2 when full. Dequeue every entry and observe equality again when empty, distinguished by count.
15 | CONSTRUCT A CIRCULAR ARRAY IMPLEMENTATION
capacity = 5
storage = [None] * capacity
front_index = 0
rear_index = 0
count = 0
# Enqueue A under the next-write convention.
if count == capacity:
print("Queue full")
else:
storage[rear_index] = "A"
rear_index = (rear_index + 1) % capacity
count = count + 1
# Dequeue and clear the consumed slot.
if count == 0:
print("Queue empty")
else:
item = storage[front_index]
storage[front_index] = None
front_index = (front_index + 1) % capacity
count = count - 1
print(item) # A
Check full or empty before touching storage. Each accepted operation changes one slot and a few state values. Dequeue does not shift all remaining entries.
The Python list models reserved storage by policy; its type remains dynamic. Clearing consumed slots avoids retaining unnecessary references in this model. Count, rather than the None marker, determines occupancy.
16 | JAVA: A QUEUE INTERFACE
import java.util.ArrayDeque;
import java.util.Queue;
public class QueueExample {
public static void main(String[] args) {
Queue<String> jobs = new ArrayDeque<>();
jobs.offer("A");
jobs.offer("B");
System.out.println(jobs.peek()); // A
System.out.println(jobs.poll()); // A
System.out.println(jobs.poll()); // B
System.out.println(jobs.isEmpty()); // true
}
}
For this ArrayDeque-backed queue, offer adds at the rear, peek reads the front and poll removes it. The declared Queue interface communicates the intended use.
peek and poll return null if empty for this implementation. Its no-null-entry policy makes that result distinguishable. The alternative no-argument remove throws NoSuchElementException if empty. Our Python wrapper uses an exception policy instead.
This Java collection is not the fixed-capacity-five circular teaching model. Its internal capacity can grow, subject to resources.
17 | PERFORMANCE: NAME THE IMPLEMENTATION
| Implementation | Enqueue / dequeue considerations | Why |
|---|---|---|
| Python list with append/pop(0) | Append may grow; dequeue shifts remaining entries. | Front removal from an array-style list moves later positions. |
| Fixed circular array | Basic enqueue/dequeue use constant work with respect to count. | One slot and bounded pointer/count updates; no full shift. |
| Linked queue with front and rear references | Basic link updates can be constant-time. | Enqueue uses rear; dequeue uses front; allocations still have a cost. |
| Suitable deque implementation | Efficient end operations; details depend on library. | Designed to avoid shifting every remaining item for front removal. |
Constant work describes scaling of the core operations, not exact wall-clock latency. Allocation, runtime and stored item handling can contribute. A dynamic backing resize may make one operation more expensive than typical operations.
18 | MEMORY: CAPACITY, REFERENCES AND BACKLOG
A fixed circular array reserves all its slots even when few entries are waiting. Its storage stays allocated after dequeue unless the whole backing structure is replaced or released.
A linked queue uses node links and allocation overhead but can add nodes as needed. Maintain both front and rear for efficient end operations; after removing its final node, both references must be updated consistently.
Queued jobs may contain only references to larger documents. Counting queue slots alone does not measure the memory or disk used by all pending job payloads. A backlog can exhaust resources even with efficient pointer updates.
19 | APPROPRIATE APPLICATION: PRINT SPOOLING
A printer spooler can accept jobs while the printer processes another. A FIFO waiting queue selects the earliest pending job next under a strict arrival-order policy. Enqueue records an accepted job; dequeue selects it for service.
Separating arrival from service lets users submit without requiring immediate printing. However, dequeue means “removed from waiting”, not automatically “printed successfully”. The system must handle the in-service job, failures and completion separately.
A full queue needs an honest response. Rejecting a new submission, waiting for capacity or using a defined persistent store have different effects. Priority printing and cancellation require additional rules beyond this simple FIFO model.
20 | WORKED PROGRAM: PROCESS JOBS IN ORDER
from collections import deque
jobs = deque(["Report", "Poster", "Worksheet"])
processed = []
while len(jobs) > 0:
current = jobs.popleft()
print("Selected:", current)
# Assume processing succeeds in this teaching example.
processed.append(current)
print(processed)
print(list(jobs))
Selection order is Report, Poster, Worksheet, and the waiting queue ends empty. The example assumes processing succeeds; it does not implement actual printer communication or durable recovery.
Each job is enqueued initially and selected once. Traversing n jobs requires a number of basic operations proportional to n, while the maximum backlog determines the number of waiting entries held.
21 | MORE QUEUE APPLICATIONS
Network buffers hold data waiting for service, task systems hold work awaiting a worker, and customer-service systems can use arrival order when that is the agreed policy. FIFO can prevent later arrivals repeatedly jumping ahead of earlier waiting entries.
FIFO alone does not guarantee short waits or successful service. If arrivals outpace processing, backlog grows until a limit is reached. Long jobs can delay short jobs behind them.
Multiple workers can select jobs in queue order yet finish them in a different order. Distinguish order of dequeue from order of completion.
22 | RATE AND BACKLOG REASONING
Assume an initially empty queue receives three jobs per minute, the single worker removes and completes two per minute, and every minute’s arrivals occur before that minute’s service. With adequate capacity and no failures, the waiting backlog grows by one per minute.
After four such minutes, four jobs remain waiting. This arithmetic depends on the stated event order, initial state and matching units; a different arrival pattern can change the peak queue length even with the same totals.
If service later exceeds arrivals, the existing backlog can shrink. A queue manages order but does not create processing capacity. Do not claim FIFO solves overload by itself.
23 | BOUNDED POLICIES ARE NOT INTERCHANGEABLE
Python deque can be created with maxlen. When full, ordinary append at one end discards an entry from the opposite end. That can suit a rolling history, but is not the same as rejecting a newly submitted print job.
For a rejection-based queue, check the chosen bound and define the failure response. In concurrent systems, a separate check and append may need coordination; a single-user teaching function does not supply concurrency protection.
A blocking queue can make a producer wait, but waiting also needs a timeout/cancellation policy in many applications. The access order, storage mechanism and full-queue policy are separate design choices.
24 | TEST FIFO AND WRAPAROUND
| Test | Expected evidence |
|---|---|
| Empty dequeue/front | Defined underflow response; contents unchanged. |
| Enqueue A,B; front twice | Both reads return A; no removal. |
| Enqueue A,B; dequeue; enqueue C | Queue is [B,C]; next dequeue returns B. |
| Full bounded queue; extra enqueue | Chosen overflow policy, no unintended overwrite. |
| Wrap rear past final physical index | Reuse freed slots while logical FIFO order remains correct. |
| front_index == rear_index | Use count to distinguish empty from full under this convention. |
| Remove last linked entry | Front and rear references both represent empty correctly. |
Also test duplicate values and single-entry transitions. The same value appearing twice still represents two separate queue entries.
25 | EXPLAIN THE CHOICE AND CONSEQUENCES
Use requirement → FIFO mechanism → benefit and limit. For example: “Jobs join at the rear and are removed at the front, therefore a later accepted job does not overtake an earlier waiting job. A growing backlog still needs capacity and service planning.”
For performance, name the implementation: list front removal shifts entries, a circular array advances indexes, and a linked queue updates references. For memory, include reserved slots or links and the data referenced by each job.
Avoid confusing a read-only front operation with dequeue, a rear next-write pointer with the last entry, or a job leaving the waiting queue with completed processing.
26 | READY TO APPLY FIFO
You can now trace and construct queue operations, define empty/full behaviour, explain circular reuse and connect performance and memory to a suitable application.
The next section focuses on programming constructs, beginning with correct instruction sequence.