Queues in Dart

Queue使用FIFO（先进先出）排序，这意味着添加的第一个元素将始终是第一个被删除的元素。当您需要维护稍后要处理的元素的顺序时，队列很方便。

/*
 * Queue使用FIFO（先进先出）排序，这意味着添加的第一个元素将始终是第一个被删除的元素。
 * 当您需要维护稍后要处理的元素的顺序时，队列很方便。
 */
/// Queue
abstract class Queue<E> {
  // enqueue：在队列的后面插入一个元素。如果操作成功，则返回true。
  bool enqueue(E element);
  // dequeue：删除队列前面的元素并返回。
  E? dequeue();
  // isEmpty：检查队列是否为空。
  bool get isEmpty;
  // peek：返回队列前面的元素而不删除它。
  E? get peek;
}

在以下部分中，您将学习使用四种不同的内部数据结构创建队列：

List

Doubly linked list

Ring buffer

Two stacks

1. List-Based Implementation

class QueueList<E> implements Queue<E> {
  // 这将设置一个专用列表来保存队列的元素。您还添加了前面定义的Queue接口所需的方法
  final _list = <E>[];
  // 平均而言，对一个元素进行排队是一个O（1）运算。这是因为列表后面有空的空间。
  // 在添加了多个元素之后，列表最终会被填满。
  // 如果您想使用超过分配的空间，则必须调整列表大小以腾出更多空间。
  // 毕竟，调整大小需要列表分配新内存，并将所有现有数据复制到新列表中。
  // 关键是这种情况不会经常发生。
  // 这是因为每当空间不足时，容量就会翻倍。
  // 因此，如果计算enqueue操作的摊余成本（平均成本），enqueue仅为O（1）。
  // 也就是说，当执行复制时，最坏的性能是O（n）。
  @override
  bool enqueue(E element) {
    _list.add(element);
    return true;
  }

  // 从列表的开头删除元素总是一种线性时间操作，因为它需要在内存中移动列表中所有剩余的元素。
  @override
  E? dequeue() => (isEmpty) ? null : _list.removeAt(0);
  @override
  bool get isEmpty => _list.isEmpty; // O(1)
  @override
  E? get peek => (isEmpty) ? null : _list.first; // O(1)
  // 添加一个新方法来覆盖QueueList中的toString，以便您可以看到操作的结果：
  @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);
// [Ray, Brian, Eric]
// [Brian, Eric]
// [Brian, Eric]

操作	平均情况	最坏情况
入列	O(1)	O(n)
出列	O(n)	O(n)
空间复杂度	O(n)	O(n)

2. Doubly Linked List Implementation

双链表只是一个链表，其中的节点还包含对前一个节点的引用。
单链表由于removeLast是O（n），因此应该避免使用该方法。
您可以使用append入队，也可以使用pop出队，这两者都是O（1）。
对于双链接列表来说，这并不重要，因为removeLast也是O（1）。

Doubly Link

class Node<T> {
  Node({required this.value, this.next, this.previous});
  T value;
  Node<T>? next;
  Node<T>? previous;

  @override
  String toString() {
    return '$value';
  }
}

abstract class LinkedList<E> {
  Node<E>? head;
  Node<E>? tail;
  bool get isEmpty;
  void append(E value);
  void push(E value);
  E? pop();
  E? removeLast();
}

class DoublyLinkedList<E> extends Iterable<E> implements LinkedList<E> {
  @override
  Node<E>? head;

  @override
  Node<E>? tail;

  @override
  bool get isEmpty => head == null;

  @override
  void append(E value) {
    // convert the value to a node
    final newNode = Node(value: value, previous: tail);

    // update the pointers at the tail of the list
    if (isEmpty) {
      head = newNode;
    } else {
      tail!.next = newNode;
      // handle lists with only one element
      head?.next ??= newNode;
    }
    tail = newNode;
  }

  @override
  void push(E value) {
    // convert the value to a node
    final newNode = Node(value: value, next: head);

    // update the pointers at the tail of the list
    if (isEmpty) {
      tail = newNode;
    } else {
      head!.previous = newNode;
      // handle lists with only one element
      tail?.previous ??= newNode;
    }
    head = newNode;
  }

  @override
  E? pop() {
    // handle an empty list
    if (isEmpty) return null;

    // save the return value
    final value = head?.value;

    // handle a list of length one
    if (head?.next == null) {
      head = null;
      tail = null;
      return value;
    }

    // update the pointers
    head = head?.next;
    head?.previous = null;

    return value;
  }

  @override
  E? removeLast() {
    // delegate lists with one or zero items to pop
    if (tail?.previous == null) return pop();

    // save the return value
    final value = tail?.value;

    // update the pointers
    tail = tail?.previous;
    tail?.next = null;

    return value;
  }

