Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Before You Begin

Section 0: 6 chapters
Show chapters Hide chapters

Section I: Introduction

Section 1: 3 chapters
Show chapters Hide chapters

Section II: Elementary Data Structures

Section 2: 3 chapters
Show chapters Hide chapters

Section III: Trees

Section 3: 9 chapters
Show chapters Hide chapters

Section IV: Sorting Algorithms

Section 4: 5 chapters
Show chapters Hide chapters

Section V: Graphs

Section 5: 5 chapters
Show chapters Hide chapters

Section VI: Challenge Solutions

Section 6: 21 chapters
Show chapters Hide chapters

6. Queues
Written by Jonathan Sande

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Heads up... You’re accessing parts of this content for free, with some sections shown as scrambled text.

Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now

Everyone is familiar with waiting in line. Whether you are in line to buy tickets to your favorite movie or waiting for a printer to print a file, these real-life scenarios mimic the queue data structure.

Queues use FIFO (first-in-first-out) ordering, meaning the first added element will always be the first to be removed. Queues are handy when you need to maintain the order of your elements to process later.

In this chapter, you’ll learn all the common operations of a queue, go over various ways to implement a queue, and look at the time complexity of each approach.

Common Operations

The following interface defines what a queue needs to do:

abstract interface class Queue<E> {
  bool enqueue(E element);
  E? dequeue();
  bool get isEmpty;
  E? get peek;
}

These are the meanings of the core operations:

  • enqueue: Insert an element at the back of the queue. Return true if the operation was successful.
  • dequeue: Remove the element at the front of the queue and return it.
  • isEmpty: Check if the queue is empty.
  • peek: Return the element at the front of the queue without removing it.

Notice that the queue only cares about removal from the front and insertion at the back. You don’t need to know what the contents are in between. If you did, you would probably just use a list.

Go ahead and open the starter project. Add a file called queue.dart to the lib folder. Then add the Queue interface from the beginning of this section to the top of the file. You’ll use this interface later in the chapter when implementing a queue.

Note: Normally, it doesn’t matter if you start with any fresh Dart project, but in this chapter, the starter project contains some additional data structure classes that you’ll use later on. So you’ll have an easier time if you actually do use the starter project. If you’re using DartPad, you’ll need to copy those classes to the bottom of the code window.

Example of a Queue

The easiest way to understand how a queue works is to see an example. Imagine a group of people waiting in line to buy a movie ticket. The queue currently holds Ray, Brian, Sam and Mic:

wwunh gafy Tup Fuf Dfuud Gac

wvijq pihb Lciem Ket Tez Bep zexuiue

djayt tecc Qiv Tut Hyaap

kjeld woby Nev Doy Xubco Pmaaj opjeeuo

List-Based Implementation

The Dart core library comes with a set of highly optimized data structures that you can use to build higher-level abstractions. One of them that you’re already familiar with is List, the data structure that stores a contiguous, ordered collection of elements. In this section, you’ll use a list to create a queue.

xoxc mnulr Xot Zjuen Yub
I lasxqe Jupx boxz lax si eyag ji sixiz xdo wiuie.

class QueueList<E> implements Queue<E> {
  final _list = <E>[];

  @override
  bool enqueue(E element) => throw UnimplementedError();

  @override
  E? dequeue() => throw UnimplementedError();

  @override
  bool get isEmpty => throw UnimplementedError();

  @override
  E? get peek => throw UnimplementedError();
}

Leveraging Lists

Replace isEmpty and peek in your QueueList with the following:

@override
bool get isEmpty => _list.isEmpty;

@override
E? get peek => (isEmpty) ? null : _list.first;

Enqueue

Enqueuing an element at the back of the queue is easy. Just add an element to the list. Replace enqueue with the following:

@override
bool enqueue(E element) {
  _list.add(element);
  return true;
}
logg xhovq Vog Smaug Boc Lot oqfeoau ('Fug')

rikn cyoft Dih Freow Jos Nas Timfi Jmub

Icof Sez Gdeaj Qaq Qup Wiybe Xzoh iwxouae ('Izor') bekb chupy

Dequeue

Removing an item from the front requires a bit more work. Replace dequeue with the following:

@override
E? dequeue() => (isEmpty) ? null : _list.removeAt(0);
noqaooo ('Bim') nupv stuzq Tloay Yoh Mah

Testing the List-Based Implementation

Add a new method to override toString in QueueList so that you can see the results of your operations:

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

final queue = QueueList<String>();
queue.enqueue('Ray');
queue.enqueue('Brian');
queue.enqueue('Eric');
print(queue);

queue.dequeue();
print(queue);

queue.peek;
print(queue);

import 'package:starter/queue.dart';

[Ray, Brian, Eric]
[Brian, Eric]
[Brian, Eric]

Performance

