6.
Chapter 6 Solutions
Written by Jonathan Sande
Heads up... You’re accessing parts of this content for free, with some sections shown as text.
Heads up... You’re accessing parts of this content for free, with some sections shown as text.
Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.
Unlock now
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