Loading...
1.4.2(b), 1.4.2(c), 2.3.1(e)Data StructuresCore
Linear, Circular and Priority Queues
Queues organise waiting work. State which item leaves next and how storage is managed before updating front and rear indices.
What you'll be able to do
- Trace enqueue and dequeue operations
- Use count-based circular queue rules
- Distinguish FIFO order from priority order
1
Define the queue contract
A normal queue removes items in first-in, first-out order. Enqueue adds at the rear; dequeue removes from the front. A bounded implementation must detect full storage before adding and an empty queue before removing. The item left in an old array slot after removal is not necessarily still logically present.
A simple linear array queue can run out of usable positions at its rear even when earlier positions were freed. Shifting remaining elements reclaims positions but costs work. A circular queue instead wraps indices to reuse the array while preserving the logical order.
2
State one circular convention precisely
For an array of capacity k, one clear model uses front as the next removal position, rear as the next insertion position and count as the number of items. Initially all are zero. Empty means count=0 and full means count=k. After insertion, rear=(rear+1) mod k and count increases.
After removal, front=(front+1) mod k and count decreases. In this count-based convention, front=rear can occur when empty or full, so indices alone do not distinguish them. Other implementations reserve a slot or use different rear meanings; do not combine their rules.
3
Handle priority deliberately
A priority queue removes the item with the most urgent specified priority rather than always the earliest arrival. Define whether smaller or larger priority numbers represent greater urgency. A tie-breaking rule, often arrival order, is also required for predictable behaviour.
Different representations move work between insertion and removal: an unsorted collection can insert cheaply but scan to remove the highest priority, while a heap supports efficient balanced costs. Choose from the required operations and scale rather than assuming every queue uses the same algorithm.
| Operation, capacity 4 | front | rear | count |
|---|---|---|---|
| Initial | 0 | 0 | 0 |
| Add A, B, C | 0 | 3 | 3 |
| Remove A, B | 2 | 3 | 1 |
| Add D, E | 2 | 1 | 3 |
4
Work through the problem
Attempt the task before opening its worked response. Record each change of state, explain the rule used, and check the result against the original requirements. Code examples labelled Python 3 use that language’s conventions; pseudocode states its own assumptions.
Example 1Using the table’s convention, which index stores E?
1D is inserted at rear 3, then rear wraps to 0.
2E is inserted at index 0, then rear becomes 1.
AnswerIndex 0.
Example 2Jobs A(priority 3) and B(priority 1) arrive in that order; lower numbers mean more urgent. Which leaves first?
1Priority order takes precedence over FIFO across different priorities.
2B has the higher urgency under the stated numbering rule.
AnswerB; equal priorities would need a tie rule.
Common mistakes to avoid
Combining full/empty rules from different queue conventions.
State the meanings of indices and count first.
Reading stale slots as current contents.
Follow the logical front and item count.
Key takeaways
- FIFO and priority queues have different removal rules.
- Circular indexing reuses bounded storage.
- Full and empty tests depend on the stated implementation.
Test yourself
Answer a few questions, then review anything you missed.
Next step
Browse practice topicsKeep practising
Start with the quiz above to check the key ideas. You can also choose another topic from the practice library.