如何在 Dart 中使用 push 和 pop 实现堆栈

Question

我想在 Dart 中实现一个堆栈数据结构（不要与 Flutter Stack 小部件混淆），以便我可以处理一堆用于 Flutter 文本渲染的自定义 TextStyles。

我知道使用堆栈可以压入和弹出值。这听起来与 Queue 类似，但我不确定它们之间的区别。

这行不通：

final myStack = Queue<int>();
myStack.push(1);
final top = myStack.pop();

Answer 1

堆栈是一种first-in-last-out (FILO) 数据结构。如果你做一堆书，你放下的第一本书将被你堆在它上面的任何其他书覆盖。除非你移除上面的所有其他书籍，否则你无法取回那本书。

实施

您可以通过多种不同的方式实现堆栈。这个答案的原始版本（参见 edit history) used a Queue as the underlying data structure. However, the default Dart Queue itself uses a list，所以 List 似乎是更直接的方法。下面是我现在如何实现堆栈：

class Stack<E> {
  final _list = <E>[];

  void push(E value) => _list.add(value);

  E pop() => _list.removeLast();

  E get peek => _list.last;

  bool get isEmpty => _list.isEmpty;
  bool get isNotEmpty => _list.isNotEmpty;

  @override
  String toString() => _list.toString();
}

备注:

到push的意思是往栈顶加一个值。这是用 _list.add 实现的，这是一个快速的 O(1) 操作。
到pop表示从栈顶取出一个值。这是用 _list.removeLast 实现的，这是一个快速的 O(1) 操作。
To peek 意思是获取栈顶元素的值，而不用实际移除它。这是用 _list.last 实现的，这是一个快速的 O(1) 操作。

可空实现

当使用上述堆栈实现时，您通常会在尝试 pop 或 peek 之前检查 isNotEmpty，因为在空堆栈上这样做会导致底层 List 抛出错误。但是，如果您更愿意检查 null，则可以使 pop 和 peek 可为空：

E? pop() => (isEmpty) ? null : _list.removeLast();

E? get peek => (isEmpty) ? null : _list.last;

用法

您可以像这样使用您的 Stack：

void main() {
  final myStack = Stack<String>();

  myStack.push('Green Eggs and Ham');
  myStack.push('War and Peace');
  myStack.push('Moby Dick');

  while (myStack.isNotEmpty) {
    print(myStack.pop());
  }
}

这是输出：

Moby Dick
War and Peace
Green Eggs and Ham

Answer 2

这是我用的class

import 'dart:collection';

class Stack<T> {
  final _stack = Queue<T>();

  int get length => _stack.length;

  bool canPop() => _stack.isNotEmpty;
  
  void clearStack(){
    while(_stack.isNotEmpty){
      _stack.removeLast();
    }
  }

  void push(T element) {
    _stack.addLast(element);
  }

  T pop() {
    T lastElement = _stack.last;
    _stack.removeLast();
    return lastElement;
  }

  T peak() => _stack.last;

}

Answer 3

我的队列包装器版本：

import "dart:collection" show Queue;

class Stack<T> {
  final Queue<T> _underlyingQueue;

  Stack() : this._underlyingQueue = Queue<T>();

  int get length => this._underlyingQueue.length;
  bool get isEmpty => this._underlyingQueue.isEmpty;
  bool get isNotEmpty => this._underlyingQueue.isNotEmpty;

  void clear() => this._underlyingQueue.clear();

  T peek() {
    if (this.isEmpty) {
      throw StateError("Cannot peek() on empty stack.");
    }
    return this._underlyingQueue.last;
  }

  T pop() {
    if (this.isEmpty) {
      throw StateError("Cannot pop() on empty stack.");
    }
    return this._underlyingQueue.removeLast();
  }

  void push(final T element) => this._underlyingQueue.addLast(element);
}

Answer 4

我修改了其他答案的版本，以使用 nullable。

import 'dart:collection';

class StackCollection<T> {
  final _queue = Queue<T>();

  void push(T element) {
    _queue.addLast(element);
  }

  T? pop() {
    return this.isEmpty ? null : _queue.removeLast();
  }

  void clear() {
    _queue.clear();
  }

  bool get isEmpty => _queue.isEmpty;
  bool get isNotEmpty => _queue.isNotEmpty;
  int get length => this._queue.length;
}

也改名为StackCollection，避免Stack widget

的干扰

如何在 Dart 中使用 push 和 pop 实现堆栈

How to implement a stack with push and pop in Dart

queue

stack

dart

flutter

实施

可空实现

用法