Що робить стек при обході без рекурсії?

АлгоритмиJunior~2 хв читання

Коротка відповідь

Стек при обході без рекурсії заміняє системний стек викликів: зберігає кадри стану (вузол і контекст його обробки), забезпечує LIFO-повернення до «точок повернення», дозволяє емулювати pre/in/post-обробку вузлів і керувати бектрекінгом. Це робить можливим обхід у глибину без використання рекурсії та з точним контролем порядку відвідування.

Детально

Що робить стек при нерекурсивному обході

Емулює стек викликів: кожен push - «вхід» у підзадачу, pop - «повернення».
Зберігає точки повернення і контекст: де ми були, що вже обробили, що залишилось (фаза обробки, індекс нащадка, ітератор тощо).
Забезпечує LIFO-порядок для бектрекінгу: остання гілка йде глибше першої - це і є обхід у глибину (DFS).
Дозволяє реалізувати різні порядки обходу (preorder/inorder/postorder) за рахунок керування моментом обробки і порядком додавання сусідів/дітей.
Дає явний контроль пам'яті і порядку обходу, уникаючи обмеження глибини системного стека.

Як це працює покроково

Покласти початковий вузол (або кадр стану) у стек.
Поки стек не порожній: дістати вершину (pop).
Обробити вузол у потрібній фазі (до/між/після дітей) - залежить від варіанта обходу.
Покласти в стек сусідів/дітей у такому порядку, щоб наступний pop дав потрібний порядок відвідування (зазвичай додаємо в зворотному порядку відображення).

Що саме кладемо в стек

Посилання на вузол (вершину дерева/графа).
Фазу/стан обробки: enter/pre, mid/in, exit/post (часто як булевий прапорець visited/expanded).
Індекс поточної дитини або ітератор сусідів (якщо потрібно обробляти по одному).
Довільний контекст: посилання на батька, накопичений шлях/глибину, проміжні обчислення.

Чому стек, а не черга

Стек (LIFO) дає обхід у глибину і природний бектрекінг - аналог рекурсії. Черга (FIFO) потрібна для обходу в ширину (BFS), де важливо спочатку пройти всі вершини поточного рівня.

Порядки обходу і роль стека

Preorder (node-left-right): обробляємо вузол одразу після pop; потім кладемо правого, потім лівого нащадка.
Inorder (left-node-right): стек зберігає шлях до крайнього лівого; після pop обробляємо вузол і йдемо в праве піддерево.
Postorder (left-right-node): використовуємо прапорець/фазу або два стеки; вузол обробляється лише після дітей.

Приклади коду (JavaScript)

1) DFS по дереву: preorder (node-left-right)

function preorderIter(root) {
  if (!root) return [];
  const res = [];
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    res.push(node.val);            // pre-обробка
    if (node.right) stack.push(node.right); // кладемо правого першим
    if (node.left) stack.push(node.left);   // щоб лівий дістався раніше
  }
  return res;
}

// Приклад структури вузла:
// { val: number, left: Node|null, right: Node|null }

2) DFS по дереву: inorder (left-node-right)

function inorderIter(root) {
  const res = [];
  const stack = [];
  let curr = root;
  while (curr || stack.length) {
    while (curr) {           // йдемо по лівих гілках, запам'ятовуючи шлях
      stack.push(curr);
      curr = curr.left;
    }
    curr = stack.pop();      // ліве піддерево вичерпано - обробляємо вузол
    res.push(curr.val);
    curr = curr.right;       // потім йдемо в праве піддерево
  }
  return res;
}

3) DFS по дереву: postorder (left-right-node) через прапорець стану

function postorderIter(root) {
  const res = [];
  if (!root) return res;
  const stack = [{ node: root, visited: false }];
  while (stack.length) {
    const { node, visited } = stack.pop();
    if (!node) continue;
    if (visited) {
      res.push(node.val); // post-обробка
    } else {
      // Кладемо маркер для повторного заходу після дітей
      stack.push({ node, visited: true });
      if (node.right) stack.push({ node: node.right, visited: false });
      if (node.left) stack.push({ node: node.left, visited: false });
    }
  }
  return res;
}

4) DFS по графу (ітеративно зі стеком)

function dfsGraph(adj, start) {
  // adj: Map<Vertex, Vertex[]> або об'єкт { v: [u1, u2, ...] }
  const visited = new Set();
  const stack = [start];
  const order = [];
  while (stack.length) {
    const v = stack.pop();
    if (visited.has(v)) continue; // важливо уникати циклів
    visited.add(v);
    order.push(v);
    const neighbors = (adj.get ? adj.get(v) : adj[v]) || [];
    for (let i = neighbors.length - 1; i >= 0; i--) {
      const u = neighbors[i];
      if (!visited.has(u)) stack.push(u);
    }
  }
  return order;
}

Шаблон «явного стека кадрів»

function dfsIterGeneric(start) {
  // Кадр зберігає вузол і фазу: 'enter' (до дітей) або 'exit' (після дітей)
  const stack = [{ node: start, state: 'enter' }];
  while (stack.length) {
    const frame = stack.pop();
    const { node, state } = frame;
    if (!node) continue;
    if (state === 'enter') {
      // 1) pre-обробка
      // ...
      // 2) Плануємо post-обробку
      stack.push({ node, state: 'exit' });
      // 3) Кладемо дітей у зворотному порядку, щоб перша логічна дитина пішла першою
      const children = node.children || [];
      for (let i = children.length - 1; i >= 0; i--) {
        stack.push({ node: children[i], state: 'enter' });
      }
    } else {
      // post-обробка
      // ...
    }
  }
}

Часті помилки

Відсутність множини visited у графі - зациклення.
Неправильний порядок push - ламається бажаний порядок обходу.
Ігнорування фаз/прапорця visited при postorder - вузол обробляється занадто рано.
Дублювання вузлів у стеку без потреби - зростання пам'яті і зайві операції.

Зв'язок з рекурсією

Рекурсія автоматично створює кадри на системному стеку: локальні змінні, позиція повернення, фаза. При нерекурсивному підході ви явним чином створюєте такі кадри і керуєте ними вручну через свій стек, отримуючи той самий ефект, але з контролем порядку і обмежень за глибиною.

Коротка відповідь

Для співбесіди

Premium

Коротка відповідь допоможе вам впевнено відповідати на цю тему під час співбесіди.