Есть ли практическое использование двусвязного списка, очередей и стеков?

Question

Я уже давно пишу код. И моя работа связана с решением реальных бизнес-сценариев. Однако я не сталкивался с практическим использованием некоторых структур данных, таких как связанный список, очереди и стеки и т. Д.

Даже на уровне бизнес-структуры. Конечно, есть вездесущие HashTable, ArrayList и, в последнее время, List ... но есть ли практическое использование некоторых других базовых структур данных?

Было бы замечательно, если бы кто-то дал реальное решение, в котором Двусвязный список «работает» лучше, чем очевидный и легко используемый аналог.

Answer 1

Конечно, можно обойтись только с Map (он же HashTable) и List. Queue - это только прославленный List, но если вы используете Queue везде, где вам действительно нужна очередь, тогда ваш код становится намного более читабельным, потому что никто не должен угадывать, для чего вы используете этот List.

И затем есть алгоритмы, которые работают намного лучше, когда базовая структура данных не является простой List, а DoublyLinkedList из-за того, как они должны перемещаться по списку. То же самое верно для всех других структур данных: их всегда можно использовать. :)

Answer 2

Стеки могут использоваться для сопряжения (анализа), например, сопоставления открытых скобок с закрывающими скобками.

Очереди могут использоваться для обмена сообщениями или обработки активности.

Для круговой навигации можно использовать связанный список или двойные связанные списки.

Answer 3

Связанный список полезен, если у вас есть подмножество «выбранных» элементов из большего набора элементов, где вы должны выполнить один тип операции над «выбранным» элементом и операцию по умолчанию или вообще не выполнять никаких операций над обычный элемент и набор «выбранных» элементов могут изменяться по желанию (возможно, из-за пользовательского ввода). Поскольку удаление связанного списка может быть выполнено почти мгновенно (по сравнению со временем обхода, которое потребуется для поиска в массиве), если подмножества достаточно велики, то поддерживать связанный список быстрее, чем поддерживать массив или восстанавливать все подмножество с помощью Сканирование всего большого набора каждый раз, когда вам нужно подмножество.

С помощью хэш-таблицы или двоичного дерева вы можете искать один «выбранный» элемент, но вы не можете искать все «выбранные» элементы без проверки каждого элемента (или наличия отдельного словаря для каждой перестановки выбранных элементов). что, очевидно, нецелесообразно).

Очередь может быть полезна, если вы находитесь в сценарии, когда к вам поступает много запросов, и вы хотите убедиться, что обрабатываете их справедливо, по порядку.

Я использую стеки всякий раз, когда у меня есть рекурсивный алгоритм, что обычно означает, что он работает с некоторой иерархической структурой данных, и я хочу напечатать сообщение об ошибке, если у меня заканчивается память, вместо того, чтобы просто позволить программному сбою, если программный стек работает нет больше места. Вместо рекурсивного вызова функции я храню ее локальные переменные в объекте, запускаю цикл и поддерживаю стек этих объектов.

Answer 4

Я их не очень часто использую, но они подходят. Например, я использую очередь в текущем проекте для обработки асинхронных изменений символьного оборудования, которые должны произойти в том порядке, в котором пользователь их вносит.

Answer 5

Я постоянно использую очереди, связанные списки и т. Д. В бизнес-решениях.

За исключением случаев, когда они реализованы Oracle, IBM, JMS и т. Д.

Эти конструкции обычно находятся на гораздо более низком уровне абстракции, чем вы хотели бы при реализации бизнес-решения. Откуда бизнес-проблема выиграет от такие низкоуровневые конструкции (например, планирование маршрута доставки, планирование производственной линии и т. д.) обычно есть пакет, доступный для этого или для вас.

Answer 6

LIFO-Stack и FIFO-Queue являются достаточно абстрактными (поведенческими спецификациями) структурами данных, поэтому , конечно, , есть много практических применений для них. Например, LIFO-Stack - отличный способ помочь удалить рекурсию (составлять текущее состояние и цикл вместо рекурсивного вызова); FIFO-Queue помогает «буферизовать» и «отслаивать» рабочие слепки в расположении сопрограмм; и т. д. и т. д.

Doubly-related-List - это скорее проблема реализации, чем поведенческая спецификация уровня, в основном ... может быть хорошим способом реализации FIFO-очереди, например. Если вам нужна последовательность с быстрым объединением и удалением, указывающая на одну последовательность iten, вы также найдете множество других реальных применений.

Answer 7

Большинство этих алгоритмов обычно находятся на более низком уровне, чем ваше обычное «деловое» приложение. Например, индексы в базе данных являются разновидностью многосвязного списка. Реализация механизма вызова функций (или дерева разбора) представляет собой стек. Очереди и FIFO используются для обслуживания сетевых запросов и т. Д.

Это всего лишь примеры структур сбора, оптимизированных для скорости в различных сценариях.