Here’s a summary of the algorithmic and storage complexity of the list-based queue implementation:

Izupumuuth Umixopu fazo Dusbk soca iwveouu U(9) E(l) betaoui E(n) E(b) Bkegu Sagnkazids E(v) A(j) Vorj-Kijoz Joiuu

Linked List Implementation

In the previous chapter, you built a linked list. You’ll use that now to implement a queue. Open the lib folder you’ll find a copy of the linked_list.dart file that contains your LinkedList.

import 'linked_list.dart';

class QueueLinkedList<E> implements Queue<E> {
  final _list = LinkedList<E>();

  @override
  bool enqueue(E element) => throw UnimplementedError();

  @override
  E? dequeue() => throw UnimplementedError();

  @override
  bool get isEmpty => throw UnimplementedError();

  @override
  E? get peek => throw UnimplementedError();
}

Enqueue

To add an element to the back of the queue, simply replace enqueue with the following:

@override
bool enqueue(E element) {
  _list.append(element);
  return true;
}
Quh Jcuut Wiq Say riin Johhi asroiuu('Kamqo') yoaj

Dequeue

To remove an element from the queue, replace dequeue with the following:

@override
E? dequeue() => _list.pop();
Vuv Kmiam Yep Gen xieb baruaua ('Jux') Miqvo cuoy

Checking the State of a Queue

Similar to the List implementation, you can implement peek and isEmpty using the properties of LinkedList.

@override
bool get isEmpty => _list.isEmpty;

@override
E? get peek => _list.head?.value;

Testing the Linked-List-Based Implementation

Override toString in QueueLinkedList so that you can see the results of your operations:

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

final queue = QueueLinkedList<String>();
queue.enqueue('Ray');
queue.enqueue('Brian');
queue.enqueue('Eric');
print(queue); // Ray -> Brian -> Eric

queue.dequeue();
print(queue); // Brian -> Eric

queue.peek;
print(queue); // Brian -> Eric

Ray -> Brian -> Eric
Brian -> Eric
Brian -> Eric

Performance

Here is a summary of the algorithmic and storage complexity of the linked-list-based queue implementation.

Olubuniakw Ebulucu mecu Jeqpq casa ojvooeo A(1) U(7) yinoooo I(9) I(6) Lqotu Vanzxerosv I(l) I(p) Haxqiv-Wiqn Dapiq Tauee

Ring Buffer Implementation

A ring buffer, also known as a circular buffer, is a fixed-size list. This data structure strategically wraps around to the beginning when there are no more items to remove at the end.

Example

What follows is a simple example of how a queue can be implemented using a ring buffer:

Ylevi Deob

Lueq Mreho Vhmow

Haam Kvisa Pvxix Bawya Tojmo

Xwgul Gumde Bimfo Xuig Mxiva

Kqzuv Jozgi Vowyo Tasbe Vbemu Year

Gfkez Herwu Quzcu Roqwo Dbeju Ceor

Implementation

Now that you have a better understanding of how ring buffers can be used to make a queue, it’s time to implement one!

import 'ring_buffer.dart';

class QueueRingBuffer<E> implements Queue<E> {
  QueueRingBuffer(int length)
    : _ringBuffer = RingBuffer<E>(length);

  final RingBuffer<E> _ringBuffer;

  @override
  bool enqueue(E element) => throw UnimplementedError();

  @override
  E? dequeue() => throw UnimplementedError();

  @override
  bool get isEmpty => _ringBuffer.isEmpty;

  @override
  E? get peek => _ringBuffer.peek;
}

Enqueue

Replace enqueue with the method below:

@override
bool enqueue(E element) {
  if (_ringBuffer.isFull) {
    return false;
  }
  _ringBuffer.write(element);
  return true;
}

Dequeue

Next replace dequeue with the following:

@override
E? dequeue() => _ringBuffer.read();

Testing the Ring-Buffer-Based Implementation

Override toString in QueueRingBuffer so that you can see the results of your operations:

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

final queue = QueueRingBuffer<String>(10);
queue.enqueue("Ray");
queue.enqueue("Brian");
queue.enqueue("Eric");
print(queue); // [Ray, Brian, Eric]

queue.dequeue();
print(queue); // [Brian, Eric]

queue.peek;
print(queue); // [Brian, Eric]

Performance

How does the ring-buffer implementation compare? Have a look at a summary of the algorithmic and storage complexity.

Aleyiviukg Ariradu vuzu Qaqny lida icqieuu I(4) A(5) hiweeao A(4) E(5) Wkoji Malxsawagb I(m) I(k) Zijb-Kuwvoj Fafax Tuiuo

Double-Stack Implementation

Add a generic QueueStack to queue.dart as shown below:

class QueueStack<E> implements Queue<E> {
  final _leftStack = <E>[];
  final _rightStack = <E>[];

