Implement a Stack data structure in Dart with operations: push, pop, peek, isEmpty, and size. Use it to check if parentheses are balanced in an expression.

Overview

Stack is a fundamental linear data structure that follows the Last-In-First-Out (LIFO) principle. Think of it like a stack of plates: you can only add or remove plates from the top. The last plate you put on is the first one you take off.

Stacks are essential in computer science for function call management, undo/redo operations, expression evaluation, backtracking algorithms, and browser history. Understanding stacks is crucial for solving many algorithmic problems and is a common interview topic.

Key characteristics:

• LIFO (Last-In-First-Out) access pattern
• Insertion and deletion from one end only (top)
• O(1) time for push, pop, and peek operations
• Used extensively in recursion and parsing

When to use:

• Function call stack (built into languages)
• Undo/redo functionality
• Browser back/forward navigation
• Balanced parentheses checking
• Depth-first search (DFS) algorithms
• Expression evaluation (postfix, prefix)

Core Concepts

Stack Operations:

1. Push: Add element to top - O(1)
2. Pop: Remove and return top element - O(1)
3. Peek: View top element without removing - O(1)
4. isEmpty: Check if stack is empty - O(1)
5. size: Get number of elements - O(1)

LIFO Visualization:

textCopy
Push(1) → Push(2) → Push(3) → Pop()
   |         |          |         |
  [1]    [1, 2]    [1, 2, 3]  [1, 2]  (3 removed)
   ↑         ↑          ↑         ↑
  top       top        top       top

Implementation Approach 1: Array-Based Stack

Using Dart's

List

dartCopy
class Stack<T> {
  final List<T> _items = [];

  /// Add element to top of stack
  void push(T item) {
    _items.add(item);
  }

  /// Remove and return top element
  T pop() {
    if (isEmpty) {
      throw StateError('Cannot pop from empty stack');
    }
    return _items.removeLast();
  }

  /// View top element without removing
  T peek() {
    if (isEmpty) {
      throw StateError('Cannot peek empty stack');
    }
    return _items.last;
  }

  /// Check if stack is empty
  bool get isEmpty => _items.isEmpty;

  /// Check if stack has elements
  bool get isNotEmpty => _items.isNotEmpty;

  /// Get number of elements
  int get size => _items.length;

  /// Clear all elements
  void clear() {
    _items.clear();
  }

  @override
  String toString() => _items.toString();
}

void main() {
  var stack = Stack<int>();

  stack.push(10);
  stack.push(20);
  stack.push(30);
  print('Stack: $stack');  // [10, 20, 30]

  print('Peek: ${stack.peek()}');  // 30
  print('Pop: ${stack.pop()}');    // 30
  print('Stack after pop: $stack'); // [10, 20]
  print('Size: ${stack.size}');     // 2
}

Operations Complexity:

• Push: O(1) - add to end of list
• Pop: O(1) - remove from end of list
• Peek: O(1) - access last element
• isEmpty: O(1) - check list length
• Space: O(n) - stores n elements

Implementation Approach 2: Linked-List-Based Stack

Using a custom linked list for potentially better memory management.

dartCopy
class Node<T> {
  T data;
  Node<T>? next;
  Node(this.data, [this.next]);
}

class LinkedStack<T> {
  Node<T>? _top;
  int _size = 0;

  /// Add element to top
  void push(T item) {
    _top = Node(item, _top);
    _size++;
  }

  /// Remove and return top element
  T pop() {
    if (isEmpty) {
      throw StateError('Cannot pop from empty stack');
    }
    final data = _top!.data;
    _top = _top!.next;
    _size--;
    return data;
  }

  /// View top element
  T peek() {
    if (isEmpty) {
      throw StateError('Cannot peek empty stack');
    }
    return _top!.data;
  }

  bool get isEmpty => _top == null;
  bool get isNotEmpty => _top != null;
  int get size => _size;

  void clear() {
    _top = null;
    _size = 0;
  }

