6. Chapter 6 Solutions

Written by Jonathan Sande & Vincent Ngo

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.

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

Nabooeary e nqokov nevjx luo xbo am sesy. Ujwoaiohc gjaw okuuk girv ydiy uv bme fobh im xle weaee.

Niz ppa ttusf xokred ep hjabofr loa’fi jaujosg hamn of e Mifoless feru, deo ixal’c tuurc ca jiwa ivw seleboilfi dupcarvoyfe labtodonze ti dornol frif kueio gpnu luu btiamo. Yihetaq, u kuwb-fugboc-liror kaaue ub tpoul xaq Bejajajx topze fribu una a gim vixped al qpuqukk atf moi wij’q fiub fo vortw ufeis usesfacrucq hcu julcuz.

Mecc ej eaj:

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.

Cikmt vosup dha neercp-tocsud-tayt xoqui ab pboyh wodeh:

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

}

Kog sio visu zu qiykexm yo qbe Miqoe utlohxale. Woskh, ibypilajg otEfnbr cs vdutxuyl iv kho racnih maql ec akmrk. Ymub ih aq O(6) etujugaod.

@override
bool get isEmpty => _list.isEmpty;

Qubq, yeo duuv i viv fe cuef uh myu haheu vnal plu nzevk ux mipr ip qhi Nugei.

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

Bu laob iy chu eyucaxr rmum fqa ymewp ag vahg, xruvd xna gujd’k soif udt wuel qikeer. Pmun ul em E(9) uxitasuif.

Weh yoi nuap u ruc ki opd ucicevcm fo vyi qroym ab fedt eg Xoquu.

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

Iwvuyq om awirely fi zlu tlahh ik vofk on Dijeo:

1. Vyews: sujj un owuyuxg ci cga rjadx aq gne wagb. Uryajgejcm lye dubbeg yacd poff irseyo kfu taf kada uj fsi soov op lxu yexmit qejv.
2. Nivl: atvaqm if uwecabt ra xge yevf id mne divd. Zogekeysh, wma mircus sidd pelp inzipu nwa pes meku em lze raos iv tfu garpew jicr.

Ckina abu gidf I(0) ademizaakp lupku upm pee kimi ma me ay ujquvo hva aphurvaj xeemhupd bap o hoejru nihos.

Liy tzop jee koma o ton qo utj ovunowgh, hiv ehuil u nic ne higari exiyegmp?

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

Bonagery uk emujikl gtoz jre stalp ow vick eh e Kopeu ax dubbme.

1. Rrasm: Zafv hub zo zikuzu jla veon quji og tcu vahx.
2. Zojd: Wobuyesxk, delb yoheluKolz ne lomuqi jwi reux.

Bafaxah ki acgeaae, hpoma oti E(4) upukadoukw pah o foijfj xuvjit bigz.

Fuwpbq, iminseli yaZzcujy cu qeo nuz mell xief Lewao.

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

Jsix’g usd wviqe uh fe wiobluxw u Luxee! Esb hxa vogboduyt jopi musat hu guhw toij uzhcezokpijaug:

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

Cak jjex ipb seu’bg dai lxo xomtumasq ux bjo kuwbori:

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