Какая структура данных описывается как lifo

Стек и очередь

Стек (англ, stack — стопка) — структура данных с методом доступа к элементам LIFO (англ. Last In — First Out, «последним пришел — первым вышел»). Чаще всего принцип работы стека сравнивают со стопкой тарелок: чтобы взять вторую сверху, нужно сначала снять самую верхнюю.

Добавление элемента возможно только в вершину стека (добавленный элемент становится первым сверху). Удаление элемента возможно также только из вершины стека, при этом второй сверху элемент становится верхним.

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

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

Стек и очередь могут быть организованы как на основе массива, так и на основе связного списка.

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

Иерархическая структура данных

Иерархическая модель структуры данных — логическая организация данных в виде древовидной структуры.

Иерархическая модель представляет собой совокупность элементов, расположенных в порядке их подчинения от более высокого по статусу (вышестоящего) элемента к подчиненному ему (нижестоящему) элементу.

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

Каждая конечная древовидная структура содержит элемент, не имеющий вышестоящего. Этот элемент называется корнем или корневым узлом. Линии, связывающие элементы, называются ребрами, а сами элементы называются узлами.

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

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

Каждый узел имеет не больше одного предка (родителя). У корневого узла нет предков. Все прочие узлы дерева могут быть достигнуты путем перехода от корневого узла по ребрам дерева. Каждый такой путь в дереве единственен.

Узлы самого нижнего уровня дерева называются листовыми узлами или листьями. Так как они находятся на самом нижнем уровне, то не имеют никаких потомков.

Высота узла — это максимальная длина нисходящего пути от этого узла к самому нижнему узлу (листу). Высота корневого узла равна высоте всего дерева. Глубина вложенности узла равна длине пути от корня до этого узла.

Добавление новых данных не нарушает иерархической структуры дерева. Недостатком иерархических структур являются относительная трудоемкость записи адреса элемента данных и сложность процедуры упорядочивания и поиска.

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

На рис. 11.1 изображена часть дерева, отображающего организационную структуру университета.

Иерархическую структуру имеет система почтовых адресов, а также система адресов компьютерных файлов.

Вопросы и задания для самоконтроля

• 1. Что такое информация? Перечислите ее виды и свойства.
• 2. Какие основные разделы информатики можно выделить?
• 3. Как определяется количество полученной информации?
• 4. Что такое бит информации и что такое байт?
• 5. Перечислите основные виды информационных процессов и дайте им краткую характеристику.
• 6. Как с помощью двух символов, 0 и 1 кодируются целые и действительные числа?

Рис. 11.1. Организационная структура университета

• 7. Как с помощью 0 и 1 кодируются символьные данные? Какие кодировки вы знаете?
• 8. Как осуществляется цифровая обработка сигналов?
• 9. Опишите основные структуры данных, отметив их сравнительные достоинства и недостатки.

Структура данных

Структура данных в программировании — это объект-контейнер, в котором хранится информация. Данные внутри контейнера структурированы по особой системе — она различается в зависимости от вида структуры. Так разработчики оптимизируют доступ к информации.

Освойте профессию «Data Scientist»

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

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

Профессия / 24 месяца
Data Scientist

Дата-сайентисты решают поистине амбициозные задачи. Научитесь создавать искусственный интеллект, обучать нейронные сети, менять мир и при этом хорошо зарабатывать. Программа рассчитана на новичков и плавно введет вас в Data Science.

Для чего нужны структуры данных

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

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

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

Характеристики структуры данных

Описание структуры данных можно условно поделить на интерфейс и реализацию. Интерфейс — это набор операций, который описывает поведение конкретной структуры. То есть это то, что можно сделать с конкретной структурой данных. А реализация — то, как данные структурированы внутри.

Кроме того, типичная структура данных отвечает нескольким критериям:

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

«Минимум места» и «минимум времени» могут различаться для разных структур. Это нормально: у каждой из них свое назначение и оптимальный способ использования.

Какими бывают структуры данных

Структуры данных в общем можно разделить на линейные и нелинейные. Разница в том, как они хранят свои элементы — данные, которые в них расположены.

• В линейных структурах элементы расположены как бы «по цепочке», друг за другом. Они выстраиваются в последовательность. Например, слово можно представить как линейную структуру данных, где данные — буквы.
• В нелинейных элементы могут ветвиться, образовывать таблицы или схемы. Пример нелинейной структуры данных из жизни — схема дорог.

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

Массивы

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

Индексы идут последовательно. Это целые числа, последовательность которых начинается с 0.

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

