5.3. Деки
Дек(от англ. deq – double ended queue, т.е. очередь с двумя концами) – особый вид очереди в котором включение и исключение элементов может осуществляться с любого из двух концов списка. Частный случай – дек с ограниченным входом и дек с ограниченным выходом. Логическая и физическая структуры деки аналогичны структурам кольцевой FIFO-очереди.
Операции над деком заключаются в определении размера, очистки, включение/исключение элемента справа/слева. На рис. 5.2 в качестве примера показана последовательность состояний дека при включении и удалении пяти элементов. На каждом этапе стрелка указывает, с какого конца дека (левого или правого) осуществляется включение или исключение элемента. Элементы соответственно обозначены буквами A, B, C, D, E.
Рис. 5.2. Состояния дека в процессе изменения.
5.3.1. Деки в вычислительных системах
Задачи, требующие структуры дека, встречаются в вычислительной технике гораздо реже, чем задачи, реализуемые на структуре стека или очереди. Как правило, вся организация дека выполняется без каких-либо специальных средств системной поддержки. В качестве примера такой системной поддержки рассмотрим организацию буфера ввода в языке REXX. В обычном режиме буфер ввода связан с клавиатурой и работает как FIFO-очередь. В REXX имеется возможность назначить в качестве буфера ввода программный буфер и направить в него вывод программ и системных утилит.
В распоряжении пользователя имеются операции QUEUE – запись строки в конец буфера и PULL – выборка строки из начала буфера. Дополнительная операция PUSH – запись строки в начало буфера – превращает буфер в дек с ограниченным выходом. Такая структура буфера ввода позволяет программировать на REXX весьма гибкую конвейерную обработку с направлением выхода одной программы на вход другой и модификацией перенаправляемого потока.
5.4. Строки
Строка– линейно упорядоченная последовательность символов, принадлежащих конечному множеству символов, называемомуалфавитом. Строки обладают следующими свойствами:
длина, как правило, переменна, хотя алфавит фиксирован;
обычно обращение к символам строки идет с одного конца последовательности, т.е. важна упорядоченность последовательности; в связи с этим свойством строки часто называют также цепочками;
чаще всего целью доступа к строке является не отдельный ее элемент (хотя это тоже не исключается), а некоторая цепочка символов в строке.
Говоря о строках, обычно имеют в виду текстовые строки– строки, состоящие из символов, входящих в алфавит какого-либо выбранного языка, цифр, знаков препинания и других служебных символов. Однако следует иметь в виду, что символы, входящие в строку могут принадлежать любому алфавиту. Так, в языке PL/1, наряду с типом данных «символьная строка» CHAR(n) существует тип данных «битовая строка» BIT(n). Битовые строки, составляются из однобитовых символов, принадлежащих алфавиту: {0,1}. Все строковые операции применимы как к символьным, так и к битовым строкам.
Хотя строки рассматриваются в главе, посвященной полустатическим структурам данных, в тех или иных конкретных задачах изменчивость строк может варьироваться от полного ее отсутствия до практически неограниченных возможностей изменения. В большинстве языков программирования (C, PASCASL, PL/1 и др.) строки представлены полустатическими структурами.
В зависимости от назначения языка средства работы со строками занимают в языке более или менее значимое место. Язык C является языком системного программирования. Типы данных, с которыми работает язык C, максимально приближены к типам, с которыми работают машинные команды. Поскольку машинные команды не работают со строками, в языке C нет такого типа данных. Строки в C представляются в виде массивов символов. Операции над строками могут быть выполнены как операции обработки массивов или при помощи библиотечных (не встроенных) функций строковой обработки.
В языках универсального назначения строковый тип обычно является базовым: STRING в PASCAL, CHAR(n) в PL/1. Основные операции над строками реализованы как базовые операции или встроенные функции. Специальные библиотеки обеспечивают расширенный набор строковых операций.
Язык REXX ориентирован на обработку текстовой информации. Поэтому в языке нет средств описания типов данных: все данные представляются в виде символьных строк. Операции над данными, не свойственные символьным строкам, выполняются специальными функциями, либо приводят к прозрачному преобразованию типов. Например, интерпретатор REXX, встретив оператор, содержащий арифметическое выражение, сам переводит его операнды в числовой тип, вычислит выражение и преобразует результат в символьную строку. Целый ряд строковых операций является простыми операциями языка, а встроенных функций обработки строк в REXX несколько десятков.