Loading…
Free A-Level Computer Science guide
A priority queue chooses by service priority rather than arrival alone. Declare which number means higher priority and how ties are resolved before tracing an operation.
Content owner: Michael Print · Written for A-Level learners · Checked against official specifications
Explore the idea
Compare FIFO with priority ordering. Smaller priority numbers are served first; equal priorities retain arrival order. Capacity is five items in this model.
A priority queue is an abstract contract for selecting the next item by priority. In this guide a smaller number has higher service priority and equal priorities use arrival order. A FIFO queue instead selects the earliest remaining arrival.
Check capacity before insertion and emptiness before removal. Peek returns the next item without removing it. A bounded array, sorted list or heap can implement a priority queue, with different costs and representation details.
AQA 7517 · 4.2.1.4; 4.2.2.1; 4.2.3.1 (peek comparison)
Useful foundations
By the end, you should be able to
AQA: the priority-queue contract is developed alongside existing linear/circular queue foundations. Smaller numeric priority is higher here, with FIFO ties. Peek is taught as a non-removing observation, consistent with the stack comparison.
Shared foundations and optional extensions are labelled separately; this page does not claim complete coverage of the qualification.
Each item carries a payload and priority. If a question uses larger numbers for higher priority, reverse the comparison; the numeric convention is not universal. Equal priorities also need a stated policy, such as stable arrival order.
An implementation might keep an unsorted list and search for the best item at removal, or keep ordered storage to speed that selection. A heap maintains an ordering invariant without globally sorting every item. None changes the abstract service rule.
For a fixed capacity, test full before adding. A rejected add leaves every existing item intact. Test empty before remove or peek; do not interpret a stale array cell as a valid item after the logical queue becomes empty.
Peek observes the selected item; remove both returns it and removes it from the structure. An array representation may shift cells or update pointers, while a linked representation adjusts references. The logical count remains distinct from unused capacity.
A printer may use FIFO for fairness among ordinary jobs, but urgent operational tasks may justify priorities. Equal-priority FIFO can preserve predictable arrival order within each service group.
A continuous stream of urgent work can starve lower-priority items. Ageing may gradually raise waiting items' effective priority. A priority rule does not automatically guarantee fairness or the smallest average waiting time.
A preallocated array has a declared capacity and predictable storage footprint. A linked structure can allocate additional nodes, but each node needs link storage and allocation can fail. Dynamic does not mean unbounded memory.
For an unsorted list, selecting the best item is linear in its length. Maintaining sorted order can move that work to insertion. Complexity depends on implementation, so name the operation and representation rather than claiming every priority queue has one cost.
Worked example
4 original questions total 13 marks. Attempt each before opening the independently written indicative marking guidance.
Capacity 4; lower number means higher priority; FIFO ties. Arrivals are A:2, B:1, C:1. State the result of peek and the removal order, and give the count after peek.
Indicative answer
A fixed queue has three items at capacity 3. Describe a safe insertion attempt, then the check needed before removing from an empty queue.
Indicative answer
Compare an unsorted array implementation with a sorted list for selecting and adding an item; explain why ADT and implementation are different concepts.
Indicative answer
Explain starvation in a priority queue and one possible mitigation.
Indicative answer
This guide addresses AQA 7517 4.2.1.4; 4.2.2.1; 4.2.3.1 (peek comparison). Check your examination year and the complete specification for the assessment scope.
These are independently written explanations and practice questions. CompSciTutoring.co.uk is not affiliated with or endorsed by an examination board. The marking guidance is indicative; always check the syllabus for your examination year.
Found an error? Email a correction.
Use the free examples first, then explore one-to-one tuition if guided practice would help.