 |
|
|
|
Очереди как структуры данных. Теория и практика
Очереди как структуры данных В проектах, где предполагается распределенная обработка или параллельные вычисления, присутствуют очереди, включая операционные системы. В данной статье рассмотрены различные аспекты применения очередей Очередь – это структура данных, которая соответствует принципу: первый пришел – первый вышел, элементы кладутся в конец очереди, а извлекаются из ее начала. Первым из очереди будет извлечен тот элемент, который будет добавлен раньше других. В англоязычной литературе для обозначения очередей довольно часто используется аббревиатура FIFO (First-In-First-Out – первым вошел – первым вышел). Основные операции, которые можно осуществить с элементами очереди:
Существует два классических варианта реализации очередей: с помощью массива и с помощью списка. Есть еще и другие варианты, но принципиально в них заложены именно эти две идеи.
Рисунок 1. Реализация очереди с помощью массива Реализация очереди с помощью массива. Если мы извлекаем из очереди элемент массива, то по идее мы должны сдвигать все элементы, что очень накладно, если ожидается большой поток. Но существует и другой подход, так называемый кольцевой алгоритм. Чтобы не сдвигать все элементы очереди, в отдельном поле Pbeg будем хранить индекс элемента массива, с которого начинается очередь, и Pend – индекс конца очереди. Как только один из указателей достигает границы массива, например, Pmax, то он сразу сбрасывается в ноль (P0). Добавление элементов происходит в конец очереди – Pend, а изъятие из начала очереди – Pbeg. Можно и наоборот – это не принципиально. Такой подход имеет один недостаток – фиксированный размер очереди, который не может превышать размерность массива, – Pmax.
Рисунок 2. Реализация очереди с помощью двух направленных списков В отличие от классического списка реализация очереди предполагает наличие двух указателей: один на начало очереди – Pbeg, второй на ее конец – Pend. В списках указатели на первый и последний элемент очереди принято называть «голова» (head) и «хвост» (tail). Вставляя элемент в очередь, мы его вставляем перед первым элементом, на который указывает указатель Pbeg, а впоследствии присваиваем указателю адрес этого элемента, таким образом, он становится первым. Извлечение из очереди, напротив, возвращает указатель на последний элемент – Pend, а сам указатель передвигаем на предыдущий. Чтобы это у нас работало, нам нужно использовать двунаправленный список. Статью целиком читайте в журнале «Системный администратор», №5 за 2014 г. на страницах 49-53. |
АЛЕКСАНДР КАЛЕНДАРЕВ, РБК Медиа, программист, 
Комментарии отсутствуют
| Добавить комментарий |
|
Комментарии могут оставлять только зарегистрированные пользователи |
|
