Структуры данных в JavaScript: стек, список, очередь

Картонная коробка на светлом фоне

Структуры данных — базовая часть информатики и программирования. Они помогают организовать, хранить и изменять данные эффективно. Выбор подходящей структуры может значительно улучшить производительность приложения.

В JavaScript по умолчанию есть примитивные структуры: массивы и объекты. Но с появлением ES6-классов можно создавать собственные структуры, такие как стеки и очереди, поверх этих примитивов.

Определения в одну строку

Стек (LIFO): последний вошёл — первый вышел.
Очередь (FIFO): первый вошёл — первый вышел.
Узел: структура с данными и ссылкой на следующий элемент.

Стек

Стек позволяет добавлять элементы сверху и убирать только с вершины. Ментальная модель: стопка тарелок — только верхнюю можно положить или снять.

Простейшая реализация на массиве и ES6-классе:

class Stack {
  constructor() {
    this.data = [];
    this.top = -1;
  }

  push(data) {
    this.top++;
    this.data[this.top] = data;
    return this.data;
  }

  pop() {
    if (this.top < 0) return undefined;
    const poppedTop = this.data[this.top];
    this.top--;
    return poppedTop;
  }

  peek() {
    return this.top >= 0 ? this.data[this.top] : undefined;
  }

  size() {
    return this.top + 1;
  }
}

Краткие заметки:

push/pop — O(1) по времени.
Используйте стек для обхода графов в глубину, отмены действий, проверок парности скобок.

Когда стек не подойдёт

Когда нужен быстрый доступ к середине коллекции.
Когда требуется извлечение по приоритету — предпочитайте очередь с приоритетом.

Связанный список

Связанный список — последовательность узлов, где каждый узел содержит данные и ссылку на следующий узел. Это полезно, когда нужно эффективно вставлять или удалять элементы в середине коллекции без сдвига целого массива.

Минимальная реализация узла и списка:

class Node {
  constructor(data, next = null) {
    this.data = data;
    this.next = next;
  }
}

class LinkedList {
  constructor() {
    this.head = null;
    this.tail = null;
    this.size = 0;
  }

  append(data) {
    const newNode = new Node(data);
    if (!this.head) {
      this.head = newNode;
      this.tail = newNode;
    } else {
      this.tail.next = newNode;
      this.tail = newNode;
    }
    this.size++;
    return this;
  }

  insert(data, index) {
    if (index < 0 || index > this.size) return undefined;
    if (index === 0) {
      this.head = new Node(data, this.head);
      if (!this.tail) this.tail = this.head;
      this.size++;
      return this;
    }
    if (index === this.size) return this.append(data);

    let count = 0;
    let beforeNode = this.head;
    while (count !== index - 1) {
      beforeNode = beforeNode.next;
      count++;
    }
    const newNode = new Node(data);
    const afterNode = beforeNode.next;
    newNode.next = afterNode;
    beforeNode.next = newNode;
    this.size++;
    return this;
  }

  deleteNode(index) {
    if (index < 0 || index > this.size - 1) return undefined;
    if (index === 0) {
      const removedHead = this.head;
      this.head = this.head.next;
      this.size--;
      if (this.size === 0) this.tail = null;
      return removedHead;
    }
    if (index === this.size - 1) {
      if (!this.head) return undefined;
      let currentNode = this.head;
      let newTail = currentNode;
      while (currentNode.next) {
        newTail = currentNode;
        currentNode = currentNode.next;
      }
      this.tail = newTail;
      this.tail.next = null;
      this.size--;
      if (this.size === 0) [this.head, this.tail] = [null, null];
      return currentNode;
    }
    let count = 0;
    let beforeNode = this.head;
    while (count !== index - 1) {
      beforeNode = beforeNode.next;
      count++;
    }
    const removedNode = beforeNode.next;
    const afterNode = removedNode.next;
    beforeNode.next = afterNode;
    removedNode.next = null;
    this.size--;
    return removedNode;
  }
}

Ключевые замечания:

Вставка и удаление в середине — O(N) в худшем случае из‑за необходимости пройти список до нужной позиции.
Если нужен быстрый доступ по индексу, массив будет эффективнее.

Очередь

Очередь моделирует людей в очереди: кто пришёл первым — обслужен первым. Часто используется при планировании задач и обработке сообщений.

Реализация на связном списке:

class Queue {
  constructor() {
    this.front = null;
    this.rear = null;
    this.size = 0;
  }

  enqueue(data) {
    const newNode = new Node(data);
    if (!this.front) {
      this.front = newNode;
      this.rear = newNode;
    } else {
      this.rear.next = newNode;
      this.rear = newNode;
    }
    this.size++;
    return this;
  }

  dequeue() {
    if (!this.front) return undefined;
    if (this.front === this.rear) this.rear = null;
    const dequeuedNode = this.front;
    this.front = this.front.next;
    this.size--;
    return dequeuedNode;
  }
}

Примечания:

enqueue и dequeue — O(1) при реализации через голову и хвост связного списка.
Если требуется индексный доступ — используйте массив, но с учётом стоимости сдвигов элементов.

Сравнение и выбор структуры

Факты и сложности:

Операция	Массив	Связанный список
Доступ по индексу	O(1)	O(N)
Вставка/удаление в середине	O(N)	O(N) (поиск)
Вставка/удаление в начале	O(N)	O(1)
Добавление в конец	O(1) аморт.	O(1) (с хвостом)

Когда выбирать:

Массив: когда важен быстрый доступ по индексу или требуется сортировка.
Связанный список: когда часто вставляете/удаляете элементы в начале или в середине и нет надобности в индексном доступе.
Стек/очередь: для LIFO/FIFO сценариев (undo, обходы, очереди задач).

Альтернативные подходы

Реализовать стек на базе объекта с числовыми ключами — полезно, если хотите контролировать память или поведение индексов.
Использовать встроенные методы массива push/pop/shift/unshift для быстрой разработки, но помните о стоимости shift/unshift (O(N)).
Для сложных требований по приоритетам — очередь с приоритетом (heap).

Методология изучения

Освойте понятия LIFO/FIFO и узел.
Реализуйте простые версии на массиве и через Node.
Напишите тесты для каждой операции.
Сравните поведение на больших объёмах данных.

Тесты и критерии приёмки

Для стека: push несколько элементов, peek возвращает последний, pop удаляет и возвращает их в обратном порядке.
Для списка: append N элементов, проверить порядок; вставить в середину и убедиться в корректной связке ссылок.
Для очереди: enqueue несколько элементов, dequeue возвращает в том же порядке.

Пример простого теста для стека:

const s = new Stack();
s.push(1);
s.push(2);
console.assert(s.peek() === 2, 'peek должен вернуть 2');
console.assert(s.pop() === 2, 'pop должен вернуть 2');
console.assert(s.pop() === 1, 'pop должен вернуть 1');
console.assert(s.pop() === undefined, 'пустой стек возвращает undefined');

Чеклист по ролям

Для разработчика: реализовать операции, написать тесты, замерить сложность.
Для интервьюера: попросить реализации и объяснить выбранную сложность.
Для студента: начать с массива, затем переходить к узлам и тестам.

Полезные эвристики

Если нужны быстрые вставки/удаления и не нужен индекс — думайте о списках.
Для простых случаев используйте массивы: меньше кода и ошибок.
Всегда учитывайте амортизированную сложность и поведение GC в среде выполнения.

Короткий глоссарий

LIFO: последний зашёл — первый вышел.
FIFO: первый зашёл — первый вышел.
Узел: элемент списка с ссылкой на следующий элемент.

Заключение

Структуры данных — это инструменты. Знание их особенностей помогает писать более эффективный код. Начните с реализаций, напишите тесты и сравните поведение на практике. Следующим шагом будут алгоритмы: сортировки, поиска и структуры данных с дополнительными свойствами (деревья, кучи, графы).

Важно: практикуйтесь на реальных задачах. Только так вы поймёте, когда использовать массив, а когда — связанный список, стек или очередь.