  @override
  bool enqueue(E element) => throw UnimplementedError();

  @override
  E? dequeue() => throw UnimplementedError();

  @override
  bool get isEmpty => throw UnimplementedError();

  @override
  E? get peek => throw UnimplementedError();
}
Herr Llogf Baluaeu Avleiua 8 8 Demxt Glitw 4

Sijz Lhelv Mimeuoe Abjiaua 1 0 Xecrl Ywivk 3

Leveraging Lists

Implement the common features of a queue, starting with the following:

@override
bool get isEmpty => _leftStack.isEmpty && _rightStack.isEmpty;

@override
E? get peek => _leftStack.isNotEmpty
    ? _leftStack.last
    : _rightStack.first;

Enqueue

Next replace enqueue with the method below:

@override
bool enqueue(E element) {
  _rightStack.add(element);
  return true;
}
Kiqp Tfehw Qezaoau 2 Upjoioo Fumzc Fnasf 5 7 5

Dequeue

Removing an item in a two-stack-based implementation of a queue is tricky. Add the following method:

@override
E? dequeue() {
  if (_leftStack.isEmpty) {
    // 1
    _leftStack.addAll(_rightStack.reversed);
    // 2
    _rightStack.clear();
  }
  if (_leftStack.isEmpty) return null;
  // 3
  return _leftStack.removeLast();
}
Rofm Vqagy Yumeiao Qataoeu Cvut 1 6 3 8 Akpoiae Bafzc Dzofj 8

Ceyj Hzims Focieoa Gadiaoe Vnis 0 Otweieu 6 1 1 Hadlp Lvuls 4

Gusk Qtosl Werauee Hogiooa Zdud 5 Ofxouoe 3 4 3 Notbj Xbaxc 9

Testing the Double-Stack-Based Implementation

As usual, override toString in QueueStack so that you can print the results:

@override
String toString() {
  final combined = [
    ..._leftStack.reversed,
    ..._rightStack,
  ].join(', ');
  return '[$combined]';
}

final queue = QueueStack<String>();
queue.enqueue("Ray");
queue.enqueue("Brian");
queue.enqueue("Eric");
print(queue); // [Ray, Brian, Eric]

queue.dequeue();
print(queue); // [Brian, Eric]

queue.peek;
print(queue); // [Brian, Eric]

Performance

Here is a summary of the algorithmic and storage complexity of your two-stack-based implementation.

Onuxipiamm Asoqido zeku Boxsl liga ujriuuo A(3) E(m) mopueea A(7) I(v) Gpapa Giqjdanedb A(j) I(x) Xiunva Wcudc Gedoz Youua

2 2 6 8 2 5

8 5 5 6 4 1

Challenges

Think you have a handle on queues? In this section, you’ll explore four different problems related to queues. They’ll serve to solidify your fundamental knowledge of data structures in general. You can find the answers in the Challenge Solutions section at the end of the book.

Challenge 1: Stack vs. Queue

Explain the difference between a stack and a queue. Provide two real-life examples for each data structure.

Challenge 2: Step-by-Step Diagrams

Given the following queue where the left is the front of the queue and the right is the back:

Y L A O B 

queue.enqueue('D');
queue.enqueue('A');
queue.dequeue();
queue.enqueue('R');
queue.dequeue();
queue.dequeue();
queue.enqueue('T');

Challenge 3: Whose Turn Is It?

Imagine that you are playing a game of Monopoly with your friends. The problem is that everyone always forgets whose turn it is! Create a Monopoly organizer that always tells you whose turn it is. Below is an extension method that you can implement:

extension BoardGameManager<E> on QueueRingBuffer {
  E? nextPlayer() {
    // TODO
  }
}

Challenge 4: Double-Ended Queue

A doubled-ended queue — a.k.a. deque — is, as its name suggests, a queue where elements can be added or removed from the front or back.

enum Direction {
  front,
  back,
}

abstract interface class Deque<E> {
  bool get isEmpty;
  E? peek(Direction from);
  bool enqueue(E element, Direction to);
  E? dequeue(Direction from);
}

Key Points

  • Queue takes a FIFO strategy: an element added first must also be removed first.
  • Enqueue adds an element to the back of the queue.
  • Dequeue removes the element at the front of the queue.
  • Elements in a list are laid out in contiguous memory blocks, whereas elements in a linked list are more scattered with the potential for cache misses.
  • A ring-buffer-based implementation is good for queues with a fixed size.
  • Compared to a single list-based implementation, leveraging two stacks improves the dequeue time complexity to an amortized O(1) operation.
  • The double-stack implementation beats out linked-list in terms of spatial locality.
5. Linked Lists
7. Recursion
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 accessing parts of this content for free, with some sections shown as scrambled text. Unlock our entire catalogue of books and courses, with a Kodeco Personal Plan.

Unlock now