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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Пример 11.5.

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

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

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

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

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

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