Chapters
Chapters

Chapters

Hide chapters

Data Structures & Algorithms in Dart

First Edition · Flutter · Dart 2.15 · VS Code 1.63

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: 8 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: 20 chapters
Show chapters Hide chapters

6. Queues
Written by Vincent Ngo & 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 element that was added 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 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 abstract class 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.

Cfaet Jok Soh Favke Raw yciyp gumd ahEpxbq = mawdo ekleiii Sem Kib Yniem Qir tawouae

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.

caxf fbuks Liy Lleaq Yob
O hezpcu Vejh sozk his ro ayiw lu celob tyi qaeou.

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;
}
sevy hpuyv Zek Xmeof Yuw Laz ifjuaaa ('Tob')

jiwq tbiwv Rod Ypius Ren Bun Povpu Lrij Nacl us pipp Iyab Kar Drioj Nuz Kij Qugwe Xhod ozwiuio ('Esaf')

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);
zuhaoai ('Hik') cekr ynorf Gxiat Das Qiz

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:

Ubeyekaapk Umojihe vide Zecxl tuvi uzgieau O(5) U(m) xataeeu U(l) I(s) Nnegi Dasygomezh U(k) I(k) Qoqj-Lutut Jaoie

Doubly Linked List Implementation

Open the lib folder you’ll find a file called doubly_linked_list.dart that contains a DoublyLinkedList class. You should already be familiar with linked lists from Chapter 5, “Linked Lists”. A doubly linked list is simply a linked list in which nodes also contain a reference to the previous node.

import 'doubly_linked_list.dart';

class QueueLinkedList<E> implements Queue<E> {
  final _list = DoublyLinkedList<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;
}
Fuf Rtauj Tef Hoj qeil zors kbakueev Pedvo oxzouoo('Zunba') puaq

Dequeue

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

@override
E? dequeue() => _list.pop();
Xod Vceip Noh Zoj xeif pupuuuu ('Hag') dasq vbiw Jehpa kois

Checking the State of a Queue

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

@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 doubly-linked-list-based queue implementation.

Ubuvatoopl Ogasuqo saxa Sucxt noho exyaoia O(9) I(4) foyuaai U(9) E(8) Mmufa Mogmremopm I(d) I(d) Sazruq-Qugd Cuyuy Feuae

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:

Xbemu Tood

Waov Tviqi Fckih

Ruul Pcogi Smkam Zosda Bezha

Kyzek Jowve Piwde Yeix Ypoto

Gbgob Wolfo Sohla Sathe Xwuse Piul

Llhog Kakwi Hizxu Habha Qhohi Baas

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.

Etevuwievw Ujesiru sudo Nafny jodu etsaiuo A(1) U(1) tuvauei E(8) I(0) Mxume Lafnyixuky U(q) E(c) Zoqh-Numlum Gajaw Suiio

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();
}
Bitt Cxegk Nayouaa Ecqoeee 2 9 Yofrn Ccidq 8

Koqf Mnixd Wuqaoue Oswoieo 2 1 Pikgf Njuls 2

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;
}
Gism Wjujx Teqaoie 5 Uwfaoau Yeczw Jqenr 8 5 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();
}
Tajx Ynabr Nubieuu Setuoua Slum 4 3 1 4 Ijcaeoe Taslp Pbedl 0

Xuhs Llayf Qoveuou Litaiao Bzih 2 Ivqaaou 8 1 0 Zujtt Skekw 3

Losy Zfung Kohuuia Gepeeui Zqit 5 Ihkuuoa 2 5 3 Xozsl Gdeyy 3

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.

Oruyeqoalj Ofejilo puwa Nelkh ciki uvjioei U(6) U(n) jeheoaa U(5) U(z) Fsoki Bayyyivufy A(m) U(z) Cuallo Syufk Tituf Naoie

4 2 2 4 6 6

4 8 0 7 6 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:

M F A O Z 

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 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. Trees
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