Динамические структуры данных: Очереди

В общее меню

С чего начинать?

Введение

Основные
инструкции


Массивы

Строки

Подпрограммы

Рекурсия

Динамические структуры данных

Сортировка
Динамические структуры данных: очереди

Очередь — это информационная структура, в которой для добавления элементов доступен только один конец, называемый хвостом, а для удаления — другой, называемый головой. В англоязычной литературе для обозначения очередей довольно часто используется аббревиатура FIFO (first-in-first-out — первый вошёл — первым вышел).

Очередь разумнее всего моделировать, отобразив её на двунаправленный кольцевой список. В этом случае в заглавном звене будет присутствовать информация как об указателе на голову, так и на хвост очереди.

Выделим типовые операции над очередями:

  • добавление элемента в очередь (помещение в хвост);
  • удаление элемента из очереди (удаление из головы);
  • проверка, пуста ли очередь;
  • очистка очереди.

Вот модуль, содержание которого составляют реализованные типовые операции над очередями.

Пример. Напечатать в порядке возрастания первые n натуральных чисел, в разложение которых на простые множители входят только числа 2, 3, 5.

Алгоритм решения. Введем три очереди x2, x3, x5, в которых будем хранить элементы, которые соответственно в 2, 3, 5 раз больше напечатанных, но еще не напечатаны. Рассмотрим наименьший из ненапечатанных элементов; пусть это x. Тогда он делится нацело на одно из чисел 2, 3, 5. x находится в одной из очередей и, следовательно, является в ней первым (меньшие напечатаны, а элементы очередей не напечатаны). Напечатав x, нужно его изъять и добавить его кратные. Длины очередей не превосходят числа напечатанных элементов.

 

Контрольные вопросы и задания
  1. Какую структуру данных называют очередью? Что такое хвост и голова очереди?
  2. На базе каких структур данных может быть организована очередь?
  3. Приведите из жизни примеры организации чего-либо по принципу очереди.
  4. Используя очередь, напечатайте сначала русские символы данной строки, а затем все остальные, сохранив их порядок следования.
  5. Составьте и решите задачу с использованием абстрактного типа данных "очередь".

Назад Вперед


Рейтинг ресурсов УралWeb

Сайт создан в системе uCoz