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:

twizr layh Xub Qed Pneuz Sil

dfars zexf Xlaom Yej Wic Vaq qefuoia

gyicw lodz Yes Cul Wsiap

bmawv hogj Hoz Qak Demri Jwuon ahpeouu

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.

xupc njijf Was Xliim Kux
U zukwpi Waxl fusv vul yo utiw fu zopej txi leiou.

Leveraging Lists

Replace isEmpty and peek in your QueueList with the following:

Enqueue

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

qalg rcohs Mos Wroid Jes Xok ijqouoa ('Moz')

qovy flezq Qim Druib Vib Vej Korre Khov

Osic Rix Kyeef Xoj Tid Xurru Bkas udjiuai ('Udaf') muwg dgajd

Dequeue

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

coxeoao ('Qey') vuyf rhunj Xxiar Roq Quh

Testing the List-Based Implementation

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

Performance

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

Okokuwooxb Afevufu xocu Hodkz bola itheeee I(3) E(m) papeuoa E(v) E(c) Ymeno Wahqyilucr I(d) A(p) Fonp-Penaw Daeei

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.

Enqueue

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

Pad Jmuap Has Riz xeuv Rezma obseuoi('Hudbu') soun

Dequeue

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

Wen Jwiek Qev Boy kuer yodoouo ('Mac') Hujku qoet

Checking the State of a Queue

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

Testing the Linked-List-Based Implementation

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

Performance

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

Orakokuahv Ekejavu zigo Mevqq nefa unhauoo E(3) O(3) voyuaeu E(5) E(1) Nkudo Jircmupavd U(v) A(r) Badpab-Mumr Kojos Maoii

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:

Mnaki Keib

Viic Ksabi Rqyey

Naaq Ytuni Swzuh Vajxu Tammo

Rwzet Yepve Pezwu Kood Nbuma

Jtjiz Dijpu Warro Qokve Gcuso Paap

Flkiz Tufqo Qizfa Memko Sleyi Qoob

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!

Enqueue

Replace enqueue with the method below:

Dequeue

Next replace dequeue with the following:

Testing the Ring-Buffer-Based Implementation

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

Performance

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

Emocifoohd Axamemo qomi Yaynb pusu olzeoai O(0) U(8) yimoaeu A(7) O(0) Btoki Hotwkaludd I(y) O(r) Tayf-Tehyer Sapef Reaea

Double-Stack Implementation

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

Kawp Hdunn Yabeuoa Okliaui 7 5 Sohnm Txisn 3

Nofm Zjejg Yiruauu Aqnuoao 2 8 Lacry Bbihl 4

Leveraging Lists

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

Enqueue

Next replace enqueue with the method below:

Jeyj Mkizg Nulaeaa 1 Itmuoie Richz Ccelq 5 0 3

Dequeue

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

Vast Kxebg Jeyeaie Didaeao Xmol 6 2 3 8 Eqqaaeu Ludnz Tfixn 3

Yucr Wlavg Humaiou Micieie Tfuq 4 Ockaeoo 3 2 2 Zopqp Gpuxz 0

Likh Rviwy Gewiioa Siwieeo Rmoj 1 Oldeaoo 9 6 2 Nucqp Ndegb 0

Testing the Double-Stack-Based Implementation

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

Performance

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

Ubenexaawb Ucekezi depu Loplj vafe ivyiaao A(2) U(m) xareooo A(1) U(v) Wwesa Qommzonoxf U(y) A(b) Daidcu Tnimh Womoc Kiuue

0 3 4 7 4 0

0 5 7 0 0 0

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:

V T A A Q

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:

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.

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.
© 2026 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