Деки в вычислительных системах

Задачи, требующие структуры дека, встречаются в вычислительной технике гораздо реже, чем задачи, реализуемые на структуре стека или очереди. Как правило, вся организация дека выполняется без каких-либо специальных средств системной поддержки. В качестве примера такой системной поддержки рассмотрим организацию буфера ввода в языке REXX. В обычном режиме буфер ввода связан с клавиатурой и работает как FIFO-очередь. В REXX имеется возможность назначить в качестве буфера ввода программный буфер и направить в него вывод программ и системных утилит.

В распоряжении пользователя имеются операции QUEUE – запись строки в конец буфера и PULL – выборка строки из начала буфера. Дополнительная операция PUSH – запись строки в начало буфера – превращает буфер в дек с ограниченным выходом. Такая структура буфера ввода позволяет программировать на REXX весьма гибкую конвейерную обработку с направлением выхода одной программы на вход другой и модификацией перенаправляемого потока.

Строки

Строка – линейно упорядоченная последовательность символов, принадлежащих конечному множеству символов, называемому алфавитом. Строки обладают следующими свойствами:

- длина, как правило, переменна, хотя алфавит фиксирован;

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

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

Говоря о строках, обычно имеют в виду текстовые строки – строки, состоящие из символов, входящих в алфавит какого-либо выбранного языка, цифр, знаков препинания и других служебных символов. Однако следует иметь в виду, что символы, входящие в строку могут принадлежать любому алфавиту. Так, в языке 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 несколько десятков.