Структуры и алгоритмы обработки данных, часть 2

5. Охарактеризуйте линейные структуры данных

Линейные структуры данных – это структуры данных, в которых переход от одного элемента данных к другому не зависит от каких-либо логических условий, т.е. в линейных структурах используются лишь безусловные связи элементов.

 К линейным структурам относятся стеки, очереди и деки.

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

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

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

6. Охарактеризуйте нелинейные структуры данных

Линейные - алгоритм в пошаговом исполнении от начала до конца.

Нелинейные - алгоритм с переходами по условию.