A normal queue is not clinically sufficient
First-come, first-served is fair only when every waiting case has equal urgency. Emergency departments must allow a later critical patient to be seen before an earlier standard patient. However, patients with equal clinical priority should retain their arrival order.
Register
Create a token and place the patient correctly.
Call next
Remove and free the highest-priority waiting node.
Report
Show service order and counts by category.
Define priority before implementation
| Numeric priority | Label | Ordering meaning |
|---|---|---|
| 1 | Critical | Served before every other category |
| 2 | Emergency | Served after Critical |
| 3 | Urgent | Served after Emergency |
| 4 | Standard | Served after all urgent categories |
Smaller numeric value means higher urgency. Within the same value, smaller arrivalOrder is served first. Therefore the complete key is:
ordering key = (priority ascending, arrivalOrder ascending)
Stability
A priority queue is stable when equal-priority items preserve insertion order. Stability prevents a newly registered Urgent patient from overtaking Urgent patients already waiting.
Patient node and queue state
Patient = { token, name, age, priority, arrivalOrder, *next }
Queue state = { *front, nextToken, nextArrival }| Member | Role | Invariant |
|---|---|---|
| token | Public queue identifier | Unique and increasing |
| priority | Urgency rank | 1 through 4 |
| arrivalOrder | Fairness tie-breaker | Unique and increasing |
| next | Links service order | Final node points to NULL |
| front | Next patient to call | Always best ordered node |
Rules that make every dequeue correct
- Priorities never decrease while traversing from front.
- For equal priorities, arrivalOrder strictly increases.
- Every allocated waiting patient is reachable from front exactly once.
- front is NULL if and only if the queue is empty.
- Calling next removes exactly front and advances to the old front’s next.
P1, arrival 4
P2, arrival 2
P3, arrival 1
P4, arrival 3
Find the first patient who should come later
comesBefore(a,b) compares priority first and arrival order second. Enqueue walks while the new patient does not come before the current node.
- Start with
position = &front. - While a node exists and the new patient belongs after it, advance to the address of its next link.
- Point the new node to the node currently stored at position.
- Store the new node at position.
while (*position != NULL && !comesBefore(patient, *position))
position = &(*position)->next;
patient->next = *position;
*position = patient;This pointer-to-pointer form handles insertion at front, middle and end without three separate code blocks.
Compiler-ready C11 program
Loading source…Design reading guide
Comparator
Understand comesBefore before examining insertion.
Queue mutation
Compare enqueue’s O(n) work with callNext’s O(1).
Lifetime
Registration allocates; service or shutdown frees.
Trace priority and stability together
- A arrives first.
- B arrives with higher priority.
- B is inserted at front.
- C has equal priority to B.
- Stable ordering is preserved.
- D arrives last but is most urgent.
- D moves to front by priority.
- The critical patient is served.
- Fairness resolves equal priority.
Press Next to begin.
Test urgency, fairness and lifetime
Test 1 — Different priorities
Test 2 — Equal-priority stability
Test 3 — New highest priority
Test 4 — Empty dequeue
Test 5 — Validation
Test 6 — Complete cleanup
Where should ordering work happen?
| Operation | Sorted linked queue | Binary heap | Unsorted list |
|---|---|---|---|
| Register | O(n) | O(log n) | O(1) |
| View/call best | O(1) | O(1)/O(log n) | O(n) |
| Display service order | O(n) | Requires ordered extraction | Requires sorting |
| Memory locality | Lower | High | Lower |
The linked queue is appropriate for teaching and moderate waiting lists because Call Next is simple and display order is already correct. At large scale, a stable heap or four FIFO queues—one per category—would reduce insertion cost.
Check and extend the design
What makes this priority queue stable?
Why is Call Next O(1)?
Extension challenges
- Implement four separate FIFO queues and compare complexity.
- Add controlled priority reassessment while retaining the original arrival order.
- Estimate waiting time from average consultation duration.
- Add cancellation by token and test front/middle/tail removal.
- Prevent starvation by gradually increasing long-waiting patients’ effective priority.
Explain fairness and performance
Why not use a normal FIFO queue?
FIFO cannot allow a critical later arrival to overtake a standard earlier arrival. Clinical urgency is the primary ordering requirement.
How is stable priority maintained?
Comparison uses priority first and monotonically increasing arrivalOrder second, so a new equal-priority patient is inserted after existing peers.
What is starvation?
Low-priority patients may wait indefinitely if higher-priority patients keep arriving. Aging or service quotas can mitigate this.
Why use pointer-to-pointer insertion?
It modifies the exact link that must point to the new node, whether that link is front or a predecessor’s next field.
Would a heap always be better?
No. A heap improves insertion asymptotically but complicates stable ties and ordered display. Choice depends on queue size and operation frequency.
Correct ordering requires an explicit comparator
A priority queue is not merely “sorted by priority”. This system becomes correct only when the ordering key contains both urgency and arrival sequence, validation protects the domain, and allocation ownership covers registration, service and shutdown.