How to implement a stack with push and pop in Dart
Solution 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
Solution 2
here is the class I use
import 'dart:collection';
class Stack<T> {
final _stack = Queue<T>();
int get length => _stack.length;
bool canPop() => _stack.isNotEmpty;
void clearStack(){
while(_stack.isNotEmpty){
_stack.removeLast();
}
}
void push(T element) {
_stack.addLast(element);
}
T pop() {
T lastElement = _stack.last;
_stack.removeLast();
return lastElement;
}
T peak() => _stack.last;
}
Solution 3
My version of a Queue wrapper:
import "dart:collection" show Queue;
class Stack<T> {
final Queue<T> _underlyingQueue;
Stack() : this._underlyingQueue = Queue<T>();
int get length => this._underlyingQueue.length;
bool get isEmpty => this._underlyingQueue.isEmpty;
bool get isNotEmpty => this._underlyingQueue.isNotEmpty;
void clear() => this._underlyingQueue.clear();
T peek() {
if (this.isEmpty) {
throw StateError("Cannot peek() on empty stack.");
}
return this._underlyingQueue.last;
}
T pop() {
if (this.isEmpty) {
throw StateError("Cannot pop() on empty stack.");
}
return this._underlyingQueue.removeLast();
}
void push(final T element) => this._underlyingQueue.addLast(element);
}
Solution 4
I modified the other answers' versions, to make use of nullable.
import 'dart:collection';
class StackCollection<T> {
final _queue = Queue<T>();
void push(T element) {
_queue.addLast(element);
}
T? pop() {
return this.isEmpty ? null : _queue.removeLast();
}
void clear() {
_queue.clear();
}
bool get isEmpty => _queue.isEmpty;
bool get isNotEmpty => _queue.isNotEmpty;
int get length => this._queue.length;
}
Also renamed to StackCollection
, to avoid interference from the Stack widget
Comments
-
Suragch over 1 year
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();