Каждый из нас время от времени стоит в очереди: в магазине, на бензоколонке, на автобусной остановке, к железнодорожной кассе, а студенты очень хорошо знают очередь на регистрацию курсов, которые они хотят изучить. Множество очередей используется внутри компьютерных систем, так что нам нужны программы, которые моделируют очереди и их функционирование.
Очередь представляет собой хороший пример абстрактного типа данных. Очередь предлагает своим клиентам четко определенное поведение. Клиенты ставят некие элементы в очередь по одному за раз, используя операцию поставить в очередь, и получают их по одному за раз по запросу, используя операцию исключить из очереди. В принципе очередь может быть бесконечно длинной. Реальная очередь, конечно, ограничена. Элементы возвращаются из очереди в соответствии с дисциплиной — первый вошел — первый вышел (first-in, first-out — FIFO), т.е. первый элемент, вставленный в очередь, первым же ее покидает.
Очередь скрывает внутреннее представление данных, которое как-то отражает процесс ожидания элементов в очереди. Она предлагает своим клиентам набор операций, а именно — поставить в очередь и исключить из очереди. Клиентам не надо обращать внимание на способ реализации очереди. Клиенты просто хотят работать с очередью «как объявлено». Когда клиент ставит в очередь новый элемент, очередь должна принять этот элемент и разместить его внутри себя в какой-то структуре данных типа первый вошел — первый вышел. Когда клиент хочет получить следующий элемент из начала очереди, очередь должна взять этот элемент из внутреннего представления и выпустить его во внешний мир в соответствии с дисциплиной FIFO, т.е. элемент, который находился в очереди дольше всех, должен быть следующим, возвращенным очередной операцией исключить из очереди.
АТД очередь гарантирует целостность своей внутренней структуры данных. Клиенты могут не манипулировать непосредственно этой структурой данных. Только АТД очередь имеет доступ к своим внутренним данным. Клиенты могут вызывать лишь разрешенные операции для их выполнения над представлением данных; операции, которыми открытый интерфейс АТД не обеспечен, соответствующим образом скрыты в АТД. К ним могли бы относиться выдача сообщений об ошибках, прекращение выполнения или просто игнорирование требований операций.
Комментариев нет:
Отправить комментарий