  @override
  String toString() {
    if (isEmpty) return '[]';
    final items = <T>[];
    var current = _top;
    while (current != null) {
      items.add(current.data);
      current = current.next;
    }
    return items.reversed.toList().toString();
  }
}

void main() {
  var stack = LinkedStack<String>();

  stack.push('First');
  stack.push('Second');
  stack.push('Third');

  print('Top: ${stack.peek()}');  // Third
  print('Pop: ${stack.pop()}');   // Third
  print('Size: ${stack.size}');   // 2
}

Operations Complexity:

• Push: O(1) - add new head node
• Pop: O(1) - remove head node
• Peek: O(1) - access head node
• Space: O(n) - n nodes + references

Complete Production Class

Full-featured stack with capacity limits and iteration support.

dartCopy
class ProductionStack<T> {
  final List<T> _items = [];
  final int? _maxCapacity;

  ProductionStack({int? maxCapacity}) : _maxCapacity = maxCapacity;

  /// Push with overflow check
  void push(T item) {
    if (_maxCapacity != null && _items.length >= _maxCapacity!) {
      throw StateError('Stack overflow: max capacity $_maxCapacity reached');
    }
    _items.add(item);
  }

  /// Pop with underflow check
  T pop() {
    if (isEmpty) {
      throw StateError('Stack underflow: cannot pop from empty stack');
    }
    return _items.removeLast();
  }

  /// Safe pop - returns null instead of throwing
  T? tryPop() {
    return isEmpty ? null : _items.removeLast();
  }

  /// Peek with check
  T peek() {
    if (isEmpty) {
      throw StateError('Cannot peek empty stack');
    }
    return _items.last;
  }

  /// Safe peek
  T? tryPeek() {
    return isEmpty ? null : _items.last;
  }

  /// Push multiple items
  void pushAll(Iterable<T> items) {
    for (var item in items) {
      push(item);
    }
  }

  /// Pop multiple items
  List<T> popN(int n) {
    if (n > size) {
      throw StateError('Cannot pop $n items from stack of size $size');
    }
    final result = <T>[];
    for (int i = 0; i < n; i++) {
      result.add(pop());
    }
    return result;
  }

  /// Check if contains element
  bool contains(T item) => _items.contains(item);

  /// Convert to list (top to bottom)
  List<T> toList() => _items.reversed.toList();

  bool get isEmpty => _items.isEmpty;
  bool get isNotEmpty => _items.isNotEmpty;
  int get size => _items.length;
  int? get capacity => _maxCapacity;
  bool get isFull => _maxCapacity != null && size >= _maxCapacity!;

  void clear() => _items.clear();

  @override
  String toString() => 'Stack(${_items.reversed.toList()})';
}

Use Case Example: Balanced Parentheses Checker

Classic stack application to validate if parentheses/brackets are balanced.

dartCopy
/// Check if parentheses are balanced in an expression
bool isBalanced(String expression) {
  final stack = Stack<String>();
  final openBrackets = {'(', '[', '{'};
  final closeBrackets = {')', ']', '}'};
  final matchingPairs = {')': '(', ']': '[', '}': '{'};

  for (int i = 0; i < expression.length; i++) {
    String char = expression[i];

    // Push opening brackets
    if (openBrackets.contains(char)) {
      stack.push(char);
    }
    // Check closing brackets
    else if (closeBrackets.contains(char)) {
      if (stack.isEmpty) {
        return false;  // Closing without opening
      }
      String top = stack.pop();
      if (top != matchingPairs[char]) {
        return false;  // Mismatched pair
      }
    }
    // Ignore other characters
  }

  // All brackets should be matched
  return stack.isEmpty;
}

void main() {
  // Test cases
  print(isBalanced('()')); // true
  print(isBalanced('()[]{}')); // true
  print(isBalanced('([])')); // true
  print(isBalanced('([)]')); // false - wrong nesting
  print(isBalanced('(((')); // false - unclosed
  print(isBalanced('())')); // false - extra closing
  print(isBalanced('{[()]}')); // true
  print(isBalanced('if (a > b) { return [1, 2]; }')); // true
}

