Implement a Queue data structure in Dart with operations: enqueue, dequeue, peek, isEmpty, and size. Demonstrate its use in a breadth-first search scenario.

Overview

Queue is a fundamental linear data structure that follows the First-In-First-Out (FIFO) principle. Think of it like a line at a store: the first person who joins the line is the first person to be served. Elements are added at the rear (back) and removed from the front.

Queues are essential for task scheduling, breadth-first search (BFS), handling requests in web servers, print job management, and asynchronous processing. Understanding queues is crucial for system design and is frequently tested in technical interviews.

Key characteristics:

• FIFO (First-In-First-Out) access pattern
• Insertion at rear (enqueue), deletion from front (dequeue)
• O(1) time for enqueue and dequeue operations (when properly implemented)
• Used extensively in BFS and level-order traversal

When to use:

• Task/job scheduling (print queue, CPU scheduling)
• Breadth-first search (BFS) algorithms
• Request handling (web servers, message queues)
• Buffer for data streams
• Event handling in UI frameworks

Core Concepts

Queue Operations:

1. Enqueue: Add element to rear - O(1)
2. Dequeue: Remove element from front - O(1)
3. Peek/Front: View front element without removing - O(1)
4. isEmpty: Check if queue is empty - O(1)
5. size: Get number of elements - O(1)

FIFO Visualization:

textCopy
Enqueue(1) → Enqueue(2) → Enqueue(3) → Dequeue()
    |             |             |           |
  Front→[1]    [1, 2]      [1, 2, 3]     [2, 3]
   Rear→ ↑      ↑   ↑       ↑      ↑      ↑  ↑
            Front Rear    Front   Rear  Front Rear

Implementation Approach 1: List-Based Queue (Simple)

Using Dart's

List

add

removeAt(0)

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

  /// Add element to rear of queue
  void enqueue(T item) {
    _items.add(item);
  }

  /// Remove and return front element
  T dequeue() {
    if (isEmpty) {
      throw StateError('Cannot dequeue from empty queue');
    }
    return _items.removeAt(0);  // ⚠️ O(n) operation!
  }

  /// View front element
  T peek() {
    if (isEmpty) {
      throw StateError('Cannot peek empty queue');
    }
    return _items.first;
  }

  bool get isEmpty => _items.isEmpty;
  bool get isNotEmpty => _items.isNotEmpty;
  int get size => _items.length;

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

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

void main() {
  var queue = SimpleQueue<String>();

  queue.enqueue('First');
  queue.enqueue('Second');
  queue.enqueue('Third');
  print('Queue: $queue');  // [First, Second, Third]

  print('Dequeue: ${queue.dequeue()}');  // First
  print('After dequeue: $queue');  // [Second, Third]
  print('Peek: ${queue.peek()}');  // Second
}

Problem:

removeAt(0)

Operations Complexity:

• Enqueue: O(1) - add to end
• Dequeue: O(n) - remove from start (shifts all elements)
• Peek: O(1) - access first element
• Space: O(n)

Implementation Approach 2: Circular Queue (Optimized)

Use a fixed-size array with front and rear pointers. This achieves O(1) for all operations.

dartCopy
class CircularQueue<T> {
  late List<T?> _items;
  int _front = 0;
  int _rear = 0;
  int _size = 0;
  final int _capacity;

  CircularQueue(int capacity) : _capacity = capacity {
    _items = List.filled(capacity, null);
  }

  /// Add element to rear - O(1)
  void enqueue(T item) {
    if (isFull) {
      throw StateError('Queue overflow: capacity $_capacity reached');
    }
    _items[_rear] = item;
    _rear = (_rear + 1) % _capacity;  // Wrap around
    _size++;
  }

  /// Remove and return front element - O(1)
  T dequeue() {
    if (isEmpty) {
      throw StateError('Cannot dequeue from empty queue');
    }
    final item = _items[_front] as T;
    _items[_front] = null;  // Clear reference
    _front = (_front + 1) % _capacity;  // Wrap around
    _size--;
    return item;
  }

  /// View front element - O(1)
  T peek() {
    if (isEmpty) {
      throw StateError('Cannot peek empty queue');
    }
    return _items[_front] as T;
  }

  bool get isEmpty => _size == 0;
  bool get isNotEmpty => _size > 0;
  bool get isFull => _size == _capacity;
  int get size => _size;
  int get capacity => _capacity;

  void clear() {
    _items = List.filled(_capacity, null);
    _front = 0;
    _rear = 0;
    _size = 0;
  }

  @override
  String toString() {
    if (isEmpty) return '[]';
    final result = <T>[];
    int index = _front;
    for (int i = 0; i < _size; i++) {
      result.add(_items[index] as T);
      index = (index + 1) % _capacity;
    }
    return result.toString();
  }
}

void main() {
  var queue = CircularQueue<int>(5);

  queue.enqueue(10);
  queue.enqueue(20);
  queue.enqueue(30);
  print('Queue: $queue');  // [10, 20, 30]

  print('Dequeue: ${queue.dequeue()}');  // 10
  print('Dequeue: ${queue.dequeue()}');  // 20

  queue.enqueue(40);
  queue.enqueue(50);
  queue.enqueue(60);  // Uses wrap-around!
  print('After wrap: $queue');  // [30, 40, 50, 60]
}

Operations Complexity:

• Enqueue: O(1) - just increment rear pointer
• Dequeue: O(1) - just increment front pointer
• Peek: O(1)
• Space: O(capacity)

