Queues — AQA A-Level Computer Science

A queue is a First-In, First-Out (FIFO) abstract data structure where elements are added at the rear and removed from the front. In AQA A-Level Computer Science, students must master linear, circular, and priority queues, including pointer manipulation, overflow and underflow conditions, and algorithm implementation.

Queues explained

A queue is a first-in, first-out (FIFO) data structure: the item that has waited longest is the next one to be removed.

Read the full explanation

Adding an item, often called enqueue, places a new element at the rear (tail) of the queue. The operation needs a pointer or index that marks where the next item should go, and that pointer moves forward each time an item is added. For example, if a queue holds customers A, B and C with C at the rear, adding D places D after C and leaves A at the front, unchanged. Students should be able to trace this on a diagram, showing how the rear pointer changes and why the front pointer does not move. Recognising that adding affects the rear, and not the front, is the key idea the question is testing. Adding to a full queue must be handled, typically by reporting an overflow condition rather than overwriting existing data.

Your focus

add an item

Which command word is this?

Follow the execution of an algorithm step by step, completing a trace table to record changing variable values, pointer positions, and outputs precisely.

Queues exam tips

Topic Overview

A queue is an abstract data structure that operates under the First-In, First-Out (FIFO) discipline. Elements enter the structure at the rear (enqueue) and exit from the front (dequeue), maintaining the chronological order of arrival. Queues are fundamental to operating systems and network protocols, managing print buffers, keyboard inputs, CPU process scheduling, and packet routing.

Within the AQA specification, students study linear queues, circular queues, and priority queues. Mastering both static array-based and dynamic pointer-based implementations is critical, as exam questions frequently require students to dry-run pointer values, manipulate modulo logic, evaluate time complexities, and write robust algorithmic code.

Key Concepts

→FIFO (First-In, First-Out) discipline: The earliest added item is always the first to be extracted.
→Linear Queue: Static array where pointers shift forward; suffers from memory waste as deallocated spaces cannot be reused without expensive element shifts.
→Circular Queue: Reuses vacated front indices by wrapping the rear and front pointers around to index 0 using modulo arithmetic.
→Priority Queue: Elements are removed based on associated priority rankings rather than purely on arrival order; higher-priority items are placed ahead of lower-priority ones.
→Pointer manipulation and boundary checks: Proper handling of front and rear index updates alongside explicit checks for overflow and underflow.

Marking Points

Places the new item at the rear (tail) of the queue.
Updates the rear pointer or index so it refers to the new last position.
Leaves the front of the queue and the existing items in their original order.
Checks for a full queue first and reports overflow instead of overwriting data.

Examiner Tips

💡Identify the rear pointer in any diagram and confirm which end the new item joins.
💡Trace a short example step by step, writing the pointer values after each operation.
💡Remember that FIFO means the front item is removed first, so adding should never change the front item.
💡State your pointer conventions at the start of algorithm questions if not given (e.g. clarifying whether rear points to the current occupied cell or the next free cell).
💡Always use the MOD operator for circular queue pointer increments rather than relying solely on IF statements to demonstrate concise, elegant algorithmic thinking.
💡Check whether the question specifies a static array or a dynamic linked list, as dynamic queues cannot suffer from overflow (barring total system memory exhaustion).

Common Mistakes

Inserts the new item at the front of the queue, which makes the structure behave like a stack. Correct by always adding at the rear.
Moves the front pointer when adding, which removes or skips an item. Correct by changing only the rear pointer.
Ignores the full-queue condition, so data is overwritten. Correct by testing for overflow before adding.
Believing that DEQUEUE physically wipes the data from array memory: The data remains in the underlying array, but the front pointer advances and the count decreases, rendering that slot logically vacant.
Confusing queues (FIFO) with stacks (LIFO): Students often mistakenly pop the most recent item from a queue instead of extracting from the front pointer.
Assuming priority queues violate FIFO completely: Within identical priority levels, a priority queue still processes elements in strict FIFO order.

Revision Plan

1Day 1-2: Review core definitions of FIFO, linear queues, circular queues, and priority queues; practice drawing manual queue operations.
2Day 3-4: Work through pointer arithmetic using MOD and practice dry-run trace tables with wrap-around boundaries.
3Day 5-6: Write and debug pseudocode implementations for ENQUEUE, DEQUEUE, isEmpty, and isFull.
4Day 7: Complete past AQA exam questions covering algorithm design and comparisons between array-based and linked-list queues.

Exam Question Types

📋Trace tables: Dry-running pointer values (front, rear, size) and array cell contents across a sequence of enqueue and dequeue calls.
📋Algorithm implementation: Writing pseudocode functions to enqueue or dequeue items with boundary validation.
📋Evaluation and comparison: Discussing trade-offs between static linear queues, circular queues, and linked-list dynamic queues in terms of time and space complexity.

Command Word Expectations (AQA)

Trace

Follow the execution of an algorithm step by step, completing a trace table to record changing variable values, pointer positions, and outputs precisely.

Explain

Provide clear reasoning detailing how or why a mechanism works, using precise technical terms such as FIFO, modulo arithmetic, or underflow.

Write an algorithm

Produce complete, syntactically coherent pseudocode or structured English that handles inputs, processing, edge cases (overflow/underflow), and pointer updates.

How Students Lose Marks (Examiner Pitfalls)

Pitfall: Failing to check for queue overflow or underflow before performing enqueue or dequeue operations.

❌ Weak Answer (Loses Marks):To enqueue, just increment the rear pointer and put the item in the array.