How it works:

1. Push all opening brackets onto stack
2. For closing brackets, pop and verify match
3. At end, stack should be empty (all matched)

Use Case Example: Browser History

Implement browser back/forward navigation using two stacks.

dartCopy
class BrowserHistory {
  final Stack<String> _backStack = Stack();
  final Stack<String> _forwardStack = Stack();
  String _currentPage;

  BrowserHistory(this._currentPage);

  /// Visit new page
  void visit(String url) {
    _backStack.push(_currentPage);
    _currentPage = url;
    _forwardStack.clear();  // Clear forward history
  }

  /// Go back one page
  String? back() {
    if (_backStack.isEmpty) return null;

    _forwardStack.push(_currentPage);
    _currentPage = _backStack.pop();
    return _currentPage;
  }

  /// Go forward one page
  String? forward() {
    if (_forwardStack.isEmpty) return null;

    _backStack.push(_currentPage);
    _currentPage = _forwardStack.pop();
    return _currentPage;
  }

  String get current => _currentPage;
  bool get canGoBack => _backStack.isNotEmpty;
  bool get canGoForward => _forwardStack.isNotEmpty;
}

void main() {
  var browser = BrowserHistory('google.com');

  browser.visit('youtube.com');
  browser.visit('github.com');
  print('Current: ${browser.current}'); // github.com

  browser.back();
  print('After back: ${browser.current}'); // youtube.com

  browser.back();
  print('After back: ${browser.current}'); // google.com

  browser.forward();
  print('After forward: ${browser.current}'); // youtube.com
}

Comparison Table

Operations Reference

Quick Reference Card:

dartCopy
// Create stack
var stack = Stack<int>();

// Basic operations
stack.push(10);          // Add to top - O(1)
int top = stack.pop();   // Remove top - O(1)
int view = stack.peek(); // View top - O(1)

// Status checks
bool empty = stack.isEmpty;     // O(1)
int count = stack.size;          // O(1)

// Utilities
stack.clear();           // Remove all - O(1)
print(stack);            // Display stack

Edge Cases

dartCopy
void testEdgeCases() {
  var stack = Stack<int>();

  // 1. Pop from empty stack
  try {
    stack.pop();  // Throws StateError
  } catch (e) {
    print('Error: $e');
  }

  // 2. Peek empty stack
  try {
    stack.peek();  // Throws StateError
  } catch (e) {
    print('Error: $e');
  }

  // 3. Safe operations
  var safeStack = ProductionStack<int>();
  print(safeStack.tryPop());  // null (no error)
  print(safeStack.tryPeek()); // null (no error)

  // 4. Single element
  stack.push(42);
  assert(stack.peek() == 42);
  assert(stack.pop() == 42);
  assert(stack.isEmpty);

  // 5. Stack overflow (with capacity)
  var limited = ProductionStack<int>(maxCapacity: 3);
  limited.push(1);
  limited.push(2);
  limited.push(3);
  try {
    limited.push(4);  // Throws - capacity exceeded
  } catch (e) {
    print('Overflow: $e');
  }

  // 6. Null values (if nullable type)
  var nullStack = Stack<int?>();
  nullStack.push(null);  // Valid for nullable types
  assert(nullStack.pop() == null);
}

Best Practices

1. Use Generic Types

dartCopy
// ✅ Good - type safe
var intStack = Stack<int>();
var stringStack = Stack<String>();

// ❌ Bad - no type safety (avoid dynamic)
var badStack = Stack<dynamic>();

2. Check Before Pop/Peek

dartCopy
// ✅ Good - safe access
if (stack.isNotEmpty) {
  int value = stack.pop();
}

// ❌ Bad - may throw exception
int value = stack.pop();  // Crashes if empty!

// ✅ Better - use try methods
int? value = stack.tryPop();
if (value != null) {
  // Use value
}

