A-Level Computer Science / Unit 10: Organising Data in Programs

10.4.3 Queues: Enqueue, Dequeue and Circular Storage

🔒 Lesson slides are available to signed-in users. Sign in

10.4.3 Queues: Enqueue, Dequeue and Circular Storage

A queue stores items so that the item waiting longest is processed first. New items enter at the rear, while removals take place at the front. This produces first in, first out behaviour.

This page develops queue operations and explains why circular storage can use a fixed-size array more effectively than a simple arrangement that repeatedly shifts every remaining item. A more detailed comparison of array implementations appears in 10.4.5 Implementing ADTs with Arrays.

By the end of this section, you should be able to:

  • Describe a queue as an Abstract Data Type with front and rear access rules.
  • Explain the meaning of first in, first out (FIFO).
  • Apply enqueue, dequeue and peek-front operations.
  • Trace the logical order of items after a sequence of queue operations.
  • Explain the weakness of a shifting linear-array queue.
  • Trace front and rear movement in a circular queue.
  • Recognise queue underflow and overflow.
  • Justify the use of a queue for an appropriate situation.
Syllabus scope: students should be able to use a queue to add, inspect, edit and remove data, and describe an array-based implementation. Writing complete queue implementation pseudocode is not required.

The Queue Rule

A queue has two active ends. New items join at the rear, while the item at the front is the next one available for removal. Items between these two positions retain their relative order.

FIFO: first in, first out. The earliest item added is the first item removed.
Front / next out
Request 42
Request 57
Request 63
Request 81
Rear / new items enter

Request 42 entered before the other requests, so it is the next item that a dequeue operation removes.

Common misconception: a normal queue does not remove the newest item first. That behaviour belongs to a stack.

Enqueue, Dequeue and Peek Front

Operation Purpose Effect on the queue
Enqueue Add a new item. The item becomes the new rear item.
Dequeue Remove and return the front item. The next waiting item becomes the new front.
Peek front Inspect the front item without removing it. The contents and order remain unchanged.
IsEmpty Test whether no item is waiting. Returns a Boolean result.
IsFull Test whether a fixed-capacity implementation has no free slot. Returns a Boolean result.
Exam tip: say where each operation acts: enqueue adds at the rear, while dequeue removes from the front.

Tracing Queue Operations

Start with an empty queue and apply these operations: 

ENQUEUE "Scan 14"
ENQUEUE "Scan 27"
ENQUEUE "Scan 35"
DEQUEUE
ENQUEUE "Scan 46"
PEEK FRONT
Step Operation Queue from front to rear Value returned
1 Enqueue Scan 14 Scan 14 —
2 Enqueue Scan 27 Scan 14, Scan 27 —
3 Enqueue Scan 35 Scan 14, Scan 27, Scan 35 —
4 Dequeue Scan 27, Scan 35 Scan 14
5 Enqueue Scan 46 Scan 27, Scan 35, Scan 46 —
6 Peek front Scan 27, Scan 35, Scan 46 Scan 27
The final peek returns Scan 27, but the item remains at the front.
Record a queue consistently from front to rear. Label this direction in a trace so that the removal order is unambiguous.

A Simple Linear-Array Queue

One possible implementation stores the front item at index 0. New values are placed after the current rear item.

Index 0 1 2 3 4 5
Before dequeue R42 R57 R63 R81 — —
After dequeue and shift R57 R63 R81 — — —

Keeping the front fixed at index 0 means every remaining item may need to move left after a dequeue. The queue still behaves correctly, but repeated shifting creates unnecessary work.

A linear array does not have to shift values in every implementation. This is only one simple design. Moving the front pointer instead leads naturally to circular storage.

Circular Storage

A circular queue treats the final array position as if it were followed by index 0. When a dequeue frees an early slot, a later enqueue can reuse that slot after the rear reaches the end of the array.

Circular queue: a queue stored in a fixed-size array where the front and rear positions can wrap from the last index back to the first.
Index 0 1 2 3 4 5 6
Stored value Job 64 Job 71 — — — Job 52 Job 58
Logical role third rear free free free front second

Although the values are split across the end and beginning of the array, their logical FIFO order is: Job 52 → Job 58 → Job 64 → Job 71.

Array index order is not always queue order. In a wrapped queue, begin at the front pointer and follow the positions circularly until the rear is reached.
A conceptual pointer update can be written as: NextPosition = (CurrentPosition + 1) MOD Capacity. The modulo operation sends the position back to 0 after the final index.

Empty and Full Queues