  @override
  Iterator<E> get iterator => _LinkedListIterator(this);

  @override
  String toString() => '[${join(', ')}]';
}

class _LinkedListIterator<E> implements Iterator<E> {
  _LinkedListIterator(DoublyLinkedList<E> list) : _list = list;
  final DoublyLinkedList<E> _list;
  Node<E>? _currentNode;
  bool _firstPass = true;

  @override
  E get current => _currentNode!.value;

  @override
  bool moveNext() {
    if (_list.isEmpty) return false;
    if (_firstPass) {
      _currentNode = _list.head;
      _firstPass = false;
    } else {
      _currentNode = _currentNode?.next;
    }
    return _currentNode != null;
  }
}

Doubly Linked List

class QueueLinkedList<E> implements Queue<E> {
  final _list = DoublyLinkedList<E>();
  // 在幕后，双链接列表将更新尾部节点对新节点的上一个和下一个引用。这是一个O（1）运算。
  @override
  bool enqueue(E element) {
    _list.append(element);
    return true;
  }

  // 从链接列表的前面删除也是一种O（1）操作。与List实现相比，您不必逐个移动元素。
  // 相反，只需更新链表前两个节点的指针：
  @override
  E? dequeue() => _list.pop();
  @override
  bool get isEmpty => _list.isEmpty;
  @override
  E? get peek => _list.head?.value;
  @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]

操作	平均情况	最坏情况
入列	O(1)	O(1)
出列	O(1)	O(1)
空间复杂度	O(n)	O(n)

QueueList的一个主要问题是，将一个项目排队需要线性时间。使用链表实现，您将其简化为一个常量运算O（1）。您所需要做的就是更新节点的指针。

从表中可以看出QueueLinkedList的主要弱点并不明显。尽管有O（1）性能，但它的开销很高。每个元素都必须具有用于前向和后向引用的额外存储空间。此外，每次创建新元素时，都需要为新节点动态分配相对昂贵的内存。相比之下，QueueList进行批量分配，这样做更快。

您能否消除分配开销并维护dequeues O（1）？如果你不必担心你的队列会超过最大固定大小，那么答案是肯定的！

你要找的是一个环形缓冲区（ring buffer）。例如，您可能有一个有四名玩家的大富翁游戏。您可以使用基于环形缓冲区的队列来跟踪下一个轮到谁。接下来您将了解环形缓冲区的实现

3. Ring Buffer Implementation

环形缓冲区，也称为循环缓冲区，是一个固定大小的列表。一种用于表示一个固定尺寸、头尾相连的缓冲区的数据结构，适合缓存数据流。

首先创建一个固定大小为4的环形缓冲区。环形缓冲区有两个指针，用来跟踪两件事：

read指针跟踪队列的前端。
write指针跟踪下一个可用的插槽，以便您可以覆盖已经读取的现有元素

ring_buffer

class RingBuffer<E> {
  RingBuffer(int length) : _list = List.filled(length, null, growable: false);

  final List<E?> _list;
  int _writeIndex = 0;
  int _readIndex = 0;
  int _size = 0;

  bool get isFull => _size == _list.length;

  bool get isEmpty => _size == 0;

  void write(E element) {
    if (isFull) throw Exception('Buffer is full');
    _list[_writeIndex] = element;
    _writeIndex = _advance(_writeIndex);
    _size++;
  }

  int _advance(int index) {
    return (index == _list.length - 1) ? 0 : index + 1;
  }

  E? read() {
    if (isEmpty) return null;
    final element = _list[_readIndex];
    _readIndex = _advance(_readIndex);
    _size--;
    return element;
  }

  E? get peek => (isEmpty) ? null : _list[_readIndex];

  @override
  String toString() {
    final text = StringBuffer();
    text.write('[');
    int index = _readIndex;
    while (index != _writeIndex) {
      if (index != _readIndex) {
        text.write(', ');
      }
      text.write(_list[index % _list.length]);
      index++;
    }
    text.write(']');
    return text.toString();
  }
}

QueueRingBuffer

class QueueRingBuffer<E> implements Queue<E> {
  // 由于环形缓冲区具有固定大小，因此必须包含长度参数。

  QueueRingBuffer(int length) : _ringBuffer = RingBuffer<E>(length);
  final RingBuffer<E> _ringBuffer;
  // 要将一个元素附加到队列中，只需在_ringBuffer上调用write即可。这会使写入指针增加一。
  // 入队永远是一个O（1）操作。
  @override
  bool enqueue(E element) {
    // 由于队列具有固定的大小，因此现在必须返回true或false来指示元素是否已成功添加。
    if (_ringBuffer.isFull) {
      return false;
    }
    _ringBuffer.write(element);
    return true;
  }

