Как реализовать стек в Dart?

Как реализовать стек в Dart?

Стек (Stack) — это фундаментальная структура данных, основанная на принципе LIFO (Last In, First Out). В Dart существует несколько способов реализации стека, от встроенных коллекций до создания собственного класса.

Использование встроенного List

Простейший способ — использовать обычный List<T>:

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

  void push(T item) {
    _items.add(item);
  }

  T pop() {
    if (_items.isEmpty) {
      throw Exception("Стек пуст");
    }
    return _items.removeLast();
  }

  T peek() {
    if (_items.isEmpty) {
      throw Exception("Стек пуст");
    }
    return _items.last;
  }

  bool get isEmpty => _items.isEmpty;
  int get size => _items.length;
  void clear() => _items.clear();
}

Использование Queue из dart:collection

Для более эффективной работы можно использовать Queue:

import "dart:collection";

final stack = Queue<int>();
stack.add(10);
stack.add(20);
var top = stack.removeLast();
if (stack.isNotEmpty) print(stack.last);

Применение в Flutter

Практические примеры:

• Навигация и история экранов
• Операции отмены (Undo)
• Проверка парных скобок
• Поиск в глубину (DFS)
• Обратный порядок элементов

Пример проверки скобок

bool isValidBrackets(String s) {
  final stack = <String>[];
  final brackets = {")": "(", "}": "{", "]": "["};

  for (var char in s.split("")) {
    if (brackets.containsValue(char)) {
      stack.add(char);
    } else if (brackets.containsKey(char)) {
      if (stack.isEmpty || stack.removeLast() != brackets[char]) {
        return false;
      }
    }
  }
  return stack.isEmpty;
}

Сложность операций

• Push — O(1) amortized
• Pop — O(1) amortized
• Peek — O(1)
• isEmpty — O(1)

Для большинства приложений Flutter используйте встроенный List<T>. Это просто, эффективно и достаточно. Для специализированных случаев (высокая нагрузка, частые операции спереди) рассмотрите Queue из dart:collection. Создание собственного класса Stack полезно для обучения и когда нужна дополнительная функциональность или контроль над операциями.