Example improved answer:Check if the queue is full by testing if currentSize equals MAX_SIZE. If full, report a queue overflow error; otherwise, increment the rear pointer using rear = (rear + 1) MOD MAX_SIZE, insert the item at array[rear], and increment currentSize by 1.

Examiner Tip: Always write explicit boundary checks for empty and full states in algorithm questions to secure top-band marks.

Pitfall: Confusing the mechanics of linear queues with circular queues when addressing memory reuse.

❌ Weak Answer (Loses Marks):Linear queues free up space when you dequeue an item so you can always add more items.

Example improved answer:In a static linear array implementation, dequeuing simply advances the front pointer, leaving previously occupied memory inaccessible; without shifting elements at O(n) cost, the queue will report overflow once the rear reaches the upper bound even if early slots are empty. A circular queue overcomes this by wrapping pointers using modulo arithmetic.

Examiner Tip: Distinguish between static array-based queues and dynamic linked-list implementations when discussing capacity and memory reclamation.

Step-by-Step Worked Solutions

Question: A circular queue of capacity 5 is implemented using an array Q[0..4], with pointers front = 0, rear = -1, and size = 0. Trace the values of front, rear, size, and array contents after executing: ENQUEUE('A'), ENQUEUE('B'), DEQUEUE(), ENQUEUE('C'), ENQUEUE('D'), ENQUEUE('E'), ENQUEUE('F').

1.Step 1: Identify initial state: front = 0, rear = -1, size = 0, array = [empty, empty, empty, empty, empty].
2.Step 2: ENQUEUE('A'): rear = (rear + 1) MOD 5 = 0; Q[0] = 'A'; size = 1.
3.Step 3: ENQUEUE('B'): rear = (rear + 1) MOD 5 = 1; Q[1] = 'B'; size = 2.
4.Step 4: DEQUEUE(): Read Q[front] ('A'); front = (front + 1) MOD 5 = 1; size = 1.
5.Step 5: ENQUEUE('C'): rear = (rear + 1) MOD 5 = 2; Q[2] = 'C'; size = 2.
6.Step 6: ENQUEUE('D'): rear = (rear + 1) MOD 5 = 3; Q[3] = 'D'; size = 3.
7.Step 7: ENQUEUE('E'): rear = (rear + 1) MOD 5 = 4; Q[4] = 'E'; size = 4.
8.Step 8: ENQUEUE('F'): rear = (rear + 1) MOD 5 = 0; Q[0] = 'F'; size = 5 (Queue is now full).

Final Answer: Final state: front = 1, rear = 0, size = 5. Array contents: Q[0] = 'F', Q[1] = 'B', Q[2] = 'C', Q[3] = 'D', Q[4] = 'E'.

Question: Write pseudocode for a procedure called DEQUEUE that removes and returns an element from a circular queue implemented using array data[0..MAX-1], integer pointers front and rear, and an integer variable count.

1.Step 1: Check underflow condition by checking if count == 0.
2.Step 2: If empty, output an error message or return a null/error sentinel value.
3.Step 3: Extract the element at data[front] into a local variable item.
4.Step 4: Update the front pointer using front = (front + 1) MOD MAX.
5.Step 5: Decrement count by 1 and return item.

Final Answer: FUNCTION DEQUEUE() IF count == 0 THEN REPORT 'Queue Underflow' RETURN NULL ELSE item = data[front] front = (front + 1) MOD MAX count = count - 1 RETURN item ENDIF ENDFUNCTION

Active Recall Memory Test

What formula updates the rear pointer in a circular queue of size N?

Key Fact: rear = (rear + 1) MOD N

What condition represents queue underflow in a queue using a size counter?

Key Fact: size == 0 (or front == -1 in some single-pointer conventions)

In what order are elements with identical priority served in a priority queue?

Key Fact: First-In, First-Out (FIFO) order based on arrival time.

Frequently Asked Questions

What is the difference between a linear queue and a circular queue?

A linear queue allocates items sequentially in an array, meaning that as items are dequeued, earlier memory positions become inaccessible unless all items are shifted back at an O(n) time cost. A circular queue resolves this limitation by wrapping front and rear pointers back to index 0 using modulo arithmetic. This allows vacated slots to be reused efficiently without moving elements.

What happens when you try to dequeue from an empty queue?

Attempting to remove an item from an empty queue triggers a condition called queue underflow. In robust software, the dequeue algorithm tests whether the queue is empty before executing. If empty, it flags an error or returns a sentinel value rather than decrementing pointers into invalid memory addresses.

Why is a circular queue more efficient than a linear queue for arrays?

In a static linear queue, keeping the front at index 0 requires every remaining element to shift forward by one slot on each dequeue, leading to O(n) time complexity. Alternatively, leaving elements unshifted wastes space and causes false overflows. A circular queue achieves O(1) time complexity for both enqueue and dequeue operations by simply updating index pointers using modulo arithmetic.

How does a priority queue differ from a standard queue?

In a standard queue, items are dequeued strictly according to their arrival time. In a priority queue, each item has an associated priority value, and elements with higher priority are dequeued before lower-priority elements. If two elements share the same priority, they are dequeued in standard FIFO order.

What is the Big-O time complexity of queue operations?

For circular arrays and linked lists, both ENQUEUE and DEQUEUE operate in O(1) constant time because pointers directly target the insertion and removal indices. In an unoptimised linear array queue where elements shift after removal, DEQUEUE operates in O(n) linear time. Priority queues typically take O(log n) time for insertion using a binary heap, or O(n) using an unsorted or linear array.

Queues explained

Your focus

Which command word is this?

Queues exam tips

More AQA A-Level Computer Science topics

Cookies on MasteryMind