  // 在后台，它检查环形缓冲区是否为空，如果为空，则返回null。
  // 如果不是，则返回缓冲区的读取索引处的项，然后将索引增加1。
  @override
  E? dequeue() => _ringBuffer.read();
  // isEmpty和peek这两者都是O（1）
  @override
  bool get isEmpty => _ringBuffer.isEmpty;
  @override
  E? get peek => _ringBuffer.peek;

  @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]

操作	平均情况	最坏情况
入列	O(1)	O(1)
出列	O(1)	O(1)
空间复杂度	O(n)	O(n)

基于环形缓冲区的队列在入队和出队方面具有与链表实现相同的时间复杂性。
基于环形缓冲区的队列的空间复杂性虽然仍然为O（n），但在像链表实现那样对新元素进行入队时，不需要在内部分配新的内存。但是，环形缓冲区的大小是固定的，这意味着入队可能会失败。

到目前为止，您已经看到了队列的三种实现：简单列表、双链表和环形缓冲区。

这些都以各自的方式很有用，但接下来您将使用两个stack实现一个队列。它的空间局部性优于链表，也不需要像环形缓冲区那样的固定大小。

4. Double-Stack Implementation

您使用的是列表，而不是您在章“堆栈”中创建的堆栈类。
这样做的原因是，您将利用List的一些功能，而您的Stack目前没有这些功能：
first、last和reverse。

使用两个堆栈的想法很简单。每当您将一个元素排入队列时，它都会进入right堆栈。

当您需要将元素出列时，您可以反转right堆栈，将其放置在left堆栈中，然后移除顶部元素。

只有当left堆栈为空时，才需要进行此反转操作，从而使大多数入队和出队操作的时间保持不变。


class QueueStack<E> implements Queue<E> {
  final _leftStack = <E>[];
  final _rightStack = <E>[];
  @override
  bool enqueue(E element) {
    _rightStack.add(element);
    return true;
  }

  @override
  E? dequeue() {
    // 请记住，只有当左堆栈为空时，才能传输右堆栈中的元素！
    if (_leftStack.isEmpty) {
      // 1 如果左侧堆栈为空，请将其设置为右侧堆栈的反转：
      // 是的，反转列表的内容是一种O（n）操作。然而，总体出列成本仍然摊薄为O（1）。
      _leftStack.addAll(_rightStack.reversed);
      // 2 使右侧堆栈无效。由于您已将所有内容转移到左侧，只需清除右侧即可：
      _rightStack.clear();
    }
    if (_leftStack.isEmpty) return null;
    // 3 从左侧堆栈中移除最后一个元素：
    return _leftStack.removeLast();
  }

  // 要检查队列是否为空，只需检查左堆栈和右堆栈是否都为空。
  // 这意味着没有任何元素可以出列，也没有新的元素被入列。
  // O(1)
  @override
  bool get isEmpty => _leftStack.isEmpty && _rightStack.isEmpty;
  // peek是获取最上面的元素。如果左侧堆栈不为空，则此堆栈顶部的元素位于队列的前面。
  // 如果左侧堆栈为空，则右侧堆栈将反转并放置在左侧堆栈中。
  // 在这种情况下，位于右侧堆栈底部的元素是队列中的下一个。
  // O(1)
  @override
  E? get peek => _leftStack.isNotEmpty ? _leftStack.last : _rightStack.first;
  @override
  String toString() {
    final combined = [
      ..._leftStack.reversed,
      ..._rightStack,
    ].join(', ');
    return '[$combined]';
  }

// final queue = QueueStack<String>();
// queue.enqueue("Ray");
// queue.enqueue("Brian");
// final queue = QueueStack<String>();
// queue.enqueue("Ray");
// queue.enqueue("Brian");
}

操作	平均情况	最坏情况
入列	O(1)	O(n)
出列	O(1)	O(n)
空间复杂度	O(n)	O(n)

与基于列表的实现相比，通过利用两个堆栈，您能够将出列转换为摊薄的O（1）操作。

此外，您的两个堆栈实现是完全动态的，并且没有基于环形缓冲区的队列实现所具有的固定大小限制。当正确的队列需要反转或耗尽容量时，最糟糕的性能是O（n）。由于Dart每次都会将容量增加一倍，因此容量不足的情况并不经常发生。

最后，它在空间局部性方面胜过链表。这是因为列表元素在内存块中相邻。因此，在第一次访问时，大量元素将被加载到缓存中。尽管列表需要O（n）来进行简单的复制操作，但在接近内存带宽的情况下，这是一个非常快的O（n）。

Challenge 1: Stack vs. Queue

解释stack和queue之间的区别。为每个数据结构提供两个真实的例子。

