Очередь
Структуры данных
Очередь. Стек. Дек
В этом разделе рассмотрены часто используемые разновидности линейного списка (конечной последовательности элементов) с разными правилами выполнения операций.
Очередь
Очередь - это упорядоченная последовательность элементов некоторого типа, в которой выполняются операции включения и исключения элемента по принципу FIFO (First-In-First-Out) - "первым пришел - первым ушел": исключение происходит в начале очереди, а включение в конце (рис. 3.1).
Рис. 3.1. Очередь
Элементы данных помещаются в очередь, когда скорость поступления данных временно превышает скорость их обработки. Примером очереди является буфер ввода / вывода данных - область памяти для ввода / вывода записей файла параллельно с их обработкой. В операционных системах возникают многочисленные очереди программ: на загрузку в память, на выполнение к процессору, на обработку файлов и т.д. Очередь можно также рассматривать как механизм запоминания подзадач, возникающих при решении некоторой задачи, с последующим решением подзадач в порядке их возникновения. Пример такого применения очереди приведен в алгоритме обхода дерева в ширину.
Типовые операции над очередью:
1. Инициализация очереди (создание, подготовка к работе);
2. Включение элемента в очередь;
3. Исключение элемента из очереди;
4. Проверка пустоты очереди;
5. Проверка переполнения очереди;
6. Доступ к началу и концу (получение / изменение значения первого / последнего элемента).
Дата добавления: 2015-09-27 | Просмотры: 413 | Нарушение авторских прав
|