Структуры данных
Массив (Array)
Массив — это упорядоченная коллекция данных, которая встречается чаще всего. На массивах основаны многие другие структуры данных: списки, стеки, очереди. Каждый элемент массива имеет индекс (положительное числовое значение) — «адрес», который соответствует позиции элемента и по которому этот элемент можно извлечь.
В большинстве языков программирования индекс начинается с нуля.
Массивы бывают двух видов:
-
Одномерные (One-dimensional arrays) У каждого элемента только один индекс. Можно представить это как строку с данными, где одного номера достаточно, чтобы чётко определить положение каждой переменной.
-
Многомерные (Multi-dimensional arrays) У каждого элемента два или больше индексов. По сути, это комбинация из нескольких одномерных массивов, то есть вложенная структура.
В зависимости от реализации в разных языках программирования массивы могут иметь статический и динамический размер (Dynamic array).
В JavaScript массив — это особый подвид объектов, оптимизированный для работы с «упорядоченной коллекцией данных». Если мы начнём использовать его как обычный объект, например, создав свойство с индексом, намного превышающим длину массива или создав свойство с произвольным именем, то движок JavaScript начнём использовать его как обычный объект.
Как применяют массивы:
- В качестве блоков для более сложных структур данных. Массивы предусмотрены в синтаксисе большинства языков программирования, и на их основе удобно строить другие структуры.
- Для хранения несложных данных небольших объёмов.
- Для сортировки данных.
Очередь (Queue)
Очередь — это линейная упорядоченная структура данных, которая позволяет добавлять данные в конец, а извлекают из начала. Она работает по принципу FIFO — First In, First Out (англ. «первым пришёл — первым ушёл»).
Пример реализации на JavaScript
class Queue {
storage = [];
// Добавить элемент в конец очереди
enqueue(value) {
this.storage.push(value);
}
// Получить и удалить первый элемент из очереди
dequeue() {
return this.storage.shift();
}
// Получить размер очереди
size() {
return this.storage.length;
}
}
// Использование:
const queue = new Queue();
queue.enqueue('яблоко');
queue.enqueue('банан');
console.log(queue.size()); // 2
console.log(queue.dequeue()); // 'яблоко'
console.log(queue.size()); // 1
Как применяют очереди:
- Для реализации очередей, например на доступ к определённому ресурсу.
- Для управления потоками в многопоточных средах.
- Для генерации значений.
- Для создания буферов.
Стек (Stack)
Стек — это линейная упорядоченная структура данных, которая позволяет добавлять или удалять элементы только из конца. Она работает по принципу LIFO — Last In, First Out (англ. «последним пришёл — первым ушёл»)
Пример реализации на JavaScript
- Встроенная в язык структура данных
- Самописная реализации
const stack = [];
// Добавляем в конец два элемента
stack.push('яблоко');
stack.push('банан');
// Выводим размер стека
console.log(stack.length); // 2
// Получить элемент из конца стека
console.log(stack[stack.length - 1]); // 'банан'
// Удалить элемент из конца стека
stack.pop();
console.log(stack.length); // 1
// Получить элемент из конца стека
console.log(stack[stack.length - 1]); // 'яблоко'
class Stack {
storage = {};
length = 0;
// Добавить элемент в конец стека
push(value) {
this.storage[this.length] = value;
this.length++;
}
// Удалить элемент из конца стека
pop() {
if (this.length === 0) {
return undefined;
}
this.length--;
delete this.storage[this.length];
}
// Получить размер стека
size() {
return this.length;
}
// Получить элемент из конца стека
peek() {
return this.storage[this.length - 1];
}
}
// Использование:
const stack = new Stack();
stack.push('яблоко');
stack.push('банан');
console.log(stack.size()); // 2
console.log(stack.peek()); // 'банан'
stack.pop();
console.log(stack.size()); // 1
console.log(stack.peek()); // 'яблоко'
Как применяют стеки:
- Для реализации рекурсии.
- Для вычислений постфиксных значений.
- Для временного хранения данных, например истории запросов или изменений.
Связный список (Linked list)
Связный список — это линейная структура данных из узлов, где каждый узел содержит данные и указатель на последующий узел в цепочке. При этом сами элементы более разрозненны, чем в массиве, поскольку хранятся отдельно. Быстро перемещаться между элементами списка помогают указатели.
Как применяют связные списки:
- Для построения более сложных структур данных.
- Для реализации файловых систем.
- Для формирования хэш-таблиц.
- Для выделения памяти в динамических структурах данных.