Queues

OCR H446 references: 1.4.1(a), 1.4.1(b) and 2.2.1(f)

Many systems need to process work in the order it arrived. Songs requested for a student radio show, videos waiting to be rendered, print jobs sent to one printer and packets waiting for a network device all have an arrival order that matters.

A queue preserves that order. This worksheet develops the idea slowly before you trace pointers and implement a fixed-capacity linear queue in Python.

By the end, you should be able to:

• explain FIFO, enqueue and dequeue
• use head and tail pointers
• detect overflow and underflow
• compare a queue with a stack
• implement a queue without shifting every stored item

Process the oldest waiting item first

Imagine that four videos are submitted to a school media server for rendering:

interview.mp4, trailer.mp4, highlights.mp4, credits.mp4

If the server behaves fairly, interview.mp4 is processed first because it arrived first. New jobs join at the back; completed jobs leave from the front.

This is first in, first out, or FIFO.

Queue operations

• enqueue(item) adds a new item at the back, also called the tail.
• dequeue() removes and returns the item at the front, also called the head.

After the four videos above are enqueued, one dequeue returns interview.mp4. The next dequeue returns trailer.mp4.

Error conditions

In a fixed-capacity implementation:

• overflow occurs when an enqueue is attempted but there is no available position
• underflow occurs when a dequeue is attempted but no items are waiting

The program should detect these cases before accessing the array.

Head and tail pointers

This worksheet uses a simple linear queue:

• head is the index of the next item to remove
• tail is the index of the next position in which to store an item

If head == tail, there are no active items waiting.

OCR-style pseudocode

function dequeue()
    if head = tail then
        return null
    endif
    value = queue[head]
    head = head + 1
    return value
endfunction

Python equivalent

def dequeue():
    global head
    if head == tail:
        return None
    value = queue[head]
    head += 1
    return value

Only the head pointer moves. The remaining items do not need to be shifted towards index zero.

A limitation of this simple version

Once tail reaches the end of the array, this linear queue cannot reuse positions before head, even if earlier items have been removed. A circular queue can reuse them, but circular implementation is not the main focus of this worksheet. Here, the aim is to understand FIFO behaviour and the two-pointer model clearly.

Checkpoint: identify the active part of the queue

The physical array may still display an old value before head, but that value is no longer logically waiting. The active queue consists of the positions from index head up to, but not including, index tail.

For example, if head = 2 and tail = 5, the active items are at indices 2, 3 and 4. The next dequeue reads index 2; the next enqueue writes index 5.

Guided trace

Predict the service order before running the code. Record head, tail and the returned item after each operation. Then add one more arrival and one more service operation.

Independent processing task

Use a head index to process the supplied names in FIFO order:

1. Start head at zero.
2. While head is less than the list length, append waiting[head] to served.
3. Increase head.

Do not use pop(0). It produces the correct order for a small Python list, but it shifts all remaining elements and hides the pointer behaviour this task is designed to practise.

Independent task: fixed-capacity linear Queue class

Complete a queue with a fixed list:

• enqueue(value) stores at tail, advances tail and returns True.
• If tail has reached the capacity, it returns False.
• dequeue() returns None when head == tail.
• Otherwise it returns the head item and advances head.

The supplied operations check normal FIFO behaviour, overflow and underflow. This is a linear queue, so positions before head are not reused.