Главная страница Случайная страница
Разделы сайта
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника
Модуль очереди.
|
|
Очередь – это полезная структура данных для хранения информации в упорядоченной последовательности, подобно человеческой очереди, когда люди стоят один за другим. Очередь символов будет организована в виде модуля, реализованного двумя различными способами, и использована для решения задачи удаления лишних пробелов из текста.
Переменная типа TEXT предоставляет возможность хранения и извлечения символов в последовательности с использованием операторов READ/WRITE. Переменные типа TEXT и соответствующие операции над ними соблюдают правила программного модуля, потому что единственным способом сохранения и извлечения данных является использование операторов READ/WRITE.
Очередь – это подобное средство хранения и извлечения данных. Она работает по принципу FIFO (first-in, first-out): элементы добавляются в хвост очереди и извлекаются из головы очереди. Таким образом, очередь похожа на файл за исключением того, что добавления и удаления могут чередоваться в произвольном порядке.
Например, рассмотрим очередь, элементами которой являются символы. Типичный набор операций включает:
| Операция | Результат |
| EmptyQ | Инициализация очереди - очистка |
| AddQ(VAR Elt: CHAR) | Добавляет элемент Elt в очередь |
| DelQ | Удаляет первый элемент из очереди |
| HeadQ(Var Elt: CHAR) | Присваивает Elt в значение первого элемента очереди |
Если очередь содержит один или более элементов, DelQ удаляет первый из очереди, а HeadQ возвращает первый из очереди копированием его в Elt (но не изменяет при этом очередь). Если очередь пуста, DelQ ничего не делает, а HeadQ возвращает #.
В следующих разделах даны две реализации модуля для очереди символов. Первая реализация, названная SlowQueue основывается на очень простом представлении данных, которое не позволяет оптимизаций или повышения эффективности в процедурах модуля. Вторая реализация, FastQueue, использует более сложное представление данных и более сложные процедуры для увеличения скорости выполнения операций. Хотя обе реализации довольно различны внутренне, они имеют абсолютно одинаковое внешнее представление. Единственная разница во времени выполнения. То есть эти два модуля взаимозаменяемы в программах, которые их используют. Когда FastQueue заменяет SlowQueue, не требуется других изменений в программе использующей модуль. Программа изолирована от изменений в модуле, поскольку и программа и модуль соблюдают правила разработки и использования модулей.
|
|