How to implement a stack with push and pop in Dart

Question

I'd like to implement a stack data structure (not to be confused with the Flutter Stack widget) in Dart so that I can handle a stack of custom TextStyles for Flutter text rendering.

I know with stack you can push and pop values. This sounds similar to Queue, but I'm not sure of the difference.

This doesn't work:

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

Answer 1

A stack is a first-in-last-out (FILO) data structure. If you make a stack of books, the first book you put down will be covered by any other books that you stack on top of it. And you can't get that book back until you remove all of the other books on top of it.

Implementation

You can implement a stack a number of different ways. The original version of this answer (see edit history) used a Queue as the underlying data structure. However, the default Dart Queue itself uses a list, so it seems like a List is the more straightforward approach. Here is how I would implement a stack now:

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();
}

Notes:

• To push means to add a value to the top of the stack. This is implemented here with _list.add, which is a fast O(1) operation.
• To pop means to remove a value from the top of the stack. This is implemented here with _list.removeLast, which is a fast O(1) operation.
• To peek means to get the value of the top element in the stack without actually removing it. This is implemented here with _list.last, which is a fast O(1) operation.

Nullable implementation

When using the above implementation of stack, you would normally check isNotEmpty before trying to pop or peek because doing so on an empty stack would cause the underlying List to throw an error. However, if you prefer to check for null instead, you can make pop and peek nullable:

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

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

Usage

You can use your Stack like so:

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());
  }
}

This is the output:

Moby Dick
War and Peace
Green Eggs and Ham