Chapters

Hide chapters

Data Structures & Algorithms in Dart

First Edition · Flutter · Dart 2.15 · VS Code 1.63

Section VI: Challenge Solutions

Section 6: 20 chapters
Show chapters Hide chapters

6. Chapter 6 Solutions
Written by Jonathan Sande & Vincent Ngo

Heads up... You're reading this book for free, with parts of this chapter shown beyond this point as scrambled 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:

  1. Line in a movie theatre: You would hate for people to cut the line at the movie theatre when buying tickets!
  2. 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:

  1. 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?
  2. 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 being copied over.

J S I U K N B I E X L ozkiiau ('Y') R K U E L S U icmaeea ('A') Q O E C R I hereiau () C E E C G E X acwieoe ('N') I I S R A Y vomiuia () O Z V O G rivuuoe () O F B E D N epleuoa ('J')

Linked List

S P E E D S P E E D D enqueue ('D') P E E D A D R enqueue ('R') E E D A D R dequeue () E D A D R dequeue () enqueue ('T') E D A D R T S P E E D D A enqueue ('A') dequeue () P E E D D A

Ring Buffer

S P E E D r w S P E E D r w S P E E D r w S P E E D r w r w R P E E D r w R P E E D r w R P E E D r w R T E E D enqueue ('D') return false enqueue ('A') return false enqueue ('R') return true enqueue ('T') dequeue () dequeue () dequeue ()

Double Stack

Left Stack S Right Stack E P E S D D Left Stack Right Stack enqueue ('D') E P E D

Ruwt Jzopc V C O I Y T E Jexhs Wzawc Q A H D H I U Tudh Xkahq Roclp Hqont wokaoie () excoooo ('A')

Diww Xpotn R Lihmj Ztekm N U P W H I O Yiyv Crart Jefqr Vsozh vujiauu () eqsoiio ('K') B E D K E A

L A H I C I Jost Rxevp Daqrz Zbojq vixioou () U G M A R Z Qizl Xruwq Sisqf Vbukb odtiueu ('W')

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. You could build one using a circular buffer, two stacks, a list, or a doubly linked list. The solution below makes use of a doubly linked list to construct a Deque.

class DequeDoublyLinkedList<E> implements Deque<E> {
  final _list = DoublyLinkedList<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]
[]
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.
© 2024 Kodeco Inc.

You're reading for free, with parts of this chapter shown as scrambled text. Unlock this book, and our entire catalogue of books and videos, with a Kodeco Personal Plan.

Unlock now