6 Chapter 6 Solutions

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.

SPEEDSPEEDDenqueue ('D')SPEEDDAenqueue ('A')PEEDDAdequeue ()PEEDDARenqueue ('R')EEDDARdequeue ()EDDARdequeue ()EDDARTenqueue ('T')

Linked List

SPEEDSPEEDDenqueue ('D')PEEDADRenqueue ('R')EEDADRdequeue ()EDADRdequeue ()enqueue ('T')EDADRTSPEEDDAenqueue ('A')dequeue ()PEEDDA

Ring Buffer

SPEEDrwSPEEDrwSPEEDrwSPEEDrwrwRPEEDrwRPEEDrwRPEEDrwRTEEDenqueue ('D')return falseenqueue ('A')return falseenqueue ('R')return trueenqueue ('T')dequeue ()dequeue ()dequeue ()

Double Stack

Left StackSRight StackEPESDDLeft StackRight Stackenqueue ('D')EPED

Left StackSPEEDDARight StackDADPSEELeft StackRight Stackdequeue ()enqueue ('A')

Left StackRRight StackDADPREELeft StackRight Stackdequeue ()enqueue ('R')DADPEE

DADERELeft StackRight Stackdequeue ()EDDARTLeft StackRight Stackenqueue ('T')

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;
  }
}

Dequeuing a player tells you who is next. Enqueuing them again puts them at the back of the queue.

For the small number of players you’re dealing with in a Monopoly game, you aren’t going to have any noticeable performance difference no matter what queue type you choose. However, a ring-buffer-based queue is great for Monopoly since there are a set number of players and you don’t need to worry about overfilling the buffer.

Test it out:

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.

First setup the doubly-linked-list deque as shown below:

class DequeDoublyLinkedList<E> implements Deque<E> {
  final _list = DoublyLinkedList<E>();

}

Now you have to conform to the Deque interface. First, implement isEmpty by checking if the linked list is empty. This is an O(1) operation.

@override
bool get isEmpty => _list.isEmpty;

Next, you need a way to look at the value from the front or back of the Deque.

@override
E? peek(Direction from) {
  switch (from) {
    case Direction.front:
      return _list.head?.value;
    case Direction.back:
      return _list.tail?.value;
  }
}

To peek at the element from the front or back, check the list’s head and tail values. This is an O(1) operation.

Now you need a way to add elements to the front or back of Deque.

@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;
}

Adding an element to the front or back of Deque:

1. Front: push an element to the front of the list. Internally the linked list will update the new node as the head of the linked list.
2. Back: append an element to the back of the list. Similarly, the linked list will update the new node as the tail of the linked list.

These are both O(1) operations since all you have to do is update the internal pointers for a couple nodes.

Now that you have a way to add elements, how about a way to remove elements?

@override
E? dequeue(Direction from) {
  switch (from) {
    case Direction.front:
      return _list.pop();
    case Direction.back:
      return _list.removeLast();
  }
}

Removing an element from the front or back of a Deque is simple.

1. Front: Call pop to remove the head node in the list.
2. Back: Similarly, call removeLast to remove the tail.

Similar to enqueue, these are O(1) operations for a doubly linked list.

Lastly, override toString so you can test your Deque.

@override
String toString() => _list.toString();

That’s all there is to building a Deque! Add the following code below to test your implementation:

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);

Run that and you’ll see the following in the console:

[1, 2, 3, 4]
[5, 1, 2, 3, 4]
[]