Классические массивы — статические, то есть у них конечная и неизменная длина. Если такой массив создать с длиной 5 — там всегда будет место ровно для 5 элементов, не больше и не меньше. Еще бывают динамические массивы: их длина изменяется в зависимости от того, сколько значений в них «положили».

Как правило, в массиве могут лежать данные только одного типа. Например, массив чисел или массив строк.

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

Применение. Массивы применяют в большинстве ситуаций, где требуется организованное хранение данных. Не используют их только в сложных структурах: там логичнее будет применить другой формат. Но и тут массивы нужны как строительные «кирпичики» для реализации более комплексных структур.

Станьте дата-сайентистом и решайте амбициозные задачи с помощью нейросетей

Очереди

Очередь похожа на массив. Это тоже линейная структура, состоящая из последовательности элементов. Разница в том, что доступ к этим элементам возможен только по принципу FIFO: First In, First Out. Это значит, что из очереди можно быстро и легко извлечь элемент, который расположен в самом ее начале и находится в ней дольше всего. А вот операций для доступа с конца или из середины может вообще не быть. Добавляются же элементы, наоборот, только в конец — как с реальной очередью в магазине.

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

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

Стеки

Стек — структура, обратная очереди. Это последовательность, в которой доступ работает по принципу LIFO: Last In, First Out. Элементы добавляются в конец, а быстро получить и извлечь их можно опять же с конца. То есть чем позже элемент добавили в стек, тем легче до него добраться.

Английское слово stack означает «стопка», например, стопка бумаг. Так можно представить и стек: как стопку бумаг, где самый верхний элемент берется первым.

Операции. Среди операций специально для стеков — так называемый push, то есть добавление элемента в конец, и pop — извлечение элемента из конца. Извлечение означает, что элемент удаляется из стека, но возвращается как значение.

Также есть проверка пустоты стека и операция, возвращающая последний элемент без его удаления.

Применение. Стек используется при выделении памяти программам и процессам. Функции, работающие внутри программы, как бы «укладываются» в системный стек. Популярное выражение stack overflow — это распространенная ошибка, возникающая, когда стек переполняется из-за неправильного использования памяти. Чаще всего такое бывает при рекурсии.

Еще один вариант применения стека — история просмотров: доступ к данным, которые человек просмотрел последними, проще.

Деки

Деками называют двусторонние очереди: они объединяют возможности и очереди, и стека. Такие структуры данных могут работать и по принципу FIFO, и по принципу LIFO. Доступ к элементам возможен с любого конца.

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

Применение. Деки используют, когда важно обеспечить доступ и к первым, и к последним элементам. Например, при оптимизации выполнения процессов.

Связанные списки

Еще один распространенный пример линейной структуры данных. Это последовательность элементов, каждый из которых хранит данные и ссылку на следующий или предыдущий элемент. В результате от одного элемента можно быстро получить доступ к его «соседу».

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

У односвязных списков есть ссылки только на следующий элемент, у двусвязных — и на следующий, и на предыдущий. Их еще называют однонаправленными или двунаправленными. Есть и круговые списки — они закольцовываются, и последний их элемент указывает на первый.

Первый элемент называется головой списка, последний — хвостом.

Операции. В список можно добавить элемент — в голову, хвост или заданный участок. Также можно обновить значение элемента или удалить его, провести поиск по структуре данных. Также есть операция-проверка, пуст ли список. Доступ к следующему элементу возможен с помощью указателя next, к предыдущему — prev.

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

Множества

Множество — еще одна линейная структура данных. Ее особенность в том, что элементы не имеют четкого порядка, зато уникальны по значению. Ее можно представить не как последовательность или список, а как «облако тегов»: неупорядоченный набор уникальных значений. Это определение близко к математическому понятию множества. И работают с ним так же: не сортируют и не структурируют, но хранят, получают и анализируют данные.

Множество еще называют сетом. По-английски название звучит как Set.

Операции. Характерные для этой структуры данных операции рассчитаны на работу с двумя множествами. Например, это операции объединения множества, сравнения, поиска пересечений между двумя сетами. Похоже на круги Эйлера, но программно реализованные.

Также есть операция, которая возвращает только элементы множества, не пересекающиеся с другим, и операция поиска подмножества. Она показывает, содержится ли одно множество в другом.

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

Карты

По-английски эта структура данных называется Map. Ее еще называют ассоциативным массивом или словарем. Она действительно похожа на массив, но вместо упорядоченных числовых индексов в ней используются «ключи» — заданные пользователем числа или строки. Весь массив — это набор пар из ключей и значений.

Можно представить эту структуру данных как телефонный справочник. Ключ — это имя, по которому человек ищет нужный номер. А само значение — собственно, номер телефона.

