## Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

#### Before You Begin

Section 0: 6 chapters

#### Section I: Introduction

Section 1: 3 chapters

#### Section II: Elementary Data Structures

Section 2: 3 chapters

#### Section IV: Sorting Algorithms

Section 4: 5 chapters

#### Section V: Graphs

Section 5: 5 chapters

# 15. Chapter 15 Solutions Written by Jonathan Sande

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

## Solution to Challenge 1

Start with the following `Person` type:

``````class Person implements Comparable<Person> {
Person({
required this.name,
required this.age,
required this.isMilitary,
});

final String name;
final int age;
final bool isMilitary;

@override
int compareTo(other) => throw UnimplementedError();
}
``````

Since a priority queue needs to compare elements, `Person` also needs to be `Comparable`.

Given a list of people on the waitlist, you would like to prioritize the people in the following order:

1. Military background.
2. Seniority, by age.

The key to solving this problem is to finish implementing the `compareTo` method in `Person` so that you can use a priority queue to tell you the order of people on the waitlist. Replace `compareTo` with the following code:

``````@override
int compareTo(other) {
if (isMilitary == other.isMilitary) {
return age.compareTo(other.age);
}
return isMilitary ? 1 : -1;
}
``````

If two people have the same military background, then age is used to see who has the highest priority. But if the military background is different, then the one having a military background is prioritized.

Before you test your implementation out, override `toString` so that `Person` is printable:

``````@override
String toString() {
final military = (isMilitary) ? ', (military)' : '';
return '\$name, age \$age\$military';
}
``````

Import the `PriorityQueue` that you made earlier in the chapter if you haven’t already. Then run the following example in `main`:

``````final p1 = Person(name: 'Josh', age: 21, isMilitary: true);
final p2 = Person(name: 'Jake', age: 22, isMilitary: true);
final p3 = Person(name: 'Clay', age: 28, isMilitary: false);
final p4 = Person(name: 'Cindy', age: 28, isMilitary: false);
final p5 = Person(name: 'Sabrina', age: 30, isMilitary: false);

final waitlist = [p1, p2, p3, p4, p5];

var priorityQueue = PriorityQueue(elements: waitlist);
while (!priorityQueue.isEmpty) {
print(priorityQueue.dequeue());
}
``````

You should see the output below:

``````Jake, age 22, (military)
Josh, age 21, (military)
Sabrina, age 30
Clay, age 28
Cindy, age 28
``````

## Solution to Challenge 2

To make a list-based priority queue, all you have to do is implement the `Queue` interface. Instead of a heap, you use a list data structure.

``````abstract interface class Queue<E> {
bool enqueue(E element);
E? dequeue();
bool get isEmpty;
E? get peek;
}
``````

### Getting Started

First, add the following code to a project that contains the `Queue` interface:

``````enum Priority { max, min }

class PriorityQueueList<E extends Comparable<E>> implements Queue<E> {
PriorityQueueList({List<E>? elements, Priority priority = Priority.max}) {
_priority = priority;
_elements = elements ?? [];
}

late List<E> _elements;
late Priority _priority;

// more to come
}
``````

### Which Is the High Priority End?

At this point, you need to make a decision. You can either put the high priority elements at the start of the list or at the end of the list. It might seem logical to put the high priority elements at the start of the list since that’s how you implemented heap. However, think about the properties of a list and what you need to accomplish in a queue. Inserting and removing from the beginning of a list is slow. If you make the start of the list the high priority end, then every single dequeue will be slow.

### Sorting an Initial List

Replace the `PriorityQueueList` constructor with the following code:

``````PriorityQueueList({List<E>? elements, Priority priority = Priority.max}) {
_priority = priority;
_elements = elements ?? [];
_elements.sort((a, b) => _compareByPriority(a, b));
}

int _compareByPriority(E a, E b) {
if (_priority == Priority.max) {
return a.compareTo(b);
}
return b.compareTo(a);
}
``````

### Implementing isEmpty and peek

Add the following methods to begin implementing the `Queue` interface:

``````@override
bool get isEmpty => _elements.isEmpty;

@override
E? get peek => (isEmpty) ? null : _elements.last;
``````

### Implementing enqueue

Next, add the `enqueue` method:

``````@override
bool enqueue(E element) {
// 1
for (int i = 0; i < _elements.length; i++) {
// 2
if (_compareByPriority(element, _elements[i]) < 0) {
// 3
_elements.insert(i, element);
return true;
}
}
// 4
return true;
}
``````

### Implementing dequeue

Next, add the `dequeue` method:

``````@override
E? dequeue() => isEmpty ? null : _elements.removeLast();
``````

### Making the Queue Printable

Finally, override `toString` so that you can print your priority queue in a friendly format:

``````@override
String toString() => _elements.toString();
``````

### Testing it Out

To test out the priority queue, run the following in `main`:

``````final priorityQueue = PriorityQueueList<num>(
elements: [1, 12, 3, 4, 1, 6, 8, 7],
);
print(priorityQueue);
priorityQueue.enqueue(5);
priorityQueue.enqueue(0);
priorityQueue.enqueue(10);
print(priorityQueue);
while (!priorityQueue.isEmpty) {
print(priorityQueue.dequeue());
}
``````
``````[1, 1, 3, 4, 6, 7, 8, 12]
[0, 1, 1, 3, 4, 5, 6, 7, 8, 10, 12]
12
10
8
7
6
5
4
3
1
1
0
``````
Have a technical question? Want to report a bug? You can ask questions and report bugs to the book authors in our official book forum here.