Стек и очередь

Стек (stack) — структура данных LIFO (последний вошёл — первый вышел); очередь (queue) — структура FIFO (первый вошёл — первый вышел); обе поддерживают вставку и удаление за O(1).

Зачем нужно

Стек и очередь — фундаментальные ADT (abstract data types), которые встречаются повсюду: стек вызовов, undo/redo, история браузера — стек; обработка задач, BFS, планировщик — очередь. Понимание их позволяет корректно реализовывать рекурсию, обходы графов и управление потоками задач.

Где используется

  • Стек: обход DFS, стек вызовов, undo/redo, парсинг выражений, история браузера
  • Очередь: BFS, планировщик задач ОС, буферизация данных, асинхронные очереди

Основной контент

Стек (Stack) — LIFO

push → [4] [3] [2] [1] ← pop/peek
       top           bottom

class Stack {
  #items = ;

  push(item)  { this.#items.push(item); }     // O(1)
  pop       { return this.#items.pop(); }    // O(1)
  peek      { return this.#items.at(-1); }   // O(1)
  isEmpty   { return this.#items.length === 0; }
  get size  { return this.#items.length; }
}

// Применение: проверка сбалансированности скобок
function isBalanced(str) {
  const stack = new Stack();
  const pairs = { ')': '(', ']': '[', '}': '{' };
  for (const ch of str) {
    if ('([{'.includes(ch)) stack.push(ch);
    else if (')]}'.includes(ch)) {
      if (stack.isEmpty || stack.pop() !== pairs[ch]) return false;
    }
  }
  return stack.isEmpty;
}
console.log(isBalanced("({})")); // true
console.log(isBalanced("({[})"));  // false

Очередь (Queue) — FIFO

enqueue → [4][3][2][1] → dequeue
          back         front

class Queue {
  #items = ;
  #head = 0; // избегаем O(n) shift

  enqueue(item) { this.#items.push(item); }          // O(1)
  dequeue     {                                     // O(1) амортизированно
    if (this.isEmpty) return undefined;
    return this.#items[this.#head++];
  }
  peek        { return this.#items[this.#head]; }  // O(1)
  isEmpty     { return this.#head >= this.#items.length; }
  get size    { return this.#items.length - this.#head; }
}

// BFS с очередью
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = new Queue();
  queue.enqueue(start);
  const order = ;

  while (!queue.isEmpty) {
    const node = queue.dequeue;
    order.push(node);
    for (const neighbor of graph[node] || ) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.enqueue(neighbor);
      }
    }
  }
  return order;
}

Deque (Double-Ended Queue)

Деке позволяет добавлять/удалять с обоих концов за O(1). В JS — через массив с push/pop/unshift/shift (но unshift/shift O(n)) или через двусвязный список.

Стек и очередь через массив JavaScript

// Стек: нативный массив
const stack = ;
stack.push(1);   // push — O(1)
stack.pop();     // pop — O(1)
stack.at(-1);    // peek — O(1)

// Очередь: осторожно! shift — O(n)
const queue = ;
queue.push(1);   // enqueue — O(1)
queue.shift();   // dequeue — O(n)! сдвигает весь массив

// Для высокопроизводительных очередей используй двусвязный список
// или класс Queue с указателем head (пример выше)

Частые ошибки

  • Использовать Array.shift() для очереди — O(n) вместо O(1); при n > 10^4 заметное замедление.
  • Не проверять isEmpty перед pop/dequeue — возвращает undefined вместо ошибки.
  • Путать LIFO и FIFO: стек — вертикальная стопка (последний сверху), очередь — горизонтальная линия (первый выходит с начала).
  • Реализовывать DFS с очередью или BFS со стеком — результат будет неверным.

Связанные темы

Ресурсы