Разработчик сам задает ключи или генерирует их автоматически. Часто ключи строковые: это облегчает понимание и поиск информации.

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

Операции. С картами можно работать как с массивами, но доступ к ним осуществляется по названию ключа, а не индексу. Можно добавить пару ключ-значение, удалить ее или изменить значение. Также можно обратиться к элементу по его ключу.

У ассоциативных массивов иначе реализован проход по всей структуре, чем у обычных: тут не получится просто увеличивать индекс на 1 на каждом шаге, ведь ключ может быть каким угодно. Поэтому в языках программирования обычно предусмотрены специальные операции для прохода по словарю.

Применение. Ассоциативные массивы используют для хранения данных, которые нужно быстро найти по какому-то неизменному ключу. Еще они применяются для передачи данных — ключ выступает как название параметра, а в самом элементе хранится его значение. Например, когда человек заполняет форму на сайте и отправляет ее, на сервер приходят данные в виде словаря вроде такого:

Ключи name, phone и isAgree описывают, что именно передают: имя, телефон и наличие согласия на получение сообщений. А Ivan, true и номер — уже значения, которые приняли эти параметры.

Хэш-таблицы

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

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

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

Операции. В таблицу можно добавить элемент, удалить или найти по тому или иному признаку. При ее создании также можно и нужно задать формулу, по которой будут генерироваться хэши.

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

Графы

Граф — нелинейная структура организации данных, которая состоит из «вершин» и «ребер» между ними. Каждая вершина — это значение, а ребра — пути, которые соединяют между собой вершины. Получается своеобразная «сетка», похожая на карту дорог или созвездие.

Графы бывают неориентированными, когда ребра не имеют конкретного направления, и ориентированными. Во втором случае по ребрам можно пройти только в одну сторону — как по дороге с односторонним движением. Есть смешанные графы, в которых есть и ориентированные, и неориентированные ребра.

Также существуют взвешенные графы, у ребер которых есть «вес» — то или иное значение. Например, в карте дорог весом ребра-дороги можно назвать его длину.

Графы обычно реализуют с помощью связанных списков или матриц — двумерных массивов.

Операции. С этими структурами есть базовые операции: добавление вершины или ребра, отображение вершины или графа целиком, оценка «стоимости» обхода взвешенного графа и так далее.

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

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

Деревья

Деревья можно назвать частным случаем графов. Это тоже структуры из вершин и ребер, но имеющие древовидный формат. Вершины деревьев называются узлами. От одного узла может отходить несколько вершин-потомков, но предок у каждого узла может быть только один. Так и получается древовидная иерархическая структура.

В программировании применяют несколько видов деревьев. Большинство из них реализуют с помощью графов.

• Бинарные деревья поиска — самый распространенный формат деревьев. У каждого узла может быть не более двух потомков. Если значение узла-потомка меньше предка, он располагается слева. Если равно или больше — справа. С помощью таких деревьев удобно сортировать данные и искать в них нужное значение с помощью бинарного поиска.
• Префиксные деревья, они же нагруженные деревья или боры — это деревья, которые хранят данные «по цепочке». Узлы-предки — префиксы, которые нужны, чтобы перейти к потомкам. При прохождении дерева «собираются» полные данные. Например, в каждом узле — буква. При прохождении от начала до конца получаются слова. Обычно такие деревья используют для хранения повторяющихся данных или, например, для реализации автодополнения при вводе.
• Двоичные кучи — двоичные деревья, заполненные целиком. У каждого узла два потомка. Потомки в зависимости от типа дерева должны быть строго больше предков или меньше либо равны им.

Также существуют N-арные деревья, красно-черные деревья, AVL-деревья, сбалансированные, 2-3-4-деревья и так далее.

Операции. По деревьям можно проходить снизу вверх или сверху вниз, в ширину или в глубину. Для этого существуют специальные алгоритмы — как и для графов. Так как обычно в деревьях расположение узла зависит от его значения, произвольно добавить узел куда угодно не получится. Поэтому при добавлении, удалении или изменении узла происходит перебалансировка — изменение структуры с учетом добавленного значения.

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

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

Узнать больше о программировании и хранении данных вы можете на наших курсах. Записывайтесь — сделайте первый шаг к новой популярной профессии.

Data Scientist

Дата-сайентисты решают поистине амбициозные задачи. Научитесь создавать искусственный интеллект, обучать нейронные сети, менять мир и при этом хорошо зарабатывать. Программа рассчитана на новичков и плавно введет вас в Data Science.

LIFO и FIFO

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

FIFO (First In, First Out, «первый пришел – первый ушел») – поведение как в очереди в магазине. Ему соответствует структура данных очередь. У такого хранилища две операции: enqueue – добавить элемент в конец, и dequeue – забрать из начала.

