Kayouyou's Den

class Stack<E> {
  Stack() : _storage = <E>[];

  Stack.of(Iterable<E> elements) : _storage = List<E>.of(elements);

  final List<E> _storage;

  void push(E element) => _storage.add(element);

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

  E get peek => _storage.last;

  bool get isEmpty => _storage.isEmpty;

  bool get isNotEmpty => !isEmpty;

  @override
  String toString() {
    return '--- Top ---\n'
        '${_storage.reversed.join('\n')}'
        '\n-----------';
  }

  /* 问题1： 反转列表
   * 将所有列表元素推入Stack的时间复杂度为O（n）。
   * 弹出Stack打印值的时间复杂度也是O（n）。
   * 总体而言，该算法的时间复杂度为O（n）
   */
  void printInReverse<E>(List<E> list) {
    var stack = Stack<E>();
    for (E value in list) {
      stack.push(value);
    }
    while (stack.isNotEmpty) {
      print(stack.pop());
    }
  }

  /* 问题2： 检查字符串中的()括号
   * 该算法的时间复杂度为O（n），其中n是字符串中代码单元的数量。
   * 该算法还由于使用Stack数据结构而导致O（n）空间复杂度。
   */
  bool checkParentheses(String text) {
    var stack = Stack<int>();
    final open = '('.codeUnitAt(0);
    final close = ')'.codeUnitAt(0);
    for (int codeUnit in text.codeUnits) {
      if (codeUnit == open) {
        stack.push(codeUnit);
      } else if (codeUnit == close) {
        if (stack.isEmpty) {
          return false;
        } else {
          stack.pop();
        }
      }
    }
    return stack.isEmpty;
  }
}