Что такое линейные структуры?¶

Мы начнём наше изучение структур данных с рассмотрения четырёх простых, но очень мощных концепций. Стеки, очереди, деки и списки являются примерами коллекций данных, чьи составляющие упорядочены в зависимости от того, как они добавлялись или удалялись. Единожды добавленный, элемент остаётся на одном и том же месте по отношению к остальным, пришедшим раньше и позже него. Коллекции такого рода часто называют линейными структурами данных.

О линейных структурах можно думать, как об имеющих два конца. Иногда эти концы называют “левым” и “правым”, иногда - “головой” и “хвостом”. Вы также можете именовать их “верхним” и “нижним” - точная терминология тут непринципиальна. В чём отличие одной линейной структуры от другой, так это в способе, каким добавляются или удаляются их элементы, в частности - в месте, где происходят данные операции. Например, структура может разрешать новым элементам добавляться только в хвост. Или отдельные структуры позволяют удалять элементы с любого края.

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