"Информатика (углублённый уровень)", Калинин И.А., Самылкина Н.Н.
Структуры данных помогают хранить сведения так, чтобы нужные операции — поиск, добавление, удаление или обработка — выполнялись удобно и эффективно. Массивы дают быстрый доступ к элементу по индексу, а в связном списке элементы соединены ссылками. Стек и очередь задают особый порядок извлечения: последний добавленный элемент или первый. Выбор зависит не от названия задачи, а от того, какие действия над данными нужны чаще всего.
Текст подготовлен нейронной сетью по теме параграфа и не заменяет учебник — важные факты и формулировки сверяйте с ним.
Структура данных — способ организации и хранения данных, определяющий доступные операции и порядок работы с элементами. Иначе говоря, она задаёт, как сведения расположены и каким способом к ним обращаться. Это понятие помогает заранее выбрать удобный способ для поиска, добавления, удаления и обработки данных.
Линейная структура данных — структура, в которой элементы расположены последовательно и для каждого, кроме крайних, есть предшественник и следующий элемент. Можно представить её как цепочку, где у каждого внутреннего звена есть сосед слева и справа. Такое описание помогает понять порядок элементов и способы перехода от одного к другому.
Стек — линейная структура, в которой добавление и удаление элементов происходят с одного конца по принципу «последним пришёл — первым вышел». Этот конец называют вершиной стека: работа идёт только с самым верхним элементом. Правило удобно, когда сначала нужно обработать то, что было добавлено последним.
Очередь — линейная структура, в которой элементы добавляются в конец, а извлекаются из начала по принципу «первым пришёл — первым вышел». Новые элементы становятся в хвост, а обработка начинается с головы. Такая организация сохраняет порядок поступления и подходит для обслуживания заявок или задач.
Структуру данных выбирают с учётом операций, которые предстоит выполнять, и частоты каждой операции. Например, если программа постоянно обращается к элементу по его номеру, важен быстрый доступ по индексу. Если чаще нужно добавлять и убирать элементы с одного края, может оказаться удобнее структура с таким правилом. Поэтому выбор влияет на скорость и простоту программы, а не только на то, как данные выглядят.
Массив хранит элементы одного типа в последовательных ячейках памяти. Поскольку положение ячейки связано с её индексом, программа может перейти непосредственно к элементу с заданным номером, не просматривая все предыдущие. Это удобно для перебора и обращения к произвольным позициям. Но если вставить элемент в середину, чтобы сохранить порядок, расположенные после него элементы часто приходится сдвигать.
В массиве ячейки идут одна за другой, а в связном списке соседние элементы связываются ссылками — указаниями на следующие элементы. Список можно представить как цепочку: каждый элемент хранит значение и связь с продолжением. Чтобы найти элемент по его месту, обычно начинают с первого и переходят по ссылкам, поэтому мгновенного доступа по индексу нет. Зато при изменении списка достаточно перестроить связи в нужном участке, не сдвигая весь хвост.
Стек и очередь по-разному ограничивают, откуда можно извлекать элементы. В стеке и добавление, и удаление происходят у вершины: последний добавленный элемент оказывается первым доступным для удаления. В очереди новые элементы добавляют в конец, но извлекают из начала, поэтому порядок поступления сохраняется. Эти правила нужны для разных сценариев обработки и определяют, какой элемент будет обработан следующим.
Одну и ту же задачу иногда можно решить с помощью разных структур данных, но решение будет различаться по удобству и эффективности. Например, массив подходит, если важен частый доступ к элементам по номерам, а связный список может быть удобен при изменении связей между элементами. Для последовательно ожидающих обработки объектов естественно использовать очередь, а для возврата к последнему добавленному — стек. Сравнение нужных операций с возможностями структуры помогает сделать обоснованный выбор.
| Свойство | Массив | Связный список | Стек | Очередь |
|---|---|---|---|---|
| Как организованы элементы | В последовательных ячейках | Соединены ссылками | Последовательность с доступом через вершину | Последовательность с началом и концом |
| Как получают нужный элемент | По индексу | Проходят по ссылкам от начала | Получают верхний элемент | Получают элемент в начале |
| Как добавляют элементы | В свободную ячейку или с возможным сдвигом элементов | Создают элемент и настраивают ссылки | В вершину | В конец |
| Как удаляют элементы | Удаляют ячейку логически, иногда сдвигая следующие элементы | Меняют ссылки, чтобы исключить элемент | С вершины | Из начала |
| Принцип извлечения | Зависит от выбранного индекса | Зависит от реализации и выбранного элемента | Последним пришёл — первым вышел | Первым пришёл — первым вышел |
Сравнивайте не только устройство, но и операции, которые нужны вашей программе. Например, для произвольного доступа по номеру сильная сторона массива — индекс, а для обработки по очереди важен порядок извлечения. Таблица помогает заметить, что стек и очередь задают специальные правила работы с элементами, тогда как массив и список описывают способы их организации.
Задача 1. Дан массив чисел. Найдите сумму его элементов. Нужно учесть каждый элемент ровно один раз, поэтому удобно пройти массив последовательно. Для накопления результата заведём переменную суммы и будем прибавлять к ней очередное значение. После завершения перебора в переменной окажется сумма всех элементов.
Ответ: сумма равна результату последовательного сложения всех элементов массива. Например, для массива 2, 5, 3 действия будут такими: 0 + 2 = 2, затем 2 + 5 = 7 и 7 + 3 = 10. Перебор гарантирует, что ни один элемент не будет пропущен.
Задача 2. Проверьте, правильно ли расставлены скобки в строке выражения. При встрече закрывающей скобки нужно сопоставить её с последней незакрытой открывающей. Именно такой порядок обеспечивает стек: он хранит открывающие скобки, которые ещё ждут пару. Если стек пуст при закрывающей скобке или типы скобок не совпали, расстановка неверна.
Ответ: скобки расставлены правильно, если ни одна проверка не выявила несоответствия и в конце стек пуст. Например, в строке «(а + [б])» закрывающая квадратная скобка сопоставится с последней открывающей квадратной, а круглая — с круглой. Оставшаяся в конце открывающая скобка означала бы, что для неё не нашлось пары.
Задача 3. Смоделируйте обслуживание заявок: новые заявки поступают в очередь, а обработчик выполняет их по порядку. Поскольку обработка должна сохранять порядок поступления, новым заявкам нельзя обгонять уже ожидающие. Очередь как раз добавляет элементы в конец и выдаёт их из начала. Поэтому программа может отдельно принимать новые заявки и обрабатывать самую раннюю из оставшихся.
Ответ: заявки выполняются в порядке поступления: первой будет обработана та, которая раньше остальных попала в очередь. Если заявки A, B и C поступили именно в таком порядке, обработчик извлечёт сначала A, затем B, затем C. Новые поступления при этом занимают место в конце и не меняют порядок уже ожидающих.
Путать стек и очередь. Ошибка возникает, когда обе структуры считают просто списком элементов и не следят за концами, с которыми выполняются операции. В стеке первым извлекают последний добавленный элемент, а в очереди — первый. Проверьте себя на короткой последовательности: добавьте A, затем B и спросите, что извлечётся первым.
Считать, что вставка в любое место массива не требует дополнительных действий. Так думают, потому что представляют массив как набор ячеек, в которые можно просто записать значение. Но для сохранения порядка при вставке в середину часто приходится сдвинуть последующие элементы, а при удалении — заполнить образовавшийся промежуток. Проверка простая: проследите, куда должны переместиться элементы справа от изменяемой позиции.
Считать связный список набором элементов с мгновенным доступом по индексу. Такое представление переносят с массива, где индекс напрямую указывает на ячейку. В списке нужно идти от начала по ссылкам, пока не будет найден нужный элемент. Чтобы проверить себя, попробуйте описать путь к пятому элементу: придётся пройти через предыдущие звенья.
Выбирать структуру данных только по названию задачи. Название может подсказать решение, но не сообщает, какие операции будут частыми и какие ограничения важны. Например, задачи со списком объектов могут требовать либо доступа по индексу, либо обработки строго в порядке поступления. Перед выбором перечислите нужные действия и оцените, какое из них будет выполняться чаще всего.
Для изучения структур данных полезно знать переменные, типы данных, массивы и циклы: переменные хранят значения и состояние программы, а циклы помогают последовательно обрабатывать элементы. Эти знания позволяют описать хранение и выполнение операций над набором данных. Структуры данных применяются при разработке алгоритмов поиска и сортировки, обработке текстов и моделировании очередей. Так, стек помогает следить за вложенностью скобок в тексте, а очередь — задавать порядок обработки ожидающих задач.
Чем структура данных отличается от типа данных?
Тип данных задаёт, какие значения можно хранить и какие действия над ними допустимы, например целые числа можно складывать. Структура данных описывает, как организовать несколько значений и как получать, добавлять или удалять их.
Почему для стека и очереди используют разные правила извлечения?
Эти правила подходят для разных способов обработки элементов. В стеке нужен доступ к последнему добавленному элементу, а очередь сохраняет порядок поступления: первым обрабатывается тот, кто пришёл первым.
В чём главное отличие массива от связного списка?
В массиве элементы расположены в последовательных ячейках, поэтому к ним можно обратиться по индексу. В связном списке каждый элемент связан ссылкой со следующим, и для поиска элемента обычно проходят по цепочке от начала.
Можно ли реализовать стек с помощью массива?
Да. Массив можно использовать для хранения элементов стека, а отдельную переменную — для указания вершины, то есть места последнего добавленного элемента. При добавлении и удалении меняют вершину, соблюдая правило «последним пришёл — первым вышел».
Как выбрать подходящую структуру данных для задачи?
Сначала определите, какие операции понадобятся и какие из них будут выполняться чаще всего. Затем сравните, насколько удобно и быстро эти операции поддерживает каждая структура, и учтите ограничения по памяти и порядку обработки.
§ 18. Структуры данных