3. Use Dart's Built-in for Simple Cases

dartCopy
// ❌ Overkill for simple tracking
var stack = Stack<String>();
stack.push('a');
stack.push('b');

// ✅ Simple list is fine for basic LIFO
var list = <String>[];
list.add('a');  // push
list.add('b');
String last = list.removeLast();  // pop

4. Set Capacity Limits for Production

dartCopy
// ✅ Good - prevent memory issues
var callStack = ProductionStack<Function>(maxCapacity: 1000);

// ❌ Bad - unbounded growth in production
var unbounded = Stack<Function>();  // Could grow indefinitely

Interview Tips

Common Interview Questions:

Q: "Implement a stack from scratch"

• Show both array and linked list implementations
• Explain trade-offs (array: cache-friendly; linked: no resize)
• Implement all core operations with O(1) complexity

Q: "Check balanced parentheses"

• Classic stack problem
• Handle multiple bracket types: ( ) [ ] { }
• Watch for edge cases: empty string, no brackets, mismatched

Q: "How does the call stack work?"

• Each function call pushes stack frame
• Contains local variables, return address
• LIFO: last called function returns first
• Stack overflow when too deep recursion

Q: "Implement min stack - get minimum in O(1)"

• Use auxiliary stack to track minimums
• Push to min stack when new minimum found
• Pop from both stacks together

Follow-up Questions:

• "Stack vs Queue?" → LIFO vs FIFO, different use cases
• "When to use stack?" → DFS, backtracking, undo, parsing
• "Array vs Linked implementation?" → Array better for cache, linked for dynamic size
• "How to reverse a string using stack?" → Push all chars, pop to build reversed

Red Flags to Avoid:

• Not handling empty stack errors ❌
• Confusing stack with queue (FIFO) ❌
• Not knowing real-world applications ❌
• Implementing without generics ❌

Real-World Applications

1. Function Call Stack (Built into Dart VM)

dartCopy
void first() {
  print('In first');
  second();
  print('Back in first');
}

void second() {
  print('In second');
  third();
  print('Back in second');
}

void third() {
  print('In third');
}

// Call stack visualization:
// first() called  → [first]
// second() called → [first, second]
// third() called  → [first, second, third]
// third() returns → [first, second]
// second() returns → [first]
// first() returns → []

2. Undo/Redo in Text Editor

dartCopy
class TextEditor {
  String _text = '';
  final Stack<String> _undoStack = Stack();
  final Stack<String> _redoStack = Stack();

  void type(String newText) {
    _undoStack.push(_text);
    _text = newText;
    _redoStack.clear();
  }

  void undo() {
    if (_undoStack.isEmpty) return;
    _redoStack.push(_text);
    _text = _undoStack.pop();
  }

  void redo() {
    if (_redoStack.isEmpty) return;
    _undoStack.push(_text);
    _text = _redoStack.pop();
  }

  String get text => _text;
}

3. Expression Evaluation (Postfix)

dartCopy
int evaluatePostfix(String expression) {
  final stack = Stack<int>();
  final tokens = expression.split(' ');

  for (var token in tokens) {
    if (int.tryParse(token) != null) {
      stack.push(int.parse(token));
    } else {
      int b = stack.pop();
      int a = stack.pop();
      switch (token) {
        case '+': stack.push(a + b); break;
        case '-': stack.push(a - b); break;
        case '*': stack.push(a * b); break;
        case '/': stack.push(a ~/ b); break;
      }
    }
  }

  return stack.pop();
}

// Example: "3 4 + 2 *" = (3 + 4) * 2 = 14

4. Flutter Navigation Stack

dartCopy
// Flutter's Navigator uses a stack internally
Navigator.push(context, MaterialPageRoute(...));  // Push route
Navigator.pop(context);  // Pop route

// Back button pops from navigation stack

Resources

• Stack (Data Structure) - Wikipedia
• Dart List API - Built-in Stack Operations
• Stack Visualization