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

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

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

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

Что такое стек

Стек — линейная структура данных, которая работает по принципу LIFO (последний пришёл — первый ушёл). Представьте стопку тарелок: можно класть и брать только с вершины.

Реализовать стек в JavaScript очень просто, используя массив или ES6-класс. Ниже — минимальная структура класса Stack (свойство data хранит элементы, top — индекс вершины):

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

Ниже разобраны основные операции стека.

Push

Операция push вставляет новое значение в вершину стека. Сначала увеличивается указатель top, затем значение записывается по этому индексу.

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

Пояснение: сложность O(1) амортизированно при использовании массива.

Pop

Операция pop удаляет верхний элемент и снижает top.

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

Если стек пуст — возвращаем undefined.

Peek

Peek возвращает значение на вершине без удаления (O(1)).

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

Что такое связный список

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

Для реализации в JavaScript обычно используют два класса: Node и LinkedList. Node описывает узел, LinkedList — операции и указатели head/tail.

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

Append добавляет новый узел в конец списка. Если список пуст — и head, и tail указывают на новый узел.

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

Insert добавляет узел по указанному индексу. В худшем случае требуется O(N) времени из‑за прохода по списку.

insert(data, index) {  
 if (index < 0 || index > this.size) return undefined;  
 if (index === 0) {  
 this.head = new Node(data, this.head);  
 !this.tail ? (this.tail = this.head) : null;  
 this.size++;  
 return this;  
 }  
 if (index === this.size) return this.append(data);  
  
 let count = 0;  
 let beforeNode = this.head;  
 while (count !== index) {  
 beforeNode = beforeNode.next;  
 count++;  
 }  
  
 const newNode = new Node(data);  
 let afterNode = beforeNode.next;  
  
 newNode.next = afterNode;  
 beforeNode.next = newNode;  
 this.size++;  
 return this;  
}

Пояснение: будьте внимательны с граничными случаями (вставка в начало и в конец).

Delete

Удаление узла требует поиска предыдущего узла и перенастройки ссылок. В худшем случае — O(N).

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

Совет: при удалении проверяйте пустой список и корректность индекса.

Что такое очередь

Очередь — линейная структура данных по принципу FIFO (первый пришёл — первый ушёл), как очередь людей. Для эффективной реализации используют связный список с указателями front и rear.

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

Enqueue

Enqueue добавляет элемент в конец очереди. Если очередь пуста — front и rear указывают на новый узел.

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

Dequeue удаляет первый элемент; при удалении единственного элемента требуется обнулить rear.

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;  
}

Шпаргалка: временная сложность (эмпирическая)

Важно помнить типичные сложности операций для этих структур:

Стек (на основе массива): push/pop/peek — O(1)
Очередь (на основе связного списка): enqueue/dequeue — O(1)
Связный список: доступ по индексу — O(N), вставка/удаление в середине — O(N) (если требуется поиск), вставка в начало/конец при наличии head/tail — O(1)

Эти оценки помогают быстро выбирать структуру под задачу.

Важно: конкретная производительность зависит от реализации и размера данных. Массивы в JS оптимизированы, но частые вставки в начало массива — дорогостоящи.

Как выбрать структуру: мини‑методология

Определите тип доступа: случайный доступ по индексу или последовательный проход?
Частота вставок/удалений в середине списка vs в конце/начале.
Требуется ли упорядочение, быстрая сортировка или поиск по ключу?
Оцените память: связный список требует дополнительной памяти под указатели.
Прототипируйте и измерьте — реальные профили важнее теории.

Пример решения: если нужно FIFO — используйте очередь; для LIFO — стек; если нужны частые вставки/удаления в середине без переаллокации — выбирайте связный список.

Когда эти структуры не подходят

Большие данные с частыми произвольными обращениями: лучше массивы или TypedArray.
Частые поиски по ключу: используйте Map или объект (O(1) средне для доступа по ключу).
Когда нужен упорядоченный набор с уникальными элементами — Set или сбалансированные деревья (внешние библиотеки).

Контрпример: реализовать очередь на массиве, постоянно вызывая shift() — для больших объёмов это приведёт к повторным сдвигам элементов и падению производительности.

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

Массивы: просты и быстры для итерации и индексного доступа.
Map/Set: быстрый доступ по ключу и уникальность элементов.
Дек (двунаправленная очередь): для операций с обоих концов.
Внешние библиотеки (immutable.js, lodash) для специализированных структур.

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

Критерии приёмки для реализаций (минимум):

Покрытие операций: push/pop/peek для стека; append/insert/delete для списка; enqueue/dequeue для очереди.
Корректное поведение на границах: пустая структура, одна запись, граничные индексы.
Сохранение порядка элементов (LIFO для стека, FIFO для очереди).
Управление памятью: отсутствие утечек ссылок (например, nullify.next при удалении узла).

Пример тест-кейсов:

Попытка pop() у пустого стека — должна вернуть undefined.
Вставка в начало и конец связного списка — проверка head/tail.
Удаление последнего элемента очереди — rear должен стать null.

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

Разработчик:

Проверить граничные условия и ошибки.
Написать тесты на производительность для реальных объёмов данных.

Интервьюируемый:

Уметь объяснить выбор структуры и её сложность.
Быстро реализовать базовый вариант и отметить возможные улучшения.

Учитель/ментор:

Демонстрировать ментальные модели (стек — стопка, очередь — очередь людей).
Показывать контрпримеры и оптимизации.

Сравнение в таблице (кратко)

Память: связный список > массивы (из‑за указателей).
Вставка в середину: связный список быстрее при известной позиции узла.
Индексный доступ: массивы значительно быстрее.

1‑строчный глоссарий

LIFO: last in, first out — последний пришёл, первый ушёл.
FIFO: first in, first out — первый пришёл, первый ушёл.
Node: элемент связного списка с указателем next.

Финальные рекомендации

Начните с простых реализаций, затем профилируйте.
Для большинства приложений JavaScript массивы и Map/Set покрывают потребности; собственные структуры полезны для обучения, специфичных задач и интервью.

Короткое резюме:

Стек, связный список и очередь — фундаментальные структуры. Знайте их операции и особенности сложности. Прототипируйте и проверяйте на реальных данных.

Спасибо за чтение. Если хотите, могу добавить готовые тесты (Jest) для каждой структуры или нарисовать flowchart для выбора структуры.

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