What a Queue Is Good and Bad At
Chapter Forty-Six
Syllabus topic Module 1, "Queues: Queue ADT, Advantages & Disadvantages"
Pages 140 to 142 of 411
In one line
A queue is good at serving things in the order they arrived and bad at everything that requires knowing what is inside it, including which item is most urgent.
The advantages
1. Every operation is O(1), on the circular array and on the linked list alike. No searching, no shifting.
2. It is fair, in the precise sense. Every item is served after those that arrived before it and before those that arrived after. Nothing can overtake, and nothing can starve: an item's wait is bounded by the number of items ahead of it.
3. It matches anything that waits. Jobs for a processor, documents for a printer, packets for a link, requests for a server, people for a counter.
4. It decouples producer from consumer. One part of a program can add faster than another removes, for a while, and the queue absorbs the difference. That is what a buffer is.
5. It is the structure for breadth first work. Chapter 94 searches a graph with a queue and chapter 61 walks a tree level by level with one. Where a stack goes deep, a queue goes wide.
The disadvantages
1. Only the front is reachable. The second item cannot be read without removing the first.
2. No searching. A queue has no contains, for the same reason a stack has none.
3. Traversal destroys it, unless the items are put back at the rear as they are read, which needs the size to be known first or the walk never ends.
4. The array version needs a capacity in advance, and the circular implementation needs the care of chapters 44 and 45.
5. Fairness is not always what is wanted. This is the important one. A queue cannot let an urgent item go first, because the only thing it knows about an item is when it arrived.
That last disadvantage is worth demonstrating, because it is the bridge into Module 2.
Where fairness is the wrong rule
from collections import deque
# Jobs as (name, urgency), where 1 is most urgent.
arrivals = [("bulk print", 5), ("routine backup", 5), ("routine report", 5),
("ALARM", 1), ("another backup", 5)]
queue = deque()
for job in arrivals:
queue.append(job)
served, waited_before_alarm = [], 0
while queue:
name, urgency = queue.popleft()
served.append(name)
if name == "ALARM":
break
waited_before_alarm += 1
print("arrived in this order:")
for name, urgency in arrivals:
print(" %-16s urgency %d" % (name, urgency))
print()
print("a queue serves them in arrival order, so the ALARM was served")
print("after %d less urgent jobs had gone first." % waited_before_alarm)
print("order served:", served)
print()
print("the queue cannot do better, because the only thing it knows")
print("about a job is WHEN IT ARRIVED. Urgency is invisible to it.")What a Queue Is Good and Bad At
arrived in this order:
bulk print urgency 5
routine backup urgency 5
routine report urgency 5
ALARM urgency 1
another backup urgency 5
a queue serves them in arrival order, so the ALARM was served
after 3 less urgent jobs had gone first.
order served: ['bulk print', 'routine backup', 'routine report', 'ALARM']
the queue cannot do better, because the only thing it knows
about a job is WHEN IT ARRIVED. Urgency is invisible to it.The queue behaved perfectly correctly and produced the wrong result, because arrival order was the wrong rule for this problem. No implementation detail fixes that: it is the ADT.
What is needed is a structure that serves by priority rather than by arrival, and that is the priority queue of chapter 78, built on the heap of chapter 81. Module 1 ends here on purpose, and Module 2 opens by picking it up.
The table
| Queue | |
|---|---|
| enqueue, dequeue, front | O(1) |
| access item i | not possible |
| search | not possible without destroying it |
| find the most urgent | not possible |
| traverse | destroys it, unless items are re-enqueued |
| memory, circular array | fixed block, capacity reserved |
| memory, linked | one address per item |
Stack, queue and deque, in one line each
The three linear restricted structures of Module 1, as an examiner may ask them compared:
| Add at | Remove from | Rule | |
|---|---|---|---|
| Stack | one end | the same end | last in, first out |
| Queue | one end | the other end | first in, first out |
| Deque | either end | either end | both, and neither |
Quick revision
- Advantages: all operations O(1); fair, with bounded waiting and no starvation; matches anything that
waits; decouples producer from consumer; the structure for breadth first work.
- Disadvantages: only the front is reachable; no search; traversal destroys it; the array version needs
a capacity; and it cannot serve by urgency.
- The last one is an ADT limitation, not an implementation one: a queue knows only when an item arrived.
- Demonstrated: an alarm arriving fourth is served fourth, behind three routine jobs.
- The fix is the priority queue of chapter 78, which is where Module 2 begins.
Test yourself
1. Give three advantages of a queue. Every operation is O(1); it is fair, with each item's wait bounded by the number ahead of it and no starvation; and it decouples a producer from a consumer, which is what a buffer does.
2. Give three disadvantages. Only the front is reachable; there is no search; and traversal destroys the queue unless items are re-enqueued as they are read.
3. Why can a queue not serve an urgent item first? Because the only thing it knows about an item is when it arrived. Urgency is not part of the ADT, so no implementation can recover it.
What a Queue Is Good and Bad At
4. In the run, how many jobs went before the ALARM, and was the queue faulty? Three. The queue was not faulty; it applied arrival order correctly, and arrival order was the wrong rule for the problem.
5. What structure fixes that, and where is it built? The priority queue, chapter 78, implemented with the heap of chapter 81.
6. Compare the stack, queue and deque in one line each. A stack adds and removes at one end (last in, first out); a queue adds at one end and removes at the other (first in, first out); a deque adds and removes at either end.
The rest of this subject
These notes are cut from the University's printed syllabus. Open the syllabus itself, or the past papers, for the same subject.