LIFO (Last In, First Out, «последний пришел – первый ушел» – наоборот, первый пришедший ждет всех остальных, подобно стопке тарелок. Соответственно, его реализует структура данных стек. Операция push кладет новый элемент наверх стопки, pop забирает сверху же.

Термины применяются не только к способу доступа к данным, но и к порядку разрешения конфликтов. Так, например, по принципу LIFO или FIFO может определяться порядок исполнения параллельно пришедших сигналов какой-либо системы: доступа к диску, планировки задач ОС, и прочих.

Очереди типов FIFO и LIFO

Мы продолжаем изучение структур данных. На этом занятии познакомимся с еще одним способом организации данных – очередями.

Само слово очередь (по англ. queue) сразу ассоциируется с очередью в магазин за каким-нибудь долгожданным или дефицитным продуктом:

Здесь тот, кто первым пришел (First In), тот первым и покидает очередь (First Out). Именно поэтому такой тип очереди получил сокращенное название FIFO. То есть, в такой структуре данные добавляются в конец очереди, а извлекаются из начала.

Где может быть полезна такая организация данных? Распространенный пример – буфер приема или передачи какого-либо устройства:

Здесь вновь поступающие данные добавляются в конец очереди, а извлекаются (читаются) из начала очереди.

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

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

Но это первый тип очереди, который, как мы уже знаем, носит название FIFO. Есть еще один тип очереди под названием:

LIFO (Last In, First Out)

Что это за очередь? Представьте себе ящик, в который складываются разные вещи:

А вынимать их можно только сверху. В результате, последняя положенная вещь будет извлечена первой, вторая – второй и так до последней. Получаем очередь типа LFIO: последний зашел, первый вышел.

Классический пример использования этого типа очереди – организация стеков вызова функций в программах. Пусть имеется вот такая простая программа на языке Python, в которой последовательно вызываются три функции: сначала main, затем show_sum и последней print:

def show_sum(a, b): print(a+b) def main(): show_sum ()

Чтобы интерпретатор «знал» в какой последовательности функции были вызваны и в какой последовательности продолжать их выполнять, после завершения очередной, формируется очередь по принципу LIFO: последняя вызванная функция должна первой и завершаться, затем, вторая и, наконец, третья.

Реализация очередей на основе связных списков

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

Итак, для реализации очередей нужно выбрать структуру, которая бы обладала высокой скоростью обработки крайних элементов последовательности, то есть, O(1). И мы с такими структурами уже знакомы – это односвязные и двусвязные списки:

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

deque (сокращение от double ended queue)

То есть, очереди часто представляют собой обычные двусвязные списки. В результате, чтобы организовать очередь типа FIFO нам достаточно добавлять новые элементы в начало списка, а извлекать с конца. Это делается с помощью уже знакомых нам методов push_front() и pop_back(). А для очереди типа LIFO можно использовать методы push_front() и pop_front(). Кстати, можно заметить, что тот же эффект достигается, если мы будем конец списка считать началом, а начало – концом. Тогда очередь FIFO будет строиться методами push_back() и pop_front(), а очередь LIFO методами push_back() и pop_back(). Принципиальной разницы в их функционировании при этом не будет.

Сразу отмечу, что очереди типа deque реализуются не только на основе обычных двухсвязных списков, но и на гибридной структуре двухсвязных списков и динамических массивов:

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

Очередь, как абстрактная структура данных

Вообще, очереди можно реализовывать не только на базе связных списков, но, например, и динамического массива. Тогда для типа FIFO нам придется при добавлении нового элемента в начало сдвигать все остальные элементы массива, что вычислительно несколько дольше – O(n) операций (вместо O(1) для связных списков). Да и операции добавления новых элементов в конец динамического массива требуют большего числа операций, чем у связных списков. Поэтому динамический массив для очередей, в общем случае, не лучший выбор. Хотя, в некоторых частных задачах, возможно, это будет иметь смысл.

Я привел пример с динамическим массивом, чтобы вы ясно себе представляли, что очередь – это не какая то конкретная структура данных, как связные списки или массивы, а несколько абстрактная. Она лишь определяет порядок взаимодействия с элементами упорядоченной коллекции. А именно, добавление и удаление граничных элементов. С промежуточными элементами тоже возможно взаимодействие, но производительность этих операций, как правило, значительно ниже и составляет O(n), где n – число элементов в очереди.

На следующих занятиях мы увидим, как реализуются очереди на языках программирования С++ и Python.

Видео по теме

#1. О большое (Big O) — верхняя оценка сложности алгоритмов