Condition Meaning Unsafe operation Resulting problem
Empty queue No front item is available. Dequeue or peek front Underflow
Full fixed-capacity queue Every storage slot is occupied. Enqueue Overflow
In a circular queue, front and rear positions alone can sometimes be ambiguous. An implementation may also store an item count or reserve one unused slot to distinguish empty from full. The widget uses an explicit count.

Editing Data in a Queue

The front item is directly available for inspection or removal. An item deeper in the queue is normally not directly accessible through the queue interface.

Requested change Possible directly? Explanation
Inspect the next item Yes Use peek front.
Remove the next item Yes Use dequeue.
Add a new waiting item Yes Use enqueue at the rear.
Edit an arbitrary middle item Not normally Earlier items would need to be removed first, or another structure should be used.
Remove the newest item first No That would break FIFO behaviour and suggests a stack instead.
A queue is a poor choice when a program frequently needs direct access to arbitrary waiting items.

When Is a Queue Suitable?

Situation Why a queue fits
Print jobs waiting for a shared printer Jobs should normally be processed in submission order.
Packets waiting in a network buffer Earlier arrivals are forwarded before later arrivals.
Keyboard events awaiting processing Events should be handled in the order they occurred.
Requests waiting for a service worker The longest-waiting request should be selected next.
Breadth-first exploration Earlier discovered locations are explored before later ones.
Strong justification: “A queue is suitable because jobs must be removed in the same order in which they arrive, matching FIFO behaviour.”
Weak justification: “A queue is suitable because printers use queues.” State the required order, not only a familiar example.

Interactive: Queue and Circular Storage Lab

Switch between linear and circular storage. Enqueue, dequeue and peek to observe FIFO behaviour, shifting, pointer movement, wrap-around, underflow and overflow.

Physical array: capacity 7 4 items
Front → dequeue Enqueue ← rear
Queue state
Front pointer 0
Rear pointer 3
Front item Request 42
Last returned None
Is empty? FALSE
Is full? FALSE
Logical order: front to rear Request 42 → Request 57 → Request 63 → Request 81
The front item is Request 42. A dequeue removes it first.
Operation history

    Common Mistakes and Misconceptions

    • Confusing FIFO with LIFO.
    • Enqueuing at the front instead of the rear.
    • Dequeuing from the rear instead of the front.
    • Saying that peek front removes an item.
    • Reading a wrapped queue in ordinary index order rather than from its front pointer.
    • Forgetting that a circular rear can move from the final index back to index 0.
    • Assuming that every linear queue must shift data.
    • Trying to dequeue or peek an empty queue.
    • Trying to enqueue into a full fixed-capacity queue.
    • Justifying a queue without mentioning arrival order or FIFO.

    Practice

    Task 1: Basic trace

    Start with an empty queue and apply: ENQUEUE 18, ENQUEUE 42, ENQUEUE 27, DEQUEUE, ENQUEUE 63.

    1. State the final queue from front to rear.
    2. State the value returned by dequeue.
    3. State the final front and rear items.

    Task 2: Peek or dequeue?

    A system must display the next print job without removing it. Name the operation and explain why it is appropriate.

    Task 3: Read a wrapped queue

    A circular queue of capacity 6 has its front at index 4 and rear at index 1. The occupied values are:

    • index 4: P
    • index 5: Q
    • index 0: R
    • index 1: S
    1. Write the queue from front to rear.
    2. Which item is dequeued next?
    3. At which index should the next item be enqueued?

    Task 4: Choose and justify

    Decide whether a queue is suitable for each situation.

    1. Processing support requests in arrival order.
    2. Undoing the newest drawing action.
    3. Forwarding network packets in arrival order.
    4. Editing any waiting item directly by its numbered position.

    Task 5: Underflow and overflow

    A fixed-capacity queue can store five values.

    1. What happens if dequeue is requested when the queue is empty?
    2. What happens if enqueue is requested when five values are already stored?
    3. Name both error conditions.

    Review

    Question Strong answer should include
    How does a queue organise access? Items enter at the rear and leave from the front.
    What does FIFO mean? The earliest item added is removed first.
    What does enqueue do? Adds a new item at the rear.
    What does dequeue do? Removes and returns the front item.
    What does peek front do? Returns or inspects the front item without removing it.
    Why use circular storage? To reuse freed array slots and avoid shifting all remaining values.
    How is a wrapped queue read? Begin at the front pointer and follow positions circularly to the rear.
    How should a queue choice be justified? By explaining that items must be processed in arrival order.
    Final exam tip: connect both ends to FIFO: enqueue adds at the rear, dequeue removes from the front, so earlier arrivals leave first.