6.
Chapter 6 Solutions
Written by Jonathan Sande
Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as text.
Solution to Challenge 1
Queues have a behavior of first-in-first-out. What comes in first must come out first. Items in the queue are inserted from the rear and removed from the front.
Queue Examples:
- Line in a movie theatre: You would hate for people to cut the line at the movie theatre when buying tickets!
- Printer: Multiple people could print documents from a printer in a similar first-come-first-serve manner.
Stacks have a behavior of last-in-first-out. Items on the stack are inserted at the top and removed from the top.
Stack Examples:
- Stack of plates: You stack plates on top of each other and remove the top plate every time you use one. Isn’t this easier than grabbing the one at the bottom?
- Undo functionality: Imagine typing words on a keyboard. Clicking Ctrl-Z will undo the most recent text you typed.
Solution to Challenge 2
List
Keep in mind that whenever the list is full, and you try to add a new element, a new list will be created with twice the capacity and existing elements will be copied over.
Linked List
Ring Buffer
Double Stack
Solution to Challenge 3
Creating a board game manager is straightforward. All you care about is whose turn it is. A queue data structure is the perfect choice for that!
extension BoardGameManager<E> on QueueRingBuffer<E> {
E? nextPlayer() {
final person = dequeue();
if (person != null) {
enqueue(person);
}
return person;
}
}
final monopolyTurn = QueueRingBuffer<String>(4);
monopolyTurn.enqueue('Ray');
monopolyTurn.enqueue('Vicki');
monopolyTurn.enqueue('Luke');
monopolyTurn.enqueue('Pablo');
String? player;
for (var i = 1; i <= 20; i++) {
player = monopolyTurn.nextPlayer();
print(player);
}
print('$player wins!');
Solution to Challenge 4
Deque is made up of common operations from the Queue and Stack data structures. There are many ways to implement a Deque. The solution below makes use of a linked list to construct a Deque.
class DequeLinkedList<E> implements Deque<E> {
final _list = LinkedList<E>();
}
@override
bool get isEmpty => _list.isEmpty;
@override
E? peek(Direction from) {
switch (from) {
case Direction.front:
return _list.head?.value;
case Direction.back:
return _list.tail?.value;
}
}
@override
bool enqueue(E value, Direction to) {
switch (to) {
case Direction.front:
_list.push(value);
break;
case Direction.back:
_list.append(value);
break;
}
return true;
}
@override
E? dequeue(Direction from) {
switch (from) {
case Direction.front:
return _list.pop();
case Direction.back:
return _list.removeLast();
}
}
@override
String toString() => _list.toString();
final deque = DequeDoublyLinkedList<int>();
deque.enqueue(1, Direction.back);
deque.enqueue(2, Direction.back);
deque.enqueue(3, Direction.back);
deque.enqueue(4, Direction.back);
print(deque);
deque.enqueue(5, Direction.front);
print(deque);
deque.dequeue(Direction.back);
deque.dequeue(Direction.back);
deque.dequeue(Direction.back);
deque.dequeue(Direction.front);
deque.dequeue(Direction.front);
deque.dequeue(Direction.front);
print(deque);
1 -> 2 -> 3 -> 4
5 -> 1 -> 2 -> 3 -> 4
Empty list