Введение в структуры данных и абстрактные типы данных
Что такое структуры данных?
В информатике структуры данных - это особые форматы, используемые при организации, управлении и обработке данных. Есть много структур данных, которые сильно различаются по сложности. По сути, структура данных существует для хранения информации и создания пути для ее эффективного извлечения и использования. Некоторые структуры данных, которые вы, возможно, видели раньше, - это массивы, хеш-таблицы, связанные списки, деревья и графики.
Что такое стек?
Стеки - это структуры, соответствующие принципу Last-In-First-Out (LIFO). Представления реального мира повсюду, при мытье посуды или складывании полотенец все, что можно сложить, будет разложено, начиная с объекта, который был помещен наверх последним. Первый элемент в стеке будет последним элементом, использованным в стеке. Массивы, а также асинхронные запросы в JavaScript используют этот порядок операций при выполнении.
Что такое очередь?
Очередь можно представить как инверсию стека. Очереди соответствуют принципу «первым пришел - первым обслужен» (FIFO). Также хорошо представлен в реальной жизни: каждый раз, когда вы стоите в очереди за службой, вы ожидаете двигаться в одном направлении к началу очереди. Массивы можно использовать для реализации очередей в JavaScript.
Как я могу использовать стеки и очереди в JavaScript?
При использовании массива в качестве стека JavaScript предоставляет методы push () и pop (). Чтобы продемонстрировать варианты использования:
// устанавливаем стек переменных в массив чисел
пусть stack = [0, 1, 2, 3, 4, 5];
// чтобы удалить элемент из вершины стека, мы будем использовать метод pop ()
stack.pop () // число 5 будет удалено из вершины стека
console.log (стек) // [0, 1, 2, 3, 4];
// чтобы добавить элемент в верх стека, мы будем использовать метод push ()
stack.push (9) // число 9 будет добавлено в верх стека
console.log (стек) // [0, 1, 2, 3, 4, 9]
У нас есть аналогичные варианты использования массива в качестве очереди в JavaScript с помощью методов push () и shift ().
// устанавливаем переменную очередь в массив чисел
пусть queue = [0, 1, 2, 3, 4, 5];
// чтобы удалить элемент из передней очереди, мы будем использовать метод shift ()
queue.shift () // число 0 будет удалено из передней очереди
console.log (очередь) // [1, 2, 3, 4, 5];
// чтобы добавить элемент в конец очереди, мы будем использовать метод push ()
queue.push (6) // число 6 будет добавлено в конец очереди
console.log (стек) // [1, 2, 3, 4, 5, 6]
Почему?
Предыдущие примеры могут показаться мрачными, скучными или унылыми, но по мере того, как данные становятся более сложными, их будет чрезвычайно важно знать и понимать, чтобы эффективно перемещать данные. При использовании стеков и очередей наш компьютер перебирает каждый элемент в массиве, повторно индексируя эти элементы, что приводит к большей временной сложности. Связанные списки обычно являются лучшим выбором при работе с большими объемами данных. Они обеспечивают более простой доступ для прямого перемещения элементов без необходимости повторно индексировать массив.
Связанные списки: обзор
Разработчик JavaScript на любом уровне может оценить полезность массива. Однако по мере того, как приложения становятся более сложными, вставка и удаление элементов, в частности, становится все более эффективным с использованием связного списка. Анатомия связного списка - это либо узел, который указывает на другой узел в одном направлении, либо узел, который указывает непосредственно позади и прямо перед собой. Эта цепочка эффективна для перемещения вперед и назад без необходимости переиндексировать коллективные данные. Стеки и очереди - это шаблоны, которые можно увидеть и использовать как в массивах, так и в связанных списках.
Я всегда рада подключиться, вы можете найти меня в Twitter, LinkedIn или в моем портфолио!
