Руководство для начинающих по использованию структур данных Queue и Stack в коде.
Когда вы начинаете изучать структуры данных и алгоритмы, все может очень быстро усложниться. Таким образом, эта статья предназначена для того, чтобы замедлить работу и познакомить вас с двумя распространенными структурами данных (очередями и стеками), которые часто используются в качестве основных строительных блоков в более сложных реализациях алгоритмов.
P.S.
Вы уже используете эти структуры данных в своем коде, просто не знаете об этом!
Очереди
Хорошо, а что такое очередь? Более официальное определение звучит примерно так:
"Набор элементов, который поддерживается в определенной последовательности и может быть изменен путем добавления нового элемента в конце коллекции или удаления существующего элемента в начале коллекции".
В конечном счете, очередь — это структура данных первым пришел — первым обслужен (FIFO). Вот простое изображение, которое иллюстрирует, как выглядит этот процесс:
Отлично, у вас должно быть довольно четкое представление о том, как они работают, и если у вас есть небольшой опыт программирования на JavaScript, вы, вероятно, уже догадались, какой тип данных мы собираемся использовать для создания нашей первой очереди.
Правильно, массив!
- Используя метод .push(), мы можем заполнить наш массив, добавив новые элементы из задней структуры данных (также называемой постановкой в очередь). .
- Используя метод .shift(), мы можем удалять элементы из нашего массива, удаляя элементы из передней структуры данных (это также называется удалением из очереди).
Хорошо, теперь, когда мы поняли, как создать очередь, давайте немного формализуем ситуацию и придадим нашей очереди некоторую структуру.
В этом примере мы собираемся реализовать очередь с помощью класса (в стиле ООП или объектно-ориентированного программирования) и добавить несколько полезных методов для управления и просмотра различных ее частей.
Итак, в последнем примере мы построили очередь и добавили несколько методов, чтобы немного поиграть с ней. В следующем примере мы сделаем то же самое, но в несколько более функциональном стиле программирования. При таком подходе мы никогда не будем мутировать (или изменять) существующую очередь напрямую. Вместо этого каждая функция будет создавать и возвращать новую копию очереди.
JavaScript не является настоящим функциональным языком, поэтому этот пример не является идеальным, но он должен проиллюстрировать другой способ мышления о построении структуры данных.
Вызов 1
В приведенных выше примерах я использовал массивы для создания каждой очереди, потому что они просты для понимания, просты в написании и очень распространены в JavaScript. Но вы можете реализовать очередь, используя другой тип данных, если она работает в соответствии с упомянутым выше принципом FIFO. Итак, вот ваша задача:
Создайте очередь, используя строку вместо массива.
Стеки
Теперь, когда мы понимаем, что такое очередь, разобраться со стеками будет довольно просто. В отличие от очереди (FIFO), стеки представляют собой структуры данных, которые следуют принципу последний пришел – первый ушел (LIFO). Вот изображение, иллюстрирующее, как это работает на практике:
Опять же, используя массив, мы реализуем структуру данных стека в JavaScript.
- Мы можем использовать метод .push() для добавления элементов в стек из назад, как мы это делали с очередью.
- Но в отличие от очереди, мы будем использовать метод .pop() для удаления элементов из задней части стека.
Круто, как видно из приведенного выше кода, стек почти идентичен очереди, за исключением того, как удаляются элементы.
Далее мы более подробно рассмотрим ООП-подход к построению стека с использованием класса Object.
Еще раз, на всякий случай, мы построим стек в более функциональном стиле.
Вызов 2
Опять же, я использовал массивы для построения каждого стека. Но вы можете реализовать стек, используя другой тип данных, если он работает по принципу LIFO. Итак, вот ваша задача:
Создайте стек, используя объект вместо массива.
Вывод
Вот и все для очередей и стеков. Хотя они могут показаться относительно простыми, они часто используются внутри и в сочетании с более сложными структурами данных и алгоритмами. Твердое понимание таких базовых концепций настроит вас на успех позже, когда на собеседованиях и на работе возникнут действительно сложные проблемы.
Спасибо за чтение и, как всегда, продолжайте кодить!
Взгляните на некоторые более сложные алгоритмы и посмотрите, сможете ли вы определить, где используются очереди и стеки:
Источники
