What is Stack and implementing Stack in Dart

stack-in-dart.md

A stack implements LIFO (last-in first-out) ordering.

It uses the operations:

• push(item): push an item to the top of the stack
• pop(): Remove the top item in the stack
• peek(): Return the top of the stack
• isEmpty(): Return true if and on if the stack is empty

There are several places that we can use Stack but it may appear in recursive operations the most. For example, when part of the recursive function fails and you want to roll back everything, Stack sounds like a good plan for that.

                    -----push()        ------> pop()
                            |          | 
                           \|/        /|\    

                        |        ++top++        | <----------- Top
                        |                       | 
                        |         ++++          |
                        |                       | 
                        |         ++++          |
                        |                       |
                        |         ++++          |
                        |                       |
                        |         ++++          |
                        |                       |
                        |         ++++          |
                        |                       |
                        |         ++++          |
                        |                       |
                        |      ++bottom++       | <----------- Bottom
                        |_______________________|
                                Stack

We can implement a simple stack in dart as follow:

class NoSuchElementException implements Exception {}

class StackNode<T> {
  StackNode(this.data);
  T data;
  StackNode<T> next;

  @override
  String toString() {
    return '{ Data: $data, Next: $next }';
  }
}

class Stack<T> {
  StackNode<T> top;

  void push(T item) {
    final t = StackNode<T>(item);
    t.next = top;
    top = t;
  }

  T pop() {
    if (top == null) {
      throw NoSuchElementException();
    }

    final data = top.data;
    top = top.next;
    return data;
  }

  T peek() {
    if (top == null) {
      throw NoSuchElementException();
    }

    return top.data;
  }

  bool isEmpty() {
    return top == null;
  }

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

// Examples
void main() {
  final Stack q1 = Stack<int>()..push(2)..push(3)..push(4)..push(5);
  print('Stack: $q1');
  print('Peek: ${q1.peek()}');
  print('pop: ${q1.pop()}');
  print('Stack: $q1');
}