Card 07/ 08
Practice: Naming the Set or Queue for Five Requirements
Seen-before checks in three orders, the most urgent job, and an undo history.
Sets are chosen by the iteration order you need, and queues by which element should come out next. For each requirement below, name the collection and say what the requirement rules out, all five before you open the answer.
| The requirement | |
|---|---|
| 1 | Record which customer references have been seen, and ask often |
| 2 | The same, but the report must list them in the order they arrived |
| 3 | The same, but the report must list them alphabetically |
| 4 | Hold work items and always take the most urgent one next |
| 5 | Undo history: the last action taken is the first one undone |
The five answers, and what each requirement rules out
| Use | What the requirement ruled out | |
|---|---|---|
| 1 | HashSet | A list, because contains on one is a walk |
| 2 | LinkedHashSet | HashSet, whose iteration order is not promised |
| 3 | TreeSet | Both hash sets; or sort a copy at the end, if adding is the frequent operation |
| 4 | PriorityQueue | ArrayDeque, which has no notion of urgency |
| 5 | ArrayDeque used as a stack | Stack, which is synchronised and exposes Vector |
The third has two defensible answers, which is why it is here. A TreeSet keeps order on every add; sorting a HashSet once at the end does the work only once. Which wins depends on how many adds there are per report.
← → move through sections and cards