Data Structures & Algorithms in Dart

Second Edition · Flutter · Dart 3.0 · VS Code 1.78

Before You Begin

Section 0: 6 chapters

Section I: Introduction

Section 1: 3 chapters

Section II: Elementary Data Structures

Section 2: 3 chapters

Section IV: Sorting Algorithms

Section 4: 5 chapters

Section V: Graphs

Section 5: 5 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.

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:

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.

``````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) {
return true;
}
``````

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

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:

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

Dequeue

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

``````@override
E? dequeue() => _list.pop();
``````

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.

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:

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.

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();
}
``````

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) {
return true;
}
``````

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
// 2
_rightStack.clear();
}
if (_leftStack.isEmpty) return null;
// 3
return _leftStack.removeLast();
}
``````

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.

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:

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