Complete Production Class

Full-featured queue with safe operations and utilities.

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

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

  /// Enqueue with overflow check
  void enqueue(T item) {
    if (_maxCapacity != null && size >= _maxCapacity!) {
      throw StateError('Queue overflow: max capacity $_maxCapacity reached');
    }
    _items.add(item);
  }

  /// Dequeue with underflow check
  T dequeue() {
    if (isEmpty) {
      throw StateError('Queue underflow: cannot dequeue from empty queue');
    }
    final item = _items[_front];
    _front++;

    // Cleanup when 50% wasted space
    if (_front > _items.length ~/ 2) {
      _items.removeRange(0, _front);
      _front = 0;
    }

    return item;
  }

  /// Safe dequeue - returns null instead of throwing
  T? tryDequeue() {
    return isEmpty ? null : dequeue();
  }

  /// Peek with check
  T peek() {
    if (isEmpty) {
      throw StateError('Cannot peek empty queue');
    }
    return _items[_front];
  }

  /// Safe peek
  T? tryPeek() {
    return isEmpty ? null : _items[_front];
  }

  /// Enqueue multiple items
  void enqueueAll(Iterable<T> items) {
    for (var item in items) {
      enqueue(item);
    }
  }

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

  /// Check if contains element
  bool contains(T item) {
    for (int i = _front; i < _items.length; i++) {
      if (_items[i] == item) return true;
    }
    return false;
  }

  /// Convert to list
  List<T> toList() {
    if (isEmpty) return [];
    return _items.sublist(_front);
  }

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

  void clear() {
    _items.clear();
    _front = 0;
  }

  @override
  String toString() => 'Queue(\${toList()})';
}

Use Case Example: Breadth-First Search (BFS)

BFS explores level by level, making queue the perfect data structure.

dartCopy
class TreeNode {
  int value;
  TreeNode? left;
  TreeNode? right;
  TreeNode(this.value, [this.left, this.right]);
}

/// Breadth-first search traversal
List<int> bfsTraversal(TreeNode? root) {
  if (root == null) return [];

  final result = <int>[];
  final queue = Queue<TreeNode>();

  queue.enqueue(root);

  while (queue.isNotEmpty) {
    final node = queue.dequeue();
    result.add(node.value);

    // Add children to queue (left to right)
    if (node.left != null) queue.enqueue(node.left!);
    if (node.right != null) queue.enqueue(node.right!);
  }

  return result;
}

void main() {
  // Build tree:
  //       1
  //      / \
  //     2   3
  //    / \
  //   4   5

  var root = TreeNode(1,
    TreeNode(2, TreeNode(4), TreeNode(5)),
    TreeNode(3)
  );

  print(bfsTraversal(root));  // [1, 2, 3, 4, 5]
  // Level 1: 1
  // Level 2: 2, 3
  // Level 3: 4, 5
}

How BFS works with Queue:

1. Start with root in queue
2. Dequeue front node, process it
3. Enqueue its children (left then right)
4. Repeat until queue is empty

Best Practices

1. Choose Right Implementation

dartCopy
// ✅ Good - Use dynamic queue for general purpose
var queue = Queue<Task>();

// ✅ Good - Use circular for fixed-size buffer
var buffer = CircularQueue<int>(1024);

// ❌ Bad - Simple queue for large datasets
var bad = SimpleQueue<int>();  // O(n) dequeue!

2. Always Check Before Dequeue

dartCopy
// ✅ Good - safe access
if (queue.isNotEmpty) {
  var item = queue.dequeue();
}

// ✅ Better - use try methods
var item = queue.tryDequeue();
if (item != null) {
  // Use item
}

// ❌ Bad - may throw
var item = queue.dequeue();  // Crashes if empty!

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

dartCopy
// For simple FIFO without custom operations
import 'dart:collection';

var queue = Queue<int>();  // Dart's built-in Queue
queue.add(1);      // enqueue
queue.removeFirst();  // dequeue

Interview Tips

Common Interview Questions:

Q: "Implement a queue from scratch"

• Show circular queue for O(1) operations
• Explain front and rear pointer management
• Handle wrap-around with modulo operator

Q: "Queue vs Stack?"

• Queue: FIFO (first in, first out)
• Stack: LIFO (last in, first out)
• Queue for BFS, Stack for DFS
• Queue for scheduling, Stack for undo/redo

Q: "How to implement queue using two stacks?"

dartCopy
class QueueUsingStacks<T> {
  final Stack<T> _inbox = Stack();
  final Stack<T> _outbox = Stack();

  void enqueue(T item) => _inbox.push(item);

  T dequeue() {
    if (_outbox.isEmpty) {
      while (_inbox.isNotEmpty) {
        _outbox.push(_inbox.pop());
      }
    }
    return _outbox.pop();
  }
}

Follow-up Questions:

• "BFS vs DFS?" → Queue vs Stack, level vs depth exploration
• "Priority queue?" → Heap-based, not simple FIFO
• "When to use circular queue?" → Fixed-size buffers, resource pooling

Red Flags to Avoid:

• Using O(n) dequeue in production ❌
• Confusing queue with stack (LIFO) ❌
• Not handling empty queue errors ❌
• Not knowing BFS uses queue ❌

Resources

• Queue (Data Structure) - Wikipedia
• Dart Queue Class - Built-in Implementation
• Queue Visualization