Есть ли в Dart встроенная структура данных «стек»?

Question

Есть ли в Dart встроенная структура данных «стек»?

Тип вопроса: Алгоритмы и структуры данных Вероятность: 36% Категория: Flutter Разработчик

Ответ

Специального класса Stack в стандартной библиотеке Dart нет, но его легко и идиоматично реализовать на основе List<T>, используя методы add (для добавления) и removeLast (для извлечения). Это соответствует принципу LIFO (Last In, First Out).

Базовая реализация:

void main() {
  // Использование List как стека
  final stack = <String>[];

  // Push (добавление)
  stack.add('Task 1');
  stack.add('Task 2');
  print(stack); // [Task 1, Task 2]

  // Peek (посмотреть верхний элемент)
  final top = stack.last; // 'Task 2'

  // Pop (извлечение)
  final popped = stack.removeLast(); // 'Task 2'
  print(stack); // [Task 1]
}

Для частого использования удобно создать класс-обертку:

class Stack<T> {
  final List<T> _storage = [];

  void push(T element) => _storage.add(element);
  T pop() => _storage.removeLast();
  T get peek => _storage.last;
  bool get isEmpty => _storage.isEmpty;
  bool get isNotEmpty => _storage.isNotEmpty;
  int get length => _storage.length;

  @override
  String toString() => 'Stack(${_storage.reversed.join(' <- ')})';
}

// Пример использования
final historyStack = Stack<String>();
historyStack.push('/home');
historyStack.push('/settings');
print(historyStack.pop()); // /settings
print(historyStack.peek); // /home

Типичные сценарии использования в разработке на Flutter:

Навигация: Управление историей маршрутов (хотя Navigator делает это сам).
Отмена действий (Undo): Хранение состояний для возможности отката.
Алгоритмы: Обход деревьев (например, виджет-дерева для кастомных инспекторов), парсинг выражений, проверка сбалансированности скобок.

Ответ 18+ 🔞

А, ну вот, опять про стеки спрашивают! Слушай, тут история простая, как три копейки, но некоторые народ, бля, так охуевают, когда узнают, что отдельного класса Stack в Дарете нет. Ну да, ёпта, нет его, и всё тут. Но это не повод для волнения ебать, потому что реализовать его — это раз плюнуть.

Представь себе обычный List<T>. Вот он у тебя есть. Так вот, если ты будешь добавлять элементы только в конец методом add, а вытаскивать только последний через removeLast — поздравляю, ты только что изобрел стек, сам того не зная! Это и есть принцип LIFO — последний зашел, первый вышел. Как в пробке, когда самый наглый пытается вылезти вперёд, а его все посылают нахуй обратно.

Вот, смотри, как это выглядит в коде, элементарно:

void main() {
  // Берёшь лист и делаешь вид, что это стек. Все так делают.
  final stack = <String>[];

  // Запихиваешь (push) задачу в конец
  stack.add('Task 1');
  stack.add('Task 2');
  print(stack); // [Task 1, Task 2]

  // Подсмотреть (peek), что наверху, не трогая
  final top = stack.last; // 'Task 2'

  // Выдернуть (pop) верхнюю таску
  final popped = stack.removeLast(); // 'Task 2'
  print(stack); // [Task 1] - вот и вся магия
}

Но если ты, как нормальный человек, не хочешь каждый раз писать removeLast и боишься случайно insert в середину нахуйрить, то можно, конечно, завернуть это дело в красивый класс. Чтобы было приятно и идиоматично.

Вот тебе класс-обёртка, чтоб не париться:

class Stack<T> {
  // Внутри всё тот же лист, просто мы с ним по-особенному играем
  final List<T> _storage = [];

  void push(T element) => _storage.add(element); // Запихнул
  T pop() => _storage.removeLast(); // Выдернул
  T get peek => _storage.last; // Подсмотрел
  bool get isEmpty => _storage.isEmpty; // Пустой?
  bool get isNotEmpty => _storage.isNotEmpty; // Не пустой?
  int get length => _storage.length; // Сколько там всего

  // Чтобы красиво печаталось, типа "Stack(верхний <- средний <- нижний)"
  @override
  String toString() => 'Stack(${_storage.reversed.join(' <- ')})';
}

// Ну и пользуйся на здоровье
final historyStack = Stack<String>();
historyStack.push('/home');
historyStack.push('/settings');
print(historyStack.pop()); // /settings - последний зашёл, первый вышел
print(historyStack.peek); // /home - теперь это наверху

А где это, блядь, вообще применяется? Да везде!

Навигация в приложении: Ну, историю переходов туда-сюда хранить. Хотя во Flutter'овском Navigator это уже под капотом сделано, тебе париться не надо.
Отмена действий (Undo): Это классика! Каждое состояние сохраняешь в стек, захотел откатиться — pop, и готово. Пользователь доволен, ты не в говне.
Разные алгоритмы: Ну там, обход деревьев (например, своё кастомное виджет-дерево лазить), парсинг каких-нибудь выражений или проверка, правильно ли расставлены скобки в коде. Последнее — это вообще задачка на раз плюнуть со стеком.

Вот и вся наука. Ничего сложного, просто нужно понять принцип: последний зашёл — первый вышел. Как в плохом баре в час пик.