How do you implement a stack and queue in Dart?
TL;DR: Stack (LIFO): use List with add/removeLast. Queue (FIFO): use dart:collection Queue with addLast/removeFirst. Both O(1) for add/remove. Stack is used for undo/redo, navigation history; Queue for BFS and task scheduling.
Full Answer
Stack and Queue are fundamental data structures with opposite insertion/removal patterns. Both appear in Flutter: Navigator uses a stack, BFS traversal uses a queue.
| Aspect | Stack (LIFO) | Queue (FIFO) |
|---|---|---|
| Order | Last In, First Out | First In, First Out |
| Add | push (add to top) | enqueue (add to back) |
| Remove | pop (from top) | dequeue (from front) |
| Dart | List.add() / removeLast() | Queue.addLast() / removeFirst() |
Flutter's Navigator is a stack of routes: Navigator.push() adds to the top, Navigator.pop() removes from the top. Understanding this makes navigation debugging intuitive.
Code Examples
3 A true false
Common Mistakes
- ✗Using List.removeAt(0) for a queue — O(n) instead of Queue.removeFirst() which is O(1)
- ✗Calling pop/peek on an empty stack — throws RangeError; always check isEmpty first
Interview Tip
Balanced parentheses is the canonical stack interview question. Undo/redo in a text editor is another. BFS of a widget tree uses a queue — these real-world connections impress interviewers.