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

i) Получение доступа к А;-му узлу списка для проверки и/или изменения содержимого его полей.

ii) Вставка нового узла сразу после или до к-го узла.

iii) Удаление А;-го узла.

iv) Объединение в одном списке двух (или более) линейных списков.

v) Разбиение линейного списка на два (или более) списка.

vi) Создание копии линейного списка.

vii) Определение количества узлов в списке.

viii) Сортировка узлов в порядке возрастания значений в определенных полях этих узлов.

ix) Поиск узла с заданным значением в некотором поле.

В операциях (i)-(iii) очень важны особые случаи, когда к = 1 и к = п, поскольку доступ к первому и последнему элементам линейного списка можно организовать гораздо проще, чем к любому другому элементу списка. Операции (viii) и (ix) в данной главе рассматриваться не будут, так как они обсуждаются в главах 5 и 6 соответственно.

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

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

Стек - это линейный список, в котором все операции вставки и удаления (и, как правило, операции доступа к данным) выполняются только на одном из концов списка.

Очередь или односторонняя очередь - это линейный список, в котором все операции вставки выполняются на одном из концов списка, а все операции удаления (и, как правило, операции доступа к данным) - на другом.

Дек или двусторонняя очередь (double-ended queue) это линейный список, в котором все операции вставки и удаления (и, как правило, операции доступа к данным) выполняются на обоих концах списка.

Дек, следовательно, является более общим вариантом стека или очереди. Он обладает некоторыми общими свойствами с рассмотренной выше колодой карт, к тому же на английском языке эти термины созвучны. Кроме того, следует различать деки с ограниченным выводом (output-restricted deque) и с ограниченным вводом (input

restricted deque), в KOTopix операции удаления и вставки элементов соответственно выполняются только на одном из концов.

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

Механизм работы стека можно представить проще, если воспользоваться аналогией с железнодорожным разъездом, которая предложена Э. В. Дейкстрой (рис. 1). Соответствующая схе.ма для дека показана на рис. 2.

Вывод из стека

Ввод в стек

1е::::::::111№яклц:::::::н11!1

; Стек

Рис. 1. Схема стека в виде железнодорожного разъезда.

В деке с ограниченным вводом этот путь закрыт

Вывод Щ, Дек

siiiiiififiriSnKiificKKKjiriniiiiiiiiiiE::::::::

Из дека

Ввод

В дек

В деке с ограниченным выводом этот путь закрыт Рис. 2. Схема дека в виде железнодорожного разъезда.

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

Многие исследователи независимо пришли к выводу о важности стеков и очередей, а потому присвоили им иные собственные имена. Так, стеки часто называют магазинными списками (push-down Usts), реверсивными хранилищами (reversion storages), магазинами (cellars), вложенными хранилищами (nesting stores), кучами (piles), дисциплинами обслуживания в обратном порядке (last-in-first-out lists - LIFO lists) и даже флюгерными списками (уо-уо lists). Очереди часто называют

024356

циклическими хранилищами (circular stores) или дисциплинами обслуживания в порядке поступления (first-in-first-out lists -FIFO lists). Термины "LIFO" и "FIFO" многие годы употреблялись бухгалтерами для обозначения метода оценки и продажи товаров. Еще один термин, "стеллаж" (shelf), применялся для деков с ограниченным выводом. Аналогично деки с ограниченным вводом назывались также свитками (scrolls или rolls). Такое разнообразие имен само по себе интересно уже тем, что оно свидетельствует о важности этих концепций. Постепенно слова "стек" и "очередь" вошли в стандартную терминологию , и только термин "магазинный список" все еще остается сравнительно популярным, особенно в теории автоматов.

На практике довольно часто приходится иметь дело со стеками. Например, анализируя набор данных, часто требуется составить список возникающих исключительных ситуаций или действий, которые необходимо вьшолнить впоследствии. После анализа исходного набора данных можно перейти к вьшолнению этих действий с помощью списка, удаляя его элементы до полного опустошения списка. (Примером такой ситуации является задача о "точке перевала", которая описана в упр. 1.3.2-10.) Для организации подобного списка удобно использовать стек или очередь (хотя стек гораздо удобнее). При решении задач мы практически всегда мысленно организуем некое подобие "стека", в котором одна задача порождает другую, а другая, в свою очередь, - следуюшую. Так задачи накапливаются и соответственно разрешаются одна за другой. Аналогично процесс входа в подпрограммы и выхода из них во время вьшолнения компьютерной программы осуществляется подобно стеку. Стеки особенно полезны при обработке языков с вложенной структурой, например для языков программирования, арифметических выражений и конструкций "Schachtelsatze" немецкого языка. Вообще, стеки чаще всего встречаются при работе с явными и неявными рекурсивными алгоритмами, которые более подробно рассматриваются в главе 8.

Удалить

Вставить

Верх

Второй сверху

Третий сверху

Четвертый сверху

Начало

Второй Третий (Ь) Очередь

Крайний слева

Второй слева

Второй справа

Конец

Крайний справа

(а) Стек

Вставить или удалить

(с) Дек

Вставить или удалить

Рис. 3. Три наиболее важных класса линейных списков.