Комментарии 17
Хм… Я не сильно много работаю с JS, но даже я в курсе, что обычный Array это два в одном — сразу и стэк и очередь. В зависимости от применяемых к нему функций.
И смысл первых двух обёрток — исключительно "приятственный глазу вид"?
Тут не про JS, а про знакомство со структурами данных — если вы работаете девом, но не знаете чем очередь от стека отличается, то
На западе девелоперы любят пополнять свое портфолио подобными публикациями, полезно для карьеры.
"… в JavaScript" часть из описанных структур реализована нативно, поэтому нет особого смысла городить абстракции над абстракциями. В поисках же эффективных реализаций исписаны сотни страниц и конца этому пока не видно.
Его можно использовать в качестве стэка или очереди, но это будет лишь иммитацией поведения.
Это не "… в JavaScript", а "реализация… на JavaScript для чайников".
В целом полезно, но заголовок сбивает с толку.
Хотя если учесть, что это перевод, то основная претензия к автору перевода — не браться переводить столь низкопробный источник.
Мои глаза. Stack реализован через HashMap. Это ли не безумие? О каких структурах данных тут может идти речь? Зачем эта статья?
class Stack {
top = null;
push(value) {
this.top = { prev: this.top, value };
return this;
}
pop() {
if (!this.top) {
return null;
}
const value = this.top.value;
this.top = this.top.prev;
return value;
}
}Вот ^ зарисовка Stack-а.
Посмотрел на остальные "структуры данных" поверх массива. Пожалуй статью можно переименовать в: как при помощи буханки хлеба сделать троллейбускак при помощи массива имитировать API популярных структур данных.
Come on. Какой к чёрту .indexOf в Set? Какой к чёрту .splice? Какой смысл использовать их и называть эти структуры данных очередями, Set-ами, Stack-ами, если у них от них только внешний API?
Имхо, классические структуры данных строятся, обычно, либо
- вокруг массива-как непрерывного куска памяти с известным размером элемента (что позволяет получать константный по времени доступ к элементу с известным индексом), и математике вокруг индексов, а не вокруг элементов,
- либо вокруг указателей/ссылок на элементы, что опять таки, даёт константную возможность изменения последовательностей элементов
Причём, из-за используемой нами архитектуры компьютеров с долгим случайным доступом в память — реализации со вторым подходом уже лет 20 проигрывают реализациям с первым.
Учитывая, что в js-е просто нет классического массива, а он заменён апи к ассоциативному массиву (объекту) — всё это выглядит как хрень.
Хеш таблица из статьи вообще похожа на торжество бессмысленности — «мы строим хеш-таблицу на якобы массиве, который на самом деле объект, который хеш таблица»
Учитывая, что в js-е просто нет классического массива
В какой-то мере есть. Но это уже большая специфика.
Правда, подозреваю, что кастомный стек/очередь на js массиве-буффере смысла иметь не будет, ибо на конверсиях туда-сюда проиграем встроенным.
Попробовать, что-ли.
ЕМНИП то обычные массивы тоже скорее vector-ы нежели hashMap-ы. Значения лежат последовательно и работает адресная арифметика. Но сильно не вникал, мог что-нибудь напутать. В V8 блоге были про это статьи. Там было описано, что числовые индексы и их значения хранятся отдельно, и пока в массиве нет дырок (типа var a = []; a[9999] = 4;) то они производительны. Но, честно говоря, не копал глубже самой поверхности. Они там в V8 чего только не наворотили и постоянно всё меняют туда-сюда.
В методе remove класса BST допущена небольшая ошибка. Должно быть:
...
if (data < node.data) {
node.left = removeNode(node.left, data)
return node
} else {
node.right = removeNode(node.right, data)
return node
}
...
В методе isWord допущена ошибка. Должно быть:
...
while (word.length > 1) {
if (!node.keys.has(word[0])) {
return false
}
...
8 распространенных структур данных на примере JavaScript