queue具有先进先出(FIFO)的行为。先进来的必须先出来。
队列中的项目从后面插入，然后从前面移除。

1. 电影院排队：你会讨厌人们在电影院买票时插队！
1. 打印机：多人可以以类似的先到先得的方式从打印机打印文档

stack具有后进先出(LIFO)的行为。堆栈上的项目在顶部插入，然后从顶部移除。

1. stack：将盘子叠放在一起，每次使用时都要取下最顶部的。这不是比抓住底部的那个容易吗？
1. 撤销功能：想象一下在键盘上输入单词。单击Ctrl-Z将撤消您键入的最新文本。

Challenge 2: Step-by-Step Diagrams

提供分步图，显示以下一系列命令如何在内部影响队列：

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

对以下每个队列实现执行此操作：

List

Linked list

Ring buffer

Double stack

假设列表和环形缓冲区的初始大小为5。

List
请记住，每当列表已满，并且您试图添加一个新元素时，就会创建一个容量是现有元素的两倍的新列表。

Linked List

Ring Buffer

Double Stack

Challenge 3: Whose Turn Is It?

想象一下，你正在和你的朋友玩大富翁游戏。问题是每个人总是忘记该轮到谁了！创建一个大富翁组织者，它总是告诉轮到谁了。下面是一个可以实现的扩展方法：

extension BoardGameManager<E> on QueueRingBuffer<E> {
  E? nextPlayer() {
    final person = dequeue();
    if (person != null) {
      enqueue(person);
    }
    return person;
  }
}

Challenge 4: Double-Ended Queue

双端队列（也称为deque）顾名思义，是一个可以在前面或后面添加或删除元素的队列。

队列（FIFO顺序）允许您将元素添加到后面，并从前面移除。
堆栈（LIFO顺序）允许您将元素添加到后面，然后从后面移除。

Deque可以同时被视为队列和堆栈。

你的挑战是建立一个deque。下面是一个简单的Deque接口，可以帮助您构建数据结构。枚举方向描述是在deque的前面还是后面添加元素还是从中删除元素。您可以使用任何您喜欢的数据结构来构造Deque。

您可以使用循环缓冲区、两个堆栈、一个列表或双链接列表来构建一个。下面的解决方案使用双链接列表来构造Deque。

首先设置双链接列表deque，如下所示：

class DequeDoublyLinkedList<E> implements Deque<E> {
 final _list = DoublyLinkedList<E>();
}

现在，您必须遵守Deque接口。首先，通过检查链表是否为空来实现isEmpty。这是一个O（1）运算。

@override
bool get isEmpty => _list.isEmpty;

接下来，您需要一种从Deque的正面或背面查看value的方法。

@override
E? peek(Direction from) {
 switch (from) {
 case Direction.front:
 return _list.head?.value;
 case Direction.back:
 return _list.tail?.value;
 }
}

要从前面或后面查看元素，请检查列表的头值和尾值。
这是一个O（1）运算。

现在，您需要一种方法来为Deque的正面或背面添加元素。

@override
bool enqueue(E value, Direction to) {
 switch (to) {
 case Direction.front:
 _list.push(value);
 break;
 case Direction.back:
 _list.append(value);
 break;
 }
 return true;
}

在Deque的正面或背面添加元素：

Front：将一个元素推到列表的前面。在内部，链表将更新新节点作为链表的头。
Back：将一个元素追加到列表的后面。类似地，链表将更新新节点作为链表的尾部。

这两个操作都是O（1）操作，因为您所要做的就是更新几个节点的内部指针。

既然您已经有了添加元素的方法，那么如何删除元素呢？

@override
E? dequeue(Direction from) {
 switch (from) {
 case Direction.front:
 return _list.pop();
 case Direction.back:
 return _list.removeLast();
 }
}

从Deque的正面或背面移除元素很简单。

Front：调用pop以删除列表中的head节点。
Back：同样，调用removeLast来移除尾部。

与入队类似，这些是针对双链表的O（1）操作。

最后，覆盖toString，这样您就可以测试您的Deque了。

final deque = DequeDoublyLinkedList<int>();
deque.enqueue(1, Direction.back);
deque.enqueue(2, Direction.back);
deque.enqueue(3, Direction.back);
deque.enqueue(4, Direction.back);
print(deque);
deque.enqueue(5, Direction.front);
print(deque);
deque.dequeue(Direction.back);
deque.dequeue(Direction.back);
deque.dequeue(Direction.back);
deque.dequeue(Direction.front);
deque.dequeue(Direction.front);
deque.dequeue(Direction.front);
print(deque);

[1, 2, 3, 4]
[5, 1, 2, 3, 4]
[]

Kayouyou's Den