Лемма 4.2 Для ЛТД Очередь FIFO имеется возможность реализовать операции get и put с постоянным временем выполнения, используя либо массивы, либо связные списки.

Этот факт становится ясным, стоит только внимательно посмотреть на код профамм 4.14 и 4.15.

Те же соображения относительно использования оперативной памяти, которые были изложены в разделе 4.4, применимы и к очередям FIFO. Представление на базе массива требует резервирования оперативной памяти с объемом, достаточным для запоминания максимально ожидаемого количества элементов очереди. В случае же представления на базе связного списка оперативная память используется пропорционально числу элементов в структуре данных; это происходит за счет дополнительного расхода памяти на связи (между элементами) и дополнительного расхода времени на распределение и освобождение памяти для каждой операции.

Хотя по причине фундаментальной взаимосвязи между стеками и рекурсивными профаммами (см. главу 5), со стеками приходится сталкиваться чаще, чем с очередями FIFO, будут также встречаться и алгоритмы, для которых очереди являются естественными базовыми структурами данных. Как уже отмечалось, очереди и стеки используются в вычислительных приложениях чаще всего для того, чтобы отложить выполнение того или иного процесса. Хотя многие приложения, использующие очередь отложенных задач, работают корректно вне зависимости от того, какие правила удаления элементов задействуются в операциях удалить, общее время выполнения программы или использования ресурсов, может зависеть от применяемой дисциплины. Когда в подобных приложениях встречается большое количество операций вставить или удалить, выполняемых над сфуктурами данных с большим числом элементов, различия в производительности обретают первостепенную важность. Поэтому в настоящей книге столь существенное внимание уделяется таким АТД. Если бы производительность программ не интересовала, можно было бы создать один единственный АДТ с операциями вставить и удалить; однако производительность является предельно важным показателем, поэтому каждое правило, в сущности, соответствует своему АТД. Чтобы оценить эффективность отдельного АТД, потребуется учитывать издержки (т. е. расход машинного времени) двух видов: издержки, обусловленные реализацией, которые зависят от алгоритмов и структур данных, выбранных для реализации, и издержки, обусловленные отдельным правилом выполнения операции, в смысле его влияния на производительность клиентской программы. В заключение данного раздела описываются несколько таких АТД, которые будут рассматриваться подробно в следующих главах.

И стеки магазинного типа, и очереди FIFO являются частными случаями более общего АТД: обобщенной (generalized) очереди. Частные случаи обобщенных очередей различаются только правилами удаления элементов. Для стеков это правило будет таким: удалить элемент, который был вставлен последним ; для очередей FIFO правило гласит: удалить элемент, который был вставлен первым ; существует и множество других вариантов.

Простым, тем не менее, мощным вариантом является неупорядоченная очередь (random queue), подчиняющаяся следующему правилу: удалить случайный элемент ; и программа-клиент может ожидать, что она с одинаковой вероятностью получит лю-

бой из элементов очереди. Используя представление на базе массива (см. упр. 4.48), для неупорядоченной очереди можно реализовать операции с постоянным временем выполнения. Представление на базе массива требует (так же, как для стеков и очередей FIFO), чтобы оперативная память была распределена заранее. Однако в данном случае альтернативное представление на базе связного списка менее привлекательно, чем в случае стеков и очередей FIFO, поскольку эффективная реализация как операции вставки, так и операции удаления, является очень трудной задачей (см. упр. 4.49). Чтобы с высокой степенью вероятности избежать сценариев с наихудшей производительностью, неупорядоченные очереди можно использовать в качестве базиса для рандомизированных алгоритмов (см. раздел 2.7).

При описании стеков и очередей FIFO элементы идентифицировались по времени вставки в очередь. В качестве альтернативы эти абстрактные понятия можно описывать в терминах последовательного перечня упорядоченных элементов и базовых операций вставки и удаления элементов в начале и конце списка. Если элементы вставляются в конец списка и удаляются также с конца, получается стек (точно как в реализации на базе массива); если элементы вставляются в начало и удаляются в начале, также получается стек (точно как в реализации на базе связного списка); если же элементы вставляются в конец, а удаляются с начала, то получается очередь FIFO (как в реализации на базе связного списка). В конечном итоге, если элементы вставляются в начало, а удаляются с конца, также получается очередь FIFO (этот вариант не соответствует ни одной из реализаций - для его точной реализации можно было бы изменить представление на базе массива, а вот представление на базе связного списка для этой цели не подойдет из-за необходимости поддерживать указатель на конец очереди в случае удалении элементов в конце очереди). Развивая дальше эту точку зрения, приходим к абстрактному типу данных дек (double-ended queue, двухсторонняя очередь), в котором и вставки, и удаления разрешаются с обеих сторон. Его реализацию мы оставляем в качестве упражнений (см. упр. 4.43-4.47); при этом необходимо отметить, что реализация на базе массива является простым расширением программы 4.15, а для реализации на базе связного списка потребуется двухсвязный список, иначе удалять элементы дека можно будет только с одной стороны.

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

В главах с 12 по 16 исследуются символьные таблицы (symbol tables). Это обобщенные очереди, в которых элементы имеют ключи, а правило удаления элементов звучит так: удалить элемент, ключ которого равен данному, если таковой элемент существует . Этот АТД, пожалуй, самый важный из изучаемых, и можно будет ознакомиться с десятками его реализаций.

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

Упражнения

!> 4.36 Найдите содержимое элементов q[0], ... , q[4] после выполнения программой 4.15 операций, показанных на рис. 4.6. Считайте, что maxN, как и на рис. 4.8, равно 10.

!> 4.37 В последовательности

EAS * Y * QUE ***ST***IO*N***

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

4.38 Модифицируйте приведенную в тексте реализацию очереди FIFO на базе массива (программа 4.15) так, чтобы в ней вызывалась функция еггог(), если клиент пытается выполнить операцию get, когда очередь пуста, или операцию put, когда очередь переполнена.

4.39 Модифицируйте приведенную в тексте реализацию очереди FIFO на базе связного списка (программа 4.14) так, чтобы в ней вызывалась функция еггог(), если клиент пытается выполнить операцию get, когда очередь пуста, или если при выполнении put отсутствует доступная память в new.

о 4.40 В последовательности

EAs + Y + QUE ** + st+* + IO*n + + *

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

1> 4.41 Используя правила, принятые в упр. 4.40, найдите, каким образом в последовательность EasY необходимо вставить знаки плюс и звездочки, чтобы операции get возвращали следующую последовательность символов: (i) EsaY, (ii) YasE, (iii) aYsE, (iv) asYE; либо же в каждом случае докажите, что такая последовательность невозможна.

4.42 Имея две последовательности, составьте алгоритм, позволяющий определить, возможно ли в первую последовательность вставить знаки плюс и звездочки так.