Data Structure in Dart – Stacks & Queues

1. Why Stacks & Queues Matter

After arrays and linked lists, Stacks and Queues are the first data structures that introduce restricted access:

• You cannot access elements randomly.
• You must follow strict rules.

These rules make them extremely powerful for:

• Undo / Redo
• Function calls & recursion
• Task scheduling
• Breadth-first & depth-first traversal
• UI navigation in apps

---

2. Stack – Last In, First Out (LIFO)

Concept

A Stack works exactly like a stack of plates:

• Add plate → top
• Remove plate → top

Operations:

• push() → add element
• pop() → remove top element
• peek() → view top element
• isEmpty()

Top
[ 30 ]
[ 20 ]
[ 10 ]
Bottom

---

3. Stack Implementation in Dart

Stack using List (Array-based)

Dart’s List is perfect for stack behavior.

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

  void push(T value) {
    _items.add(value);
  }

  T pop() {
    if (_items.isEmpty) {
      throw Exception("Stack is empty");
    }
    return _items.removeLast();
  }

  T peek() {
    if (_items.isEmpty) {
      throw Exception("Stack is empty");
    }
    return _items.last;
  }

  bool get isEmpty => _items.isEmpty;
}

Usage

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

  stack.push(10);
  stack.push(20);
  stack.push(30);

  print(stack.pop());  // 30
  print(stack.peek()); // 20
}

---

4. Real-World Stack Use Cases

1. Undo / Redo (Flutter Example)

Every text editor uses stacks:

• Undo stack → previous states
• Redo stack → undone states

class UndoRedoManager {
  final Stack<String> undoStack = Stack();
  final Stack<String> redoStack = Stack();

  void execute(String state) {
    undoStack.push(state);
    redoStack._items.clear();
  }

  String undo() {
    String state = undoStack.pop();
    redoStack.push(state);
    return state;
  }
}

---

2. Function Calls (Call Stack)

Each function call:

• Stores local variables
• Stores return address
• Pops after return

This is why deep recursion can cause stack overflow.

---

5. Classic Stack Problems

Balanced Parentheses

bool isBalanced(String input) {
  final stack = Stack<String>();

  for (var char in input.split('')) {
    if (char == '(') {
      stack.push(char);
    } else if (char == ')') {
      if (stack.isEmpty) return false;
      stack.pop();
    }
  }
  return stack.isEmpty;
}

void main() {
  print(isBalanced("(())")); // true
  print(isBalanced("(()"));  // false
}

---

Reverse a String Using Stack

String reverse(String input) {
  final stack = Stack<String>();
  for (var char in input.split('')) {
    stack.push(char);
  }

  String result = '';
  while (!stack.isEmpty) {
    result += stack.pop();
  }
  return result;
}

---

6. Queue – First In, First Out (FIFO)

Concept

A Queue works like a line at Starbucks:

• First person arrives → first served

Operations:

• enqueue() → add element to rear
• dequeue() → remove element from front
• peek()

Front → [ A ][ B ][ C ] ← Rear

---

7. Queue Implementation in Dart

Simple Queue using List

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

  void enqueue(T value) {
    _items.add(value);
  }

  T dequeue() {
    if (_items.isEmpty) {
      throw Exception("Queue is empty");
    }
    return _items.removeAt(0);
  }

  T peek() {
    if (_items.isEmpty) {
      throw Exception("Queue is empty");
    }
    return _items.first;
  }

  bool get isEmpty => _items.isEmpty;
}

removeAt(0) is O(n) → not ideal for large queues.

---

8. Optimized Queue (Circular Queue Concept)

import 'dart:collection';

void main() {
  Queue<int> queue = Queue();

  queue.addLast(10);
  queue.addLast(20);
  queue.addLast(30);

  print(queue.removeFirst()); // 10
}

dart:collection.Queue is optimized and recommended for production apps.

---

9. Real-World Queue Use Cases

1. Task Scheduling

• Print jobs
• Network requests
• Background workers

2. Flutter UI Event Queue

• User taps
• Scroll events
• Gesture processing

---

10. Queue in Graph Algorithms (Preview)

Queues are essential for Breadth-First Search (BFS):

• Used in shortest path
• Used in level-order traversal of trees

void bfs(List<List<int>> graph, int start) {
  final visited = List<bool>.filled(graph.length, false);
  final queue = Queue<int>();

  queue.add(start);
  visited[start] = true;

  while (queue.isNotEmpty) {
    int node = queue.removeFirst();
    print(node);

    for (var neighbor in graph[node]) {
      if (!visited[neighbor]) {
        visited[neighbor] = true;
        queue.add(neighbor);
      }
    }
  }
}

---

11. Stack vs Queue Comparison

Feature	Stack	Queue
Order	LIFO	FIFO
Insert	push	enqueue
Remove	pop	dequeue
Use Cases	Undo, recursion	Scheduling, BFS
Access	Top only	Front only

---

12. Summary

• Stack → LIFO → undo/redo, recursion, parsing
• Queue → FIFO → scheduling, buffering, BFS
• Dart List can implement both
• Prefer dart:collection.Queue for performance
• Both are foundational for advanced algorithms