IB COMPUTER SCIENCE | B2.2.4 Queues and FIFO

Lesson objective

Explain FIFO queue behaviour and enqueue, dequeue, front and isEmpty, connecting performance, memory usage and appropriate applications.

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.

FRONT | NEXT OUT A
WAITING B
REAR | NEW ENTRIES JOIN C
Enqueue at the rear; dequeue at the front. Logical order is A, B, 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.

Most recent 12 operations; contents front to rear
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.

Python deque documentation | Java ArrayDeque documentation

MATCH THE QUEUE IDEA

Terminology

Terminology

Queue

A collection where entries join at the rear and leave at the front under FIFO.

FIFO

First in, first out: the earliest remaining entry is removed next.

Front

The end containing the next entry to be removed.

Rear

The end where new entries join; pointer meaning depends on convention.

enqueue

Add an entry at the rear.

dequeue

Remove and return the front entry.

front operation

Read the front entry without removing it; often called peek.

isEmpty

Report whether no entries are waiting.

Underflow

Attempting a front access/removal when the queue is empty.

Overflow policy

The defined response to an enqueue beyond a stated capacity.

Bounded queue

A queue with a maximum number of waiting entries.

Backlog

Entries waiting to be served.

Spooling

Holding submitted work for a device or service to process later.

Deque

A double-ended queue supporting operations at both ends, usable under a FIFO policy.

Circular queue

A queue reusing a fixed indexed buffer through wraparound positions.

front_index

In this lesson’s circular model, the next read position.

rear_index

In this lesson’s circular model, the next write position.

Count

The current number of occupied logical queue entries.

Wraparound

Advancing past the final physical index back to the beginning.

Modulo

The remainder operation used here to wrap an index within capacity.

Logical order

The front-to-rear sequence of waiting entries, independent of their physical slot indexes.

Physical slot

One indexed location in the backing storage.

Linear queue

Here, a non-circular array queue whose indexes progress towards the final slot.

Linked queue

A queue of linked nodes with suitable front/rear references.

Shifting

Moving remaining array entries to earlier or later positions.

Producer

A source submitting work or entries to a queue.

Consumer

A process removing entries for handling.

In-service job

Work removed from waiting and currently being processed.

Priority queue

A structure selecting entries by a priority rule rather than ordinary FIFO.

Blocking enqueue

An enqueue that waits for room under the interface’s full-queue policy.

Questions

Questions

CHECK YOUR UNDERSTANDING

Select all correct choices. Each exact set earns one point.

1. Which describe FIFO?
2. Which distinguish front and dequeue?
3. Enqueue A,B; dequeue; enqueue C. Which follow?
4. Which describe empty/full cases?
5. Which describe Python implementations?
6. Which follow the circular convention?
7. Which describe wraparound?
8. Which describe printing accurately?
9. Which explain trade-offs?
10. Which distinguish bounded policies?

EXPLAIN AND COMPARE

Write your answers before revealing each sample.

1. Explain FIFO with three entries.

2. Distinguish enqueue, dequeue, front and isEmpty.

3. Trace enqueue A, enqueue B, front, dequeue, enqueue C, dequeue.

4. Construct a Python deque-backed queue interface in outline.

5. Explain the cost difference between list.pop(0) and a suitable deque front removal.

6. Describe the circular pointer convention and full/empty checks.

7. Trace the capacity5 wraparound sequence in section13.

8. Explain why a circular queue can reuse slots without shifting all entries.

9. Explain why FIFO fits print spooling, including a limitation.

10. Calculate backlog after four minutes under the stated three-arrival/two-service model.

11. Explain why a bounded deque’s automatic discard policy may be inappropriate for printing.

12. Compare fixed circular and linked queues in memory and operations.

EXPLAIN IT | HELP-DESK REQUESTS

A school help desk serves requests in accepted arrival order. Explain why a queue suits this rule, what enqueue/dequeue/front/isEmpty do, and how a bounded circular implementation can reuse freed slots. Include a memory limitation and explain why selecting a request does not prove it was resolved.

Reveal an answer outline

New requests join at rear and the earliest waiting request leaves from front. Front reads without removing; isEmpty checks whether any remain. A circular implementation wraps indexes and uses count for empty/full, reusing slots without shifting all entries. Its fixed capacity still needs an overflow policy. Resolution belongs to processing after dequeue and may fail or take time.

Flashcards

Flashcards

Click to flip. Select the ideas you need to revisit.

0 cards selected for revision.

Selections are kept while this page is open.

Workbook

Workbook

COMING SOON

The workbook for B2.2.4 Queues and FIFO is coming soon. Complete the matching task and written questions in your exercise book.