Темы:
1. What are Data Structures? 2. Data Structure in JavaScript 3. Array 4. Stack 5. Queue 6. Linked List 7. Hash Table 8. Trees 9. Graphs 10. Sample Example
Что такое структуры данных?
Структуры данных - это методы хранения и организации данных, упрощающие изменение, навигацию и доступ. Структуры данных используются практически во всех областях информатики и программирования, от операционных систем до базового ванильного кода и искусственного интеллекта.
Структуры данных позволяют нам:
- Управляйте большими наборами данных и используйте их
- Поиск определенных данных из базы данных
- Разработка алгоритмов, адаптированных к конкретным программам.
- Одновременная обработка нескольких запросов от пользователей
- Упростите и ускорьте обработку данных
Структура данных в JavaScript
В JavaScript есть примитивные и непримитивные структуры данных. Примитивные структуры данных и типы данных встроены в язык программирования. К ним относятся логическое, null, число, строка и т. Д. Непримитивные структуры данных определяются не языком программирования, а программистом. К ним относятся линейные структуры данных, статические структуры данных и динамические структуры данных, такие как очереди и связанные списки.
Массив
Это основная структура данных. Может быть, каждый программист или разработчик JavaScript использовал его. Массив - это фундаментальный строительный блок для сложных структур данных. Мы можем хранить данные в массиве и вызывать их по номеру индекса. мы также можем вставлять и удалять элемент. Некоторые методы в массиве:
1. push() 2. pop() 3. unshift() 4. shift() 5. splice() 6. concat() 7. slice() etc.
Стек
Стек - это абстрактный тип данных, который служит набором элементов с двумя основными операциями:
- push, который добавляет элемент в коллекцию, и
- pop, который удаляет последний добавленный элемент, который еще не был удален.
Стек работает в стиле LIFO (Last In Fast Out). Последний элемент, который мы поместили в стек, будет удален первым. Хорошим примером является кнопка «Назад» в веб-браузерах: каждая просматриваемая страница добавляется в стек, и когда мы нажимаем кнопку «Назад», текущая страница (последняя добавленная) выталкивается из стека.
Мы можем увидеть этот пример:
Легко понять из комментариев, не так ли?
Очередь
Очередь очень похожа на стек. Ключевое различие между стеком и очередью состоит в том, что очередь соответствует стилю FIFO (первый пришел - первый ушел).
Посмотрите на изображение выше, мы можем видеть стороны внутрь и наружу. В очереди, если мы вставим значение, оно продвинется вперед. Например, здесь мы вставляем «A» как очень быстрый элемент, а затем «B». Теперь, если мы хотим удалить элемент, нам нужно сначала удалить элемент «A», а затем «B».
Может быть, вам пришла в голову идея очереди.
Вы также можете увидеть этот пример, чтобы узнать, как работает очередь:
Это тоже просто.
Связанный список
Связанный список в основном используется для языков, не имеющих массивов динамического изменения размеров. Связанные списки упорядочивают элементы последовательно, каждый элемент указывает на следующий элемент.
Каждый узел в связанном списке имеет значение data и значение next. Ниже 5 - это значение данных, а значение next указывает на следующий узел, то есть узел, имеющий значение 10.
Визуально это выглядит так:
Хеш-таблица
Хеш-таблица (хеш-карта) - это структура данных, которая реализует абстрактный тип данных ассоциативный массив, структуру, которая может сопоставлять ключи со значениями. В хэш-таблице используется хеш-функция для вычисления индекса в массиве сегментов или слотов, из которого можно найти желаемое значение.
В идеале хеш-функция будет назначать каждый ключ уникальному сегменту, но в большинстве конструкций хеш-таблиц используется несовершенная хеш-функция, которая может вызвать коллизии хеш-функции, когда хеш-функция генерирует один и тот же индекс для более чем одного ключа. Такие столкновения необходимо каким-то образом улаживать.
Деревья
Деревья - это еще одна основанная на отношениях структура данных, которая специализируется на представлении иерархических структур. Подобно связному списку, узлы содержат как элементы данных, так и указатели, обозначающие его отношение к непосредственным узлам.
Каждое дерево имеет «корневой» узел, от которого ветвятся все остальные узлы. Корень содержит ссылки на все элементы, расположенные непосредственно под ним, которые известны как его «дочерние узлы». Это продолжается, когда каждый дочерний узел разветвляется на большее количество дочерних узлов.
Узлы со связанными дочерними узлами называются внутренними узлами, а узлы без дочерних узлов - внешними. Распространенным типом дерева является «двоичное дерево поиска», которое используется для простого поиска хранимых данных. Эти операции поиска очень эффективны, поскольку продолжительность поиска зависит не от количества узлов, а от количества уровней вниз по дереву.
Много видов деревьев:
- Дерево двоичного поиска
- AVL Tree
- Красно-Черное дерево
- Дерево сегментов - с примерами запросов min / max / sum range
- Дерево Фенвика (двоичное индексированное дерево)
Графики
Граф - это абстрактный тип данных, который предназначен для реализации неориентированного графа и концепций ориентированного графа из математики, в частности из области теории графов.
Структура данных графа состоит из конечного (и, возможно, изменяемого) набора вершин, узлов или точек вместе с набором неупорядоченных пар этих вершин для неориентированного графа или набора упорядоченных пар для ориентированного графа. Эти пары известны как ребра, дуги или линии для неориентированного графа и как стрелки, направленные ребра, направленные дуги или направленные линии для ориентированного графа. Вершины могут быть частью структуры графа или могут быть внешними объектами, представленными целочисленными индексами или ссылками.
Пример:
Образец примера
Семь элементов A, B, C, D, E, F и G помещаются в стек в обратном
порядке, т. Е. Начиная с G. Стек выталкивается пять раз, и каждый элемент
вставляется в очередь. Два элемента удаляются из очереди и возвращаются в стек. Теперь из стека извлекается один элемент. Так какова ценность всплывающего предмета?
Сначала подумайте об этом и попробуйте сами.
Если вы найдете ответ, это будет здорово. Но если не можете, не волнуйтесь. Посмотрите на ниже:
На рис: -1 элементы вставляются в стек, затем на рис: -2 верхние 5 элементов выталкиваются, и эти 5 элементов вставляются в очередь, которая показана в fig: -3, теперь первые два элемента удаляются из очереди и помещаются в стек один за другим, как показано на fig: -5.
В верхней части представлен элемент стека B.
Итак, «B» - правильный ответ.
Это все на сегодня. Если вы получили представление о структуре данных из этой статьи, нажмите «хлопать». Это вдохновит меня написать для вас больше статей. Спасибо.
Увидимся позже в моей следующей статье.
