Dart DoubleLinkedQueue

最后修改于 2025 年 6 月 8 日

在 Dart 中，DoubleLinkedQueue 是一个高性能的双端队列实现，它允许在两端高效地插入和删除元素。对于需要频繁修改队列前端和后端的场景特别有用。

DoubleLinkedQueue 实现了 Queue 接口，确保元素在添加或删除时保持其顺序。在内部，它使用双向链表结构，这使得像从任一端添加、删除和查看元素这样的操作具有O(1) 的时间复杂度。

与基于可调整大小数组的标准 ListQueue 不同，DoubleLinkedQueue 在修改队列时不需要移动元素，这使得它对于动态数据结构更有效。它非常适合任务调度、撤销/重做功能和缓冲机制等用例。

DoubleLinkedQueue 的主要特点

支持在两端进行常数时间插入和删除。
保持元素顺序，确保行为可预测。
使用链式节点，避免昂贵的数组重新调整大小操作。
提供用于迭代、清空和检查是否为空的方法。

通过利用 DoubleLinkedQueue，开发人员可以高效地管理需要频繁在两端进行修改的动态集合，而无需移动元素的开销，使其成为 Dart 集合库中的强大工具。实际应用包括实现双端队列、管理事件队列以及构建需要高效前端和后端访问的复杂数据结构；例如在任务调度或缓冲场景中。

创建 DoubleLinkedQueue

创建 DoubleLinkedQueue 的最简单方法是使用构造函数。

main.dart

import 'dart:collection';

void main() {
  var queue = DoubleLinkedQueue<String>();
  queue.addFirst('Apple');
  queue.addLast('Banana');
  queue.addLast('Orange');

  print(queue);
}

我们创建一个字符串的 DoubleLinkedQueue。我们使用 addFirst 和 addLast 向两端添加元素。队列会保持插入顺序。

$ dart main.dart
DoubleLinkedQueue(Apple, Banana, Orange)

基本队列操作

DoubleLinkedQueue 在两端提供标准队列操作。

main.dart

import 'dart:collection';

void main() {
  var queue = DoubleLinkedQueue<int>();
  queue.addAll([10, 20, 30]);
  
  print('First element: ${queue.first}');
  print('Last element: ${queue.last}');
  
  queue.removeFirst();
  queue.removeLast();
  
  print('After removals: $queue');
}

我们演示了基本操作。addAll 添加多个元素。first 和 last 访问两端。removeFirst 和 removeLast 修改队列。

$ dart main.dart
First element: 10
Last element: 30
After removals: DoubleLinkedQueue(20)

遍历队列

DoubleLinkedQueue 支持使用 for-in 循环和迭代器进行迭代。您可以按照添加元素的顺序遍历元素。

main.dart

import 'dart:collection';

void main() {
  var queue = DoubleLinkedQueue.of(['Red', 'Green', 'Blue']);
  
  print('Standard iteration:');
  for (var color in queue) {
    print(color);
  }

  var it = queue.iterator;
  print('\nUsing iterator:');
  
  while (it.moveNext()) {
    print(it.current);
  }
}

我们使用 of 从可迭代对象创建一个队列。我们使用 for-in 循环和显式迭代器进行迭代。两种方法都保持原始顺序。

队列操作

DoubleLinkedQueue 提供了用于复杂操作的方法。

main.dart

import 'dart:collection';

void main() {
  var queue = DoubleLinkedQueue<int>();
  queue.addAll([1, 2, 3, 4, 5]);
  
  queue.addFirst(0);
  queue.addLast(6);
  
  queue.removeWhere((element) => element % 2 == 0);
  
  print('Final queue: $queue');
  print('Length: ${queue.length}');
}

我们演示了向两端添加元素。removeWhere 用于过滤元素。队列在所有操作中都保持顺序。

$ dart main.dart
Final queue: DoubleLinkedQueue(0, 1, 3, 5)
Length: 4

转换为其他集合

DoubleLinkedQueue 可以转换为其他集合类型。

main.dart

import 'dart:collection';

void main() {
  var queue = DoubleLinkedQueue.of(['a', 'b', 'c']);
  
  var list = queue.toList();
  var set = queue.toSet();
  
  print('List: $list');
  print('Set: $set');
}

我们将队列转换为 List 和 Set。转换会保留元素顺序。

$ dart main.dart
List: [a, b, c]
Set: {a, b, c}

最佳实践

用于双端操作： 优先用于频繁的前端/后端访问。
避免随机访问： 未针对中间元素访问进行优化。
考虑 ListQueue： 主要用于单端操作。
线程安全： 与所有 Dart 集合一样，不保证线程安全。

来源

Dart DoubleLinkedQueue 文档

本教程通过实际示例介绍了 Dart 的 DoubleLinkedQueue，展示了其关键特性和使用模式。

作者

我叫 Jan Bodnar，我是一名热情的程序员，拥有丰富的编程经验。我从 2007 年开始撰写编程文章。迄今为止，我已撰写了 1,400 多篇文章和 8 本电子书。我在教授编程方面拥有十多年的经验。

列